Private information retrieval: Difference between revisions

Content deleted Content added

Inline

Revision as of 08:59, 19 May 2014

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 is retrieved. 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 (also in the quantum setting^[1]) that gives the user information theoretic privacy for their query in a single-server setting.^[2] 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^[2] in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting.^[3] 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 $n^{O({\frac {\log \log k}{k\log k}})}$ communication.

Advances in computational PIR

The first single-database computational PIR scheme to achieve communication complexity less than $n$ was created in 1997 by Kushilevitz and Ostrovsky ^[3] and achieved communication complexity of $n^{\epsilon }$ for any $\epsilon$ , where $n$ 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^[4] achieved poly-logarithmic communication complexity. The security of their system is based on the Phi-hiding assumption. In 2004, Helger Lipmaa ^[5] achieved log-squared communication complexity $O(\ell \log n+k\log ^{2}n)$ , where $\ell$ is the length of the strings and $k$ 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 [1] 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 $\Omega (n)$ public-key operations. In 2009, Helger Lipmaa ^[6] designed a computational PIR protocol with communication complexity $O(\ell \log n+k\log ^{2}n)$ and worst-case computation of $O(n/\log n)$ public-key operations. Amortization techniques that retrieve non-consecutive bits have been considered by Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai [2].

As shown by Ostrovsky and Skeith,^[7] the schemes by Kushilevitz and Ostrovsky ^[3] and Lipmaa ^[5] 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.

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. Multi-server PIR protocols tolerant of non-responsive or malicious/colluding servers are called robust or Byzantine robust respectively. These issues were first considered by Beimel and Stahl (2002). An ℓ-server system that can operate where only k of the servers respond, ν of the servers respond incorrectly, and which can withstand up to t colluding servers without revealing the client's query is called "t-private ν-Byzantine robust k-out-of-ℓ PIR" [DGH 2012]. In 2012, C. Devet, I. Goldberg, and N. Heninger (DGH 2012) proposed an optimally robust scheme that is Byzantine-robust to $\nu <k-t-1$ which is the theoretical maximum value. It is based on an earlier protocol of Goldberg that uses Shamir's Secret Sharing to hide the query. Goldberg has released a C++ implementation on Sourceforge.[3]

Relation to other cryptographic primitives

One-way functions 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 [4] 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 functions are implied by any one-round computational PIR scheme, as shown by Ishai, Kushilevitz and Ostrovsky.^[8]

PIR variations

The basic motivation for Private Information Retrieval is a family of two-party protocols in which one of the parties (the sender) owns a database, and the other part (the receiver) wants to query it with certain privacy restrictions and warranties. So, as a result of the protocol, if the receiver wants the i-th value in the database he must learn the i-th entry, but the sender must learn nothing about i. In a general PIR protocol, a computationally unbounded sender can learn nothing about i so privacy is theoretically preserved. Since the PIR problem was posed, different approaches to its solution have been pursued and some variations were proposed.

A CPIR (Computationally Private Information Retrieval) protocol is similar to a PIR protocol: the receiver retrieves an element chosen by him from sender's database, so that the sender obtains no knowledge about which element was transferred.^[6] The only difference is that privacy is safeguarded against a polynomially bounded sender.^[9]

A CSPIR (Computationally Symmetric Private Information Retrieval) protocol is used in a similar scenario in which a CPIR protocol is used. If the sender owns a database, and the receiver wants to get the i-th value in this database, at the end of the execution of a SPIR protocol, the receiver should have learned nothing about values in the database other than the i-th one.^[9]

Notes

^ Baumeler, Ämin (17 April 2014). "Quantum Private Information Retrieval has Linear Communication Complexity". Journal of Cryptology. doi:10.1007/s00145-014-9180-2. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ ^a ^b Chor, Benny (1 November 1998). "Private information retrieval" (PDF). Journal of the ACM. 45 (6): 965–981. doi:10.1145/293347.293350. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ ^a ^b ^c Kushilevitz, Eyal (1997). "Replication is not needed: single database, computationally-private information retrieval". Proceedings of the 38th Annual Symposium on Foundations of Computer Science (PDF). Miami Beach, Florida, USA: IEEE Computer Society. pp. 364–373. ISBN 0-8186-8197-7. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Cachin, Christian (1999). "Computationally Private Information Retrieval with Polylogarithmic Communication". Advances in Cryptology - EUROCRYPT '99 (PDF). Prague, Czech Republic: Springer-Verlag. pp. 402–414. ISBN 978-3-540-48910-8. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ ^a ^b Lipmaa, Helger (2005). "An Oblivious Transfer Protocol with Log-Squared Communication". Proceedings of the 8th International Conference on Information Security (ISC 2005) (PDF). Singapore: Springer-Verlag. pp. 314–328. ISBN 978-3-540-31930-6. Archived from the original on 19 May 2014.
^ ^a ^b Lipmaa, Helger (2010). "First CPIR Protocol with Data-Dependent Computation". Proceedings of the 12th International Conference on Information Security and Cryptology (PDF). Seoul, Korea: Springer-Verlag. pp. 193–210. ISBN 978-3-642-14423-3. Archived from the original on 19 May 2014.
^ Ostrovsky, Rafail (2007). "A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PDF). Springer-Verlag. pp. 393–411. ISBN 978-3-540-71677-8. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Ishai, Yuval (2005). "Sufficient Conditions for Collision-Resistant Hashing". Proceedings of the Second Theory of Cryptography Conference (PDF). Cambridge, MA, USA: Springer-Verlag. pp. 445–456. ISBN 978-3-540-30576-7. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ ^a ^b Saint-Jean, Felipe (2005). "A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol". Yale University Technical Report YALEU/DCS/TR-1333 (PDF).

References

A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond. Breaking the $O(n^{1/(2k-1)})$ barrier for information-theoretic private information retrieval. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, pages 261-270, 2002.
A. Beimel and Y. Stahl, Robust information-theoretic private information retrieval, in Proceedings of the 3rd International Conference on Security in Communication Networks (SCN'02), pp. 326–341, 2003. Cite is from DGH 2012, op. cit.
[DGH 2012] Casey Devet, Ian Goldberg, and Nadia Heninger, Optimally Robust Private Information Retrieval, 21st USENIX Security Symposium, August 2012.
Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, ECCC TR06-127, 2006.

External links

[1] Baumeler, Ämin (17 April 2014). "Quantum Private Information Retrieval has Linear Communication Complexity". Journal of Cryptology. doi:10.1007/s00145-014-9180-2. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[ChoKusGolSud98-2] Chor, Benny (1 November 1998). "Private information retrieval" (PDF). Journal of the ACM. 45 (6): 965–981. doi:10.1145/293347.293350. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[KusOst97-3] Kushilevitz, Eyal (1997). "Replication is not needed: single database, computationally-private information retrieval". Proceedings of the 38th Annual Symposium on Foundations of Computer Science (PDF). Miami Beach, Florida, USA: IEEE Computer Society. pp. 364–373. ISBN 0-8186-8197-7. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[4] Cachin, Christian (1999). "Computationally Private Information Retrieval with Polylogarithmic Communication". Advances in Cryptology - EUROCRYPT '99 (PDF). Prague, Czech Republic: Springer-Verlag. pp. 402–414. ISBN 978-3-540-48910-8. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[Lip04-5] Lipmaa, Helger (2005). "An Oblivious Transfer Protocol with Log-Squared Communication". Proceedings of the 8th International Conference on Information Security (ISC 2005) (PDF). Singapore: Springer-Verlag. pp. 314–328. ISBN 978-3-540-31930-6. Archived from the original on 19 May 2014.

[Lip09-6] Lipmaa, Helger (2010). "First CPIR Protocol with Data-Dependent Computation". Proceedings of the 12th International Conference on Information Security and Cryptology (PDF). Seoul, Korea: Springer-Verlag. pp. 193–210. ISBN 978-3-642-14423-3. Archived from the original on 19 May 2014.

[7] Ostrovsky, Rafail (2007). "A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography (PDF). Springer-Verlag. pp. 393–411. ISBN 978-3-540-71677-8. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[8] Ishai, Yuval (2005). "Sufficient Conditions for Collision-Resistant Hashing". Proceedings of the Second Theory of Cryptography Conference (PDF). Cambridge, MA, USA: Springer-Verlag. pp. 445–456. ISBN 978-3-540-30576-7. Archived from the original on 19 May 2014. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[TR1-9] Saint-Jean, Felipe (2005). "A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol". Yale University Technical Report YALEU/DCS/TR-1333 (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 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 is retrieved. 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 (also in the [[Quantum cryptography|quantum]] setting<ref>Ämin Baumeler, Anne Braodbent: [http://dx.doi.org/10.1007/s00145-014-9180-2 Quantum Private Information Retrieval has Linear Communication Complexity]. J. Cryptol (2014).</ref>) that gives the user [[information theoretic security|information theoretic privacy]] for their query in a single-server setting.<ref name="ChoKusGolSud98">Benny Chor, Eyal Kushilevitz, [[Oded Goldreich]], [[Madhu Sudan]]: [http://www.tau.ac.il/~bchor/PIR.pdf Private Information Retrieval]. J. ACM 45(6): 965–981 (1998)</ref> There are two ways to address this problem: one is to make the server [[computational boundedness|computationally bounded]] and the other is to assume that there are multiple non-cooperating servers, each having a copy of the database.
+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 (also in the [[Quantum cryptography|quantum]] setting<ref>{{cite journal|last=Baumeler|first=Ämin|coauthors=Broadbent, Anne|title=Quantum Private Information Retrieval has Linear Communication Complexity|journal=Journal of Cryptology|date=17 April 2014|doi=10.1007/s00145-014-9180-2}}</ref>) that gives the user [[information theoretic security|information theoretic privacy]] for their query in a single-server setting.<ref name="ChoKusGolSud98">{{cite journal|last=Chor|first=Benny|coauthors=Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu|title=Private information retrieval|journal=Journal of the ACM|date=1 November 1998|volume=45|issue=6|pages=965–981|doi=10.1145/293347.293350|url=http://www.tau.ac.il/~bchor/PIR.pdf}}</ref> There are two ways to address this problem: one is to make the server [[computational boundedness|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<ref name="ChoKusGolSud98 "/> in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting.<ref name="KusOst97">Eyal Kushilevitz, [[Rafail Ostrovsky]]: Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval. FOCS 1997: 364–373 [http://www.cs.ucla.edu/~rafail/PUBLIC/34.pdf (PDF)]</ref> 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 <math>n^{O(\frac{\log \log k}{k \log k})}</math> communication.
+The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan<ref name="ChoKusGolSud98 "/> in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting.<ref name="KusOst97">{{cite book|last=Kushilevitz|first=Eyal|title=Proceedings of the 38th Annual Symposium on Foundations of Computer Science|date=1997|publisher=IEEE Computer Society|location=Miami Beach, Florida, USA|isbn=0-8186-8197-7|pages=364-373|url=http://dx.doi.org/10.1109/SFCS.1997.646125|coauthors=Ostrovsky, Rafail|archiveurl=http://www.cs.ucla.edu/~rafail/PUBLIC/34.pdf|archivedate=19 May 2014|chapter=Replication is not needed: single database, computationally-private information retrieval}}</ref> 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 <math>n^{O(\frac{\log \log k}{k \log k})}</math> communication.
 ==Advances in computational PIR==
-The first single-database computational PIR scheme to achieve communication complexity less than <math>n</math> was created in 1997 by Kushilevitz and Ostrovsky <ref name="KusOst97"/> and achieved communication complexity of <math>n^\epsilon</math> for any <math>\epsilon</math>, where <math>n</math> 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]] <ref name="Lip04">Helger Lipmaa: An Oblivious Transfer Protocol with Log-Squared Communication. ISC 2005: 314–328 [http://eprint.iacr.org/2004/063.pdf (PDF)]</ref> achieved log-squared communication complexity <math>O(\ell \log n+k \log^2 n)</math>, where <math>\ell</math> is the length of the strings and <math>k</math> 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 <math>\Omega (n)</math> public-key operations. In 2009, [[Helger Lipmaa]] <ref name="Lip09">Helger Lipmaa: First CPIR Protocol with Data-Dependent Computation. ICISC 2009: 193--210 [http://eprint.iacr.org/2009/395 (PDF)]></ref> designed a computational PIR protocol with communication complexity <math>O(\ell \log n+k \log^2 n)</math> and worst-case computation of <math>O (n / \log n)</math> 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].
+The first single-database computational PIR scheme to achieve communication complexity less than <math>n</math> was created in 1997 by Kushilevitz and Ostrovsky <ref name="KusOst97"/> and achieved communication complexity of <math>n^\epsilon</math> for any <math>\epsilon</math>, where <math>n</math> 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<ref>{{cite book|last=Cachin|first=Christian|title=Advances in Cryptology - EUROCRYPT '99|date=1999|publisher=Springer-Verlag|location=Prague, Czech Republic|isbn=978-3-540-48910-8|pages=402-414|url=http://dx.doi.org/10.1007/3-540-48910-X_28|coauthors=Micali, Silvio; Stadler, Markus|archiveurl=http://www.zurich.ibm.com/~cca/papers/cpir.pdf|archivedate=19 May 2014|chapter=Computationally Private Information Retrieval with Polylogarithmic Communication}}</ref> achieved poly-logarithmic communication complexity. The security of their system is based on the [[Phi-hiding assumption]]. In 2004, [[Helger Lipmaa]] <ref name="Lip04">{{cite book|last=Lipmaa|first=Helger|title=Proceedings of the 8th International Conference on Information Security (ISC 2005)|date=2005|publisher=Springer-Verlag|location=Singapore|isbn=978-3-540-31930-6|pages=314-328|url=http://dx.doi.org/10.1007/11556992_23|archiveurl=http://eprint.iacr.org/2004/063.pdf|archivedate=19 May 2014|chapter=An Oblivious Transfer Protocol with Log-Squared Communication}}</ref> achieved log-squared communication complexity <math>O(\ell \log n+k \log^2 n)</math>, where <math>\ell</math> is the length of the strings and <math>k</math> 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 <math>\Omega (n)</math> public-key operations. In 2009, [[Helger Lipmaa]] <ref name="Lip09">{{cite book|last=Lipmaa|first=Helger|title=Proceedings of the 12th International Conference on Information Security and Cryptology|date=2010|publisher=Springer-Verlag|location=Seoul, Korea|isbn=978-3-642-14423-3|pages=193-210|url=http://dx.doi.org/10.1007/978-3-642-14423-3_14|archiveurl=http://eprint.iacr.org/2009/395.pdf|archivedate=19 May 2014|chapter=First CPIR Protocol with Data-Dependent Computation}}</ref> designed a computational PIR protocol with communication complexity <math>O(\ell \log n+k \log^2 n)</math> and worst-case computation of <math>O (n / \log n)</math> 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,<ref>Rafail Ostrovsky, William Skeith. A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Proceedings of the Public Key Cryptography 2007 conference, pp. 393–411. (PKC-2007). [http://www.cs.ucla.edu/~rafail/PUBLIC/78.pdf (PDF)]</ref> the schemes by Kushilevitz and Ostrovsky <ref name="KusOst97"/> and Lipmaa <ref name="Lip04"/> 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]].
+As shown by Ostrovsky and Skeith,<ref>{{cite book|last=Ostrovsky|first=Rafail|title=Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography|date=2007|publisher=Springer-Verlag|isbn=978-3-540-71677-8|pages=393-411|url=http://dx.doi.org/10.1007/978-3-540-71677-8_26|coauthors=Skeith III, William E.|archiveurl=https://eprint.iacr.org/2007/059.pdf|archivedate=19 May 2014|chapter=A Survey of Single-Database Private Information Retrieval: Techniques and Applications}}</ref> the schemes by Kushilevitz and Ostrovsky <ref name="KusOst97"/> and Lipmaa <ref name="Lip04"/> 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]].
 ==Advances in information theoretic PIR==
@@ Line 18: / Line 18: @@
 [[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.<ref>[http://www.springerlink.com/content/dr8aw5rdcjqx220f/ Sufficient Conditions for Collision-Resistant Hashing]</ref>
+Collision-resistant [[cryptographic hash function]]s are implied by any one-round computational PIR scheme, as shown by Ishai, Kushilevitz and Ostrovsky.<ref>{{cite book|last=Ishai|first=Yuval|title=Proceedings of the Second Theory of Cryptography Conference|date=2005|publisher=Springer-Verlag|location=Cambridge, MA, USA|isbn=978-3-540-30576-7|pages=445-456|url=http://dx.doi.org/10.1007/978-3-540-30576-7_24|coauthors=Kushilevitz, Eyal; Ostrovsky, Rafail|archiveurl=http://www.cs.ucla.edu/~rafail/PUBLIC/66.pdf|archivedate=19 May 2014|chapter=Sufficient Conditions for Collision-Resistant Hashing}}</ref>
 ==PIR variations==
 The basic motivation for Private Information Retrieval is a family of two-party protocols in which one of the parties (the ''sender'') owns a database, and the other part (the ''receiver'') wants to query it with certain privacy restrictions and warranties. So, as a result of the protocol, if the ''receiver'' wants the ''i-th'' value in the database he  must learn the ''i-th'' entry, but the ''sender'' must learn nothing about ''i''. In a general PIR protocol, a computationally unbounded ''sender'' can learn nothing about ''i'' so privacy is theoretically preserved. Since the PIR problem was posed, different approaches to its solution have been pursued and some variations were proposed.
-A CPIR (Computationally Private Information Retrieval) protocol is similar to a PIR protocol: the ''receiver'' retrieves an element chosen by him from sender's database, so that the ''sender'' obtains no knowledge about which element was transferred.<ref name="Lip09" /> The only difference is that privacy is safeguarded against a polynomially bounded sender.<ref name=TR1 >Felipe Saint-Jean, [http://crypto.stanford.edu/portia/papers/TR1333.pdf A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol]. Yale University Technical Report YALEU/DCS/TR-1333 YALEU/DCS/TR-1333 July 2005.</ref>
+A CPIR (Computationally Private Information Retrieval) protocol is similar to a PIR protocol: the ''receiver'' retrieves an element chosen by him from sender's database, so that the ''sender'' obtains no knowledge about which element was transferred.<ref name="Lip09" /> The only difference is that privacy is safeguarded against a polynomially bounded sender.<ref name="TR1">{{cite book|last=Saint-Jean|first=Felipe|title=Yale University Technical Report YALEU/DCS/TR-1333|date=2005|url=http://crypto.stanford.edu/portia/papers/TR1333.pdf|chapter=A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol}}</ref>
 A CSPIR (Computationally Symmetric Private Information Retrieval) protocol is used in a similar scenario in which a CPIR protocol is used. If the ''sender'' owns a database, and the ''receiver'' wants to get the ''i-th'' value in this database, at the end of the execution of a SPIR protocol, the ''receiver'' should have learned nothing about values in the database other than the ''i-th'' one.<ref name=TR1 />
@@ Line 39: / Line 39: @@
 * [DGH 2012] Casey Devet, [[Ian Goldberg]], and Nadia Heninger, ''[http://www.cs.uwaterloo.ca/~iang/pubs/orpir-usenix.pdf Optimally Robust Private Information Retrieval]'', 21st USENIX Security Symposium, August 2012.
 * Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, {{ECCC|2006|06|127}}, 2006.
-* E. Kushilevitz and R. Ostrovsky,  [http://www.cs.ucla.edu/~rafail/PUBLIC/34.html Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval]  FOCS '97, 1997.
-* B. Chor, O Goldreich, E. Kushilevitz and M Sudan [http://www.cs.umd.edu/~gasarch/pir/first.pdf Private Information Retrieval]. ''Journal of the ACM Vol. 45 No. 6,  November 1998, p965–982
 {{Refend}}