Private Information Retrieval - Advances in Computational PIR

Advances in Computational PIR

The first single-database computational PIR scheme to achieve communication complexity less than was created in 1997 by Kushilevitz and Ostrovsky and achieved communication complexity of for any, where is the number of bits in the database. The security of their scheme was based on the well-studied Quadratic residuosity problem. In 1999, Christian Cachin, Silvio Micali and Markus Stadler achieved poly-logarithmic communication complexity. The security of their system is based on the Phi-hiding assumption. In 2004, Helger Lipmaa achieved log-squared communication complexity, where is the length of the strings and is the security parameter. The security of his system reduces to the semantic security of a length-flexible additively homomorphic cryptosystem like the Damgård–Jurik cryptosystem. In 2005 Craig Gentry and Zulfikar Ramzan achieved log-squared communication complexity which retrieves log-square (consecutive) bits of the database. The security of their scheme is also based on a variant of the Phi-hiding assumption. All previous sublinear-communication computational PIR protocol required linear computational complexity of public-key operations. In 2009, Helger Lipmaa designed a computational PIR protocol with communication complexity and worst-case computation of public-key operations. Amortization techniques that retrieve non-consecutive bits have been considered by Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai .

As shown by Ostrovsky and Skeith, the schemes by Kushilevitz and Ostrovsky and Lipmaa use similar ideas based on homomorphic encryption. The Kushilevitz and Ostrovsky protocol is based on the Goldwasser–Micali cryptosystem while the protocol by Lipmaa is based on the Damgård–Jurik cryptosystem.