Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000, it is well-known that information theoretically secure private information retrieval schemes can be built using locally decodable codes. In this paper, we construct a Byzantine robust PIR scheme using the multiplicity codes introduced by Kopparty et al. Our main contributions are on the one hand to avoid full replication of the database on each server; this significantly reduces the global redundancy. On the other hand, to have a much lower locality in the PIR context than in the LDC context. This shows that there exists two different notions: LDC-locality and PIR-locality. This is made possible by exploiting geometric properties of multiplicity codes.
In this article we tackle the issue of searchable encryption with a generalized query model. Departing from many previous works that focused on queries consisting of a single keyword, we consider the the case of queries consisting of arbitrary boolean expressions on keywords, that is to say conjunctions and disjunctions of keywords and their complement. Our construction of boolean symmetric searchable encryption BSSE is mainly based on the orthogonalization of the keyword field according to the Gram-Schmidt process. Each document stored in an outsourced server is associated with a label which contains all the keywords corresponding to the document, and searches are performed by way of a simple inner product. Furthermore, the queries in the BSSE scheme are randomized. This randomization hides the search pattern of the user since the search results cannot be associated deterministically to queries. We formally define an adaptive security model for the BSSE scheme. In addition, the search complexity is in $O(n)$ where $n$ is the number of documents stored in the outsourced server.
Private matching solutions allow two parties to find common data elements over their own datasets without revealing any additional private information. We propose a new concept involving an intermediate entity in the private matching process: we consider the problem of broker-based private matching where end-entities do not interact with each other but communicate through a third entity, namely the Broker, which only discovers the number of matching elements. Although introducing this third entity enables a complete decoupling between end-entities (which may even not know each other), this advantage comes at the cost of higher exposure in terms of privacy and security. After defining the security requirements dedicated to this new concept, we propose a complete solution which combines searchable encryption techniques together with counting Bloom filters to preserve the privacy of end-entities and provide the proof of the matching correctness, respectively.
We consider generic secure computation in the setting where a semi-honest server assists malicious clients in performing multiple secure two-party evaluations (SFE). We present practical schemes secure in the above model. The main technical difficulty that we address is efficiently ensuring input consistency of the malicious players across multiple executions. That is, we show how any player can prove he is using the same input he had used in another execution. We discuss applications of our solution, such as online profile matching.
In this paper, we present the design of the lightweight F_f family of privacy-preserving authentication protocols for RFID-systems. F_f results from a systematic design based on a new algebraic framework focusing on the security and privacy of RFID authentication protocols. F_f offers user-adjustable, strong authentication, and privacy against known algebraic attacks and recently popular SAT-solving attacks. In contrast to related work, F_f achieves these security properties without requiring an expensive cryptographic hash function. F_f is designed for a challenge-response protocol, where the tag sends random nonces and the results of HMAC-like computations of one of the nonces together with its secret key back to the reader. In this paper, the authentication and privacy of F_f is evaluated using analytical and experimental methods.