Private information retrieval
Encyclopedia
In cryptography
, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database
without revealing which item they are retrieving. PIR is a weaker version of 1-out-of-n oblivious transfer
, where it is also required that the user should not get information about other database items.
One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol that gives the user information theoretic privacy
for their query in a single-server setting. There are two ways to address this problem: one is to make the server computationally bounded and the other is to assume that there are multiple non-cooperating servers, each having a copy of the database.
The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting. Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and k-database (information theoretic) PIR can be done with
communication.
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 http://www.zurich.ibm.com/~cca/papers/cpir.pdf 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 http://citeseer.ist.psu.edu/context/2700426/0 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 http://citeseer.ist.psu.edu/ishai04batch.html.
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.
s are necessary, but not known to be sufficient, for nontrivial (i.e., with sublinear communication) single database computationally private information retrieval. In fact, such a protocol was proved by G. Di Crescenzo, T. Malkin and R. Ostrovsky
in http://citeseer.ist.psu.edu/dicrescenzo00single.html to imply oblivious transfer (see below).
Oblivious transfer
, also called symmetric PIR, is PIR with the additional restriction that the user may not learn any item other than the one she requested. It is termed symmetric because both the user and the database have a privacy requirement.
Collision-resistant cryptographic hash function
s are implied by any one-round computational PIR scheme, as shown by Ishai, Kushilevitz and Ostrovsky.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
without revealing which item they are retrieving. PIR is a weaker version of 1-out-of-n oblivious transfer
Oblivious transfer
In cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....
, where it is also required that the user should not get information about other database items.
One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol that gives the user information theoretic privacy
Information theoretic security
A cryptosystem is information-theoretically secure if its security derives purely from information theory. That is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the security...
for their query in a single-server setting. There are two ways to address this problem: one is to make the server computationally bounded and the other is to assume that there are multiple non-cooperating servers, each having a copy of the database.
The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting. Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and k-database (information theoretic) PIR can be done with
communication.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 problemQuadratic residuosity problem
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
. In 1999, Christian Cachin, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
and Markus Stadler http://www.zurich.ibm.com/~cca/papers/cpir.pdf achieved poly-logarithmic communication complexity. The security of their system is based on the Phi-hiding assumption
Phi-hiding assumption
The phi-hiding assumption or Φ-hiding assumption is an assumption about the difficulty of finding small factors of φ where m is a number whose factorization is unknown, and φ is Euler's totient function. The security of many modern cryptosystems comes from the perceived difficulty of certain...
. 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 securitySemantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
of a length-flexible additively homomorphic cryptosystem like the Damgård–Jurik cryptosystem. In 2005 Craig Gentry
Craig Gentry
Craig Alan Gentry is a Major League Baseball outfielder for the Texas Rangers.-Baseball career:...
and Zulfikar Ramzan http://citeseer.ist.psu.edu/context/2700426/0 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 OstrovskyRafail Ostrovsky
Rafail Ostrovsky is a professor of computer science and mathematics at UCLA and a well-known researcher in algorithms and cryptography. Prof. Ostrovsky received his Ph.D. from MIT in 1992...
and Amit Sahai http://citeseer.ist.psu.edu/ishai04batch.html.
As shown by Ostrovsky and Skeith, the schemes by Kushilevitz and Ostrovsky and Lipmaa use similar ideas based on homomorphic encryption
Homomorphic encryption
Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another algebraic operation performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem....
. 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.
Advances in information theoretic PIR
Achieving information theoretic security requires the assumption that there are multiple non-cooperating servers, each having a copy of the database. Without this assumption, any information-theoretically secure PIR protocol requires an amount of communication that is at least the size of the database n.Relation to other cryptographic primitives
One-way functionOne-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
s are necessary, but not known to be sufficient, for nontrivial (i.e., with sublinear communication) single database computationally private information retrieval. In fact, such a protocol was proved by G. Di Crescenzo, T. Malkin and R. Ostrovsky
Rafail Ostrovsky
Rafail Ostrovsky is a professor of computer science and mathematics at UCLA and a well-known researcher in algorithms and cryptography. Prof. Ostrovsky received his Ph.D. from MIT in 1992...
in http://citeseer.ist.psu.edu/dicrescenzo00single.html to imply oblivious transfer (see below).
Oblivious transfer
Oblivious transfer
In cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....
, also called symmetric PIR, is PIR with the additional restriction that the user may not learn any item other than the one she requested. It is termed symmetric because both the user and the database have a privacy requirement.
Collision-resistant cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s are implied by any one-round computational PIR scheme, as shown by Ishai, Kushilevitz and Ostrovsky.