Construction of computationally efficient PIR protocols
Julien Lavauzelle
INRIA Saclay
Private information retrieval (PIR) protocols allow a user to retrieve entries of a database without revealing the index of the desired item. Information-theoretical privacy can be achieved by the use of several servers and specific
retrieval algorithms. Most of known PIR protocols focus on decreasing the number of bits exchanged between the client and the server(s) during the retrieval process. However, only a few works address the issue of the computation complexity of the servers.
After a short review of techniques allowing computation-efficient PIR schemes, we introduce our PIR construction featuring reasonable communication complexity, low storage overhead and optimal computational complexity for the servers. Our scheme relies on an encoding of the database using incidence matrices of combinatorial structures called transversal designs. We also present instances of our construction, making use of finite geometries and orthogonal arrays, and we finally give a generalisation of our main construction for resisting collusions of servers.
Julien Lavauzelle received his engineer's degree at the École Nationale Supérieure des Techniques Avancées (ENSTA, Palaiseau, France) in 2014, where he specialized in information systems and their security. In 2015, he received a master's degree in theoretical computer science at the École Normale Supérieure, Cachan. Since 2015, he is PhD student in the Crypto team hosted by the laboratory of computer science of École Polytechnique and by Inria (Palaiseau, France), under the supervision of Daniel Augot and Françoise Levy-dit-Vehel. His main interests concern the use of codes with locality in cryptographic applications, such that private information retrieval protocols, proofs of retrievability, or secret sharing schemes.