Abstract
A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We call a PIR protocol non-trivial if its total communication is strictly less than the size of the database. Non-trivial PIR is an important cryptographic primitive with many applications. Thus, understanding which assumptions are necessary for implementing such a primitive is an important task, although (so far) not a well-understood one. In this paper we show that any non-trivial PIR implies Oblivious Transfer, a far better understood primitive. Our result not only significantly clarifies our understanding of any non-trivial PIR protocol, but also yields the following consequences:
-
Any non-trivial PIR is complete for all two-party and multi-party secure computations.
-
There exists a communication-efficient reduction from any PIR protocol to a 1-out-of-n Oblivious Transfer protocol (also called SPIR).
-
There is strong evidence that the assumption of the existence of a one-way function is necessary but not sufficient for any non-trivial PIR protocol.
Work done at the Massachusetts Institute of Technology.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Ambainis. Upper Bound on the Communication Complexity of Private Information Retrieval. In Proc. of 24th ICALP, 1997.
G. Brassard, C. Crepeau and J.-M. Robert All-or-Nothing Disclosure of Secrets In Crypto’ 86 Springer-Verlag, 1987, pp. 234–238.
A. Beimel, Y. Ishai, E. Kushilevitz, and T. Malkin. One-Way Functions are Essential for Single-Server Private Information Retrieval. In Proc. of 31st STOC, 1999.
A. Beimel, T. Malkin, S. Micali. The All-or-Nothing Nature of Two-Party Secure Computation. In Proc. of CRYPTO 99, 1999.
C. Cachin, C. Crepeau, and S. Marcil. Oblivious Transfer with a Memory Bounded Receiver. In Proc. of 39th FOCS, 1998.
C. Cachin, S. Micali, and M. Stadler. Computationally Private Information Retrieval with Polylogarithmic Communication. In Proc. of EUROCRYPT 99, 1999.
B. Chor and N. Gilboa. Computationally Private Information Retrieval. In Proc. of 29th STOC, 1997.
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private Information Retrieval. In Proc. of 36th FOCS, 1995.
T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 1991.
C. Crépeau. Equivalence Between Two Flavors of Oblivious Transfers. In Proc. of CRYPTO’ 87, 1987.
A. De Santis and P. Persiano, Zero-Knowledge Proofs of Knowledge without Interaction, In Proc. of 33rd FOCS, 1992.
G. Di Crescenzo, Y. Ishai, and R. Ostrovsky. Universal Service-Providers for Database Private Information Retrieval. In Proc. of 17th PODC, 1998.
S. Even, O. Goldreich, and A. Lempel. A Randomized Protocol for Signing Contracts. Comm. of ACM, 28:637–647, 1985.
U. Feige and A. Shamir, Witness Indistinguishable and Witness Hiding Protocols. In Proc. of 23rd STOC, 1990.
Y. Gertner, S. Goldwasser, and T. Malkin. A Random Server Model for Private Information Retrieval. In Proc. of 2nd RANDOM, 1998.
Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting Data Privacy in Private Information Retrieval Schemes. In Proc. of 30th STOC, 1998.
O. Goldreich, S. Goldwasser, and S. Micali. How to Construct Random Functions. In Journal of the ACM, vol. 38, 1991, pages 792–807, 1986.
O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing but Their Validity, and a Methodology of Cryptographic Protocol Design. In Journal of the ACM, vol. 38, 1991, pages 691–729.
O. Goldreich, S. Micali, and A. Wigderson. How to Play Any Mental Game. In Proc. of 19th STOC, 1987.
J. Hastad, R. Impagliazzo, L. Levin, and M. Luby. A Pseudorandom Generator From Any One-Way Function. SIAM J. on Computing, 1999, vol. 28, n. 4.
R. Impagliazzo and M. Luby, “One-Way Functions are Essential for Complexity-Based Cryptography” In Proc. of FOCS 89.
R. Impagliazzo and S. Rudich. Limits on the Provable Consequences of One-Way Permutations. In Proc. of 21st STOC, 1989.
Y. Ishai and E. Kushilevitz. Improved Upper Bounds on Information-Theoretic Private Information Retrieval. In Proc. of 31st STOC, 1999.
J. Kilian. Founding Cryptography on Oblivious Transfer. In Proc. of 20th STOC, 1988.
J. Kilian, E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and Completness In Private Computations. In SIAM J. on Computing, includes [26].
E. Kushilevitz, S. Micali, and R. Ostrovsky. Reducibility and Completness in Multi-party Private Computations. In Proc. of 35th FOCS 94, 1994.
E. Kushilevitz and R. Ostrovsky. Replication is Not Needed: Single-Database Computationally Private Information Retrieval. In Proc. of 38th FOCS, 1997.
E. Kushilevitz and R. Ostrovsky. One-Way Trapdoor Permutations are Sufficient for Single-database Computationally-Private Information Retrieval. In Proc. of EUROCRYPT’ 00, 2000.
E. Mann. Private Access to Distributed Information. Master’s thesis, Technion-Israel Institute of Technology, Haifa, 1998.
M. Naor. Bit Commitment Using Pseudorandom Generators. Journal of Cryptology, 4:151–158, 1991.
M. Naor and B. Pinkas. Oblivious Transfer and Polynomial Evaluation. In Proc. of 31st STOC, 1999.
M. Naor and M. Yung. Universal One-Way Hash Functions and their Cryptographic Applications. In Proc. of 21st STOC, 1989.
R. Ostrovsky and V. Shoup. Private Information Storage. In Proc. of 29th STOC, 1997.
R. Ostrovsky and A. Wigderson One-Way Functions are Essential for Non-Trivial Zero-Knowledge. In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93) pp. 1–10., IEEE 1993.
M. O. Rabin. How to Exchange Secrets by Oblivious Transfer. Technical Report TR-81, Harvard University, 1981.
J. Rompel. One-Way Functions are Necessary and Sufficient for Secure Signatures. In Proc. of 22nd STOC, 1990.
J. P. Stern. A New and Efficient All-or-Nothing Disclosure of Secrets Protocol. In Proc. of ASIACRYPT’ 98, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Crescenzo, G., Malkin, T., Ostrovsky, R. (2000). Single Database Private Information Retrieval Implies Oblivious Transfer. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_10
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67517-4
Online ISBN: 978-3-540-45539-4
eBook Packages: Springer Book Archive