| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Efficient 1-Out-of-n Oblivious Transfer Schemes with Universally Usable Parameters
February 2004 (vol. 53 no. 2)
pp. 232-240
Abstract—In this paper, we propose efficient and secure (string) oblivious transfer (OT_n^1) schemes for any n\geq 2. We build our OT_n^1 scheme from fundamental cryptographic techniques directly. The receiver's choice is unconditionally secure and the secrecy of the unchosen secrets is based on the hardness of the decisional Diffie-Hellman problem. Some schemes achieve optimal efficiency in terms of the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The distinct feature of our scheme is that the system-wide parameters are independent of n and universally usable, that is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. We extend our OT_n^1 schemes to distributed oblivious transfer schemes. Our distributed OT_n^1 schemes take full advantage of the research results of secret sharing. For applications, we present a method of transforming any (single-database) PIR protocol into a symmetric PIR protocol by slightly increasing the communication cost only.
[1] 232 B. Aiello, Y. Ishai, and O. Reingold, Priced Oblivious Transfer: How to Sell Digital Goods Proc. Advances in Cryptology (Eurocrypt '01), pp. 119-135, 2001.[2] D. Beaver, How to Break a 'Secure' Oblivious Transfer Protocols Proc. Advances in Cryptology (Eurocrypt '92), pp. 285-196, 1993.[3] D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, Locally Random Reductions: Improvements and Applications J. Cryptology, vol. 10, no. 1, pp. 17-36, 1997.[4] M. Bellare and S. Micali, Non-Interactive Oblivious Transfer Proc. Advances in Cryptology (Crypto '89), pp. 547-557, 1990.[5] M. Bellare and P. Rogaway, Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols Proc. First ACM Conf. Computer and Comm. Security, pp. 62-73, 1993.[6] M. Ben-Or, S. Goldwasser, and A. Wigderson, Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation Proc. 20th ACM Symp. Theory of Computing, pp. 1-10, 1988.[7] B. den Boer, Oblivious Transfer ProtectingSecrecy Proc. Advances in Cryptology (Eurocrypt '90), pp. 31-45, 1991.[8] G. Brassard and C. Crépeau, Oblivious Transfers and Privacy Amplification Proc. Advances in Cryptology (Eurocrypt '97), pp. 334-346, 1997.[9] G. Brassard, C. Crépeau, and J.-M. Robert, Information Theoretic Reduction among Disclosure Problems Proc. 27th IEEE Symp. Foundations of Computer Science, pp. 168-173, 1986.[10] G. Brassard, C. Crépeau, and J.-M. Robert, All-or-Nothing Disclosure of Secrets Proc. Advances in Cryptology (Crypto '86), pp. 234-238. 1987.[11] G. Brassard, C. Crépeau, and M. Santha, Oblivious Transfer and Intersecting Codes IEEE Trans. Information Theory, vol. 42, no. 6, pp. 1769-1780, 1996.[12] C. Cachin, On the Foundations of Oblivious Transfer Proc. Advances in Cryptology (Eurocrypt '98), pp. 361-374, 1998.[13] C. Cachin, C. Crépeau, and J. Marcil, Oblivious Transfer with a Memory-Bounded Receiver Proc. 39th IEEE Symp. Foundations of Computer Science, pp. 493-502, 1998.[14] C. Cachin, S. Micali, and M. Stadler, Computationally Private Informational Retrieval with Polylogarithmic Communication Proc. Advances in Cryptology (Eurocrypt '99), pp. 402-414, 1999.[15] R. Canetti, O. Goldreich, and S. Halevi, The Random Oracle Methodology, Revisited Proc. 30th ACM Symp. Theory of Computing, pp. 209-218, 1998.[16] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Private Information Retrieval J. ACM, vol. 45, no. 6, pp. 965-982, 1998.[17] C. Crépeau, Equivalence between Two Flavors of Oblivious Transfers Proc. Advances in Cryptology (Crypto '87), pp. 350-354, 1988.[18] C. Crépeau, J. van de Graff, and A. Tapp, Committed Oblivious Transfer and Private Multi-Party Computations Proc. Advances in Cryptology (Crypto '95), pp. 110-123, 1995.[19] G. Di Crescenzo, T. Malkin, and R. Ostrovsky, Single Database Private Information Retrieval Implies Oblivious Transfer Proc. Advances in Cryptology (Eurocrypt '00), pp. 122-138, 2000.[20] Y.Z. Ding, Oblivious Transfer in the Bounded Storage Model Proc. Advances in Cryptology (Crypto '01), pp. 155-170, 2001.[21] Y. Dodis and S. Micali, Lower Bounds for Oblivious Transfer Reductions Proc. Advances in Cryptology (Eurocrypt '99), pp. 42-45, 1999.[22] T. ElGamal, A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms IEEE Trans. Information Theory, vol. 31, no. 4, pp. 469-472, 1985.[23] S. Even, O. Goldreich, and A. Lempel, A Randomized Protocol for Signing Contracts Comm. ACM, vol. 28, pp. 637-647, 1985.[24] P. Feldman, A Practical Scheme for Non-Interactive Verifiable Secret Sharing Proc. 28th IEEE Symp. Foundations of Computer Science, pp. 427-437, 1987.[25] U. Feige and A. Shamir, Witness Indistinguishable and Witness Hiding Protocols Proc. 22nd ACM Symp. Theory of Computing, pp. 416-426, 1990.[26] M.J. Fischer, S. Micali, and C. Rackoff, A Secure Protocol for Oblivious Transfer (Extended Abstract) J. Cryptology, vol. 9, no. 3, pp. 191-195, 1996.[27] J.A. Garay and P.D. MacKenzie, Concurrent Oblivious Transfer Proc. 41st IEEE Symp. Foundations of Computer Science, pp. 314-324, 2000.[28] Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, Protecting Data Privacy in Private Data Retrieval Schemes Proc. 30th ACM Symp. Theory of Computing, pp. 151-160, 1998.[29] O. Goldreich and R. Vainish, How to Solve Any Protocol Problem: An Efficient Improvement Proc. Advances in Cryptology (Crypto '87), pp. 73-86, 1988.[30] S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems SIAM J. Computing, vol. 18, no. 1, pp. 186-208, 1989.[31] D.M. Gordon, A Survey of Fast Exponentiation Methods J. Algorithms, vol. 27, no. 1, pp. 129-146, 1998.[32] J. Kilian, Founding Cryptography on Oblivious Transfer Proc. 20th ACM Symp. Theory of Computing, pp. 20-31, 1988.[33] E. Kushilevitz and R. Ostrovsky, Replication Is Not Needed: Single Database, Computationally-Private Informational Retrieval Proc. 38th IEEE Symp. Foundations of Computer Science, pp. 364-373, 1997.[34] M. Naor and B. Pinkas, Oblivious Transfer and Polynomial Evaluation Proc. 31st ACM Symp. Theory of Computing, pp. 145-254, 1999.[35] M. Naor and B. Pinkas, Oblivious Transfer with Adaptive Queries Proc. Advances in Cryptology (Crypto '99), pp. 573-590, 1999.[36] M. Naor and B. Pinkas, Distributed Oblivious Transfer Proc. Advances in Cryptology (Asiacrypt '00), pp. 205-219, 2000.[37] M. Naor and B. Pinkas, Efficient Oblivious Transfer Protocols Proc. 12th Ann. Symp. Discrete Algorithms, pp. 448-457, 2001.[38] V. Niemi and A. Renvall, Cryptographic Protocols and Voting Result and Trends in Theoretical Computer Science, pp. 307-316, 1994.[39] T. P. Pedersen, Non-Interactive and Information-Theoretical Secure Verifiable Secret Sharing Proc. Advances in Cryptology (Crypto '91), pp. 129-140, 1991.[40] M. Rabin, How to Exchange Secrets by Oblivious Transfer Technical Report TR-81, Aiken Computation Laboratory, Harvard Univ., 1981.[41] A. Salomaa and L. Santean, Secret Selling of Secrets with Several Buyers 42nd EATCS Bulletin, pp. 178-186, 1990.[42] A. De Santis, G. Di Crescenzo, and G. Persiano, Zero-Knowledge Arguments and Public-Key Cryptography Information and Computation, vol. 121, no. 1, pp. 23-40, 1995.[43] A. De Santis, G. Di Crescenzo, and G. Persiano, Necessary and Sufficient Assumptions for Non-Interactive Zero-Knowledge Proofs of Knowledge for All NP Relations Proc. 27th Int'l Colloquium Automata, Languages, and Programming, pp. 451-462, 2000.[44] A. De Santis and G. Persiano, Public-Randomness in Public-Key Cryptography Proc. Advances in Cryptology (Eurocrypt '90), pp. 46-62, 1991.[45] A. De Santis and G. Persiano, Zero-Knowledge Proofs of Knowledge without Interactions Proc. 33rd IEEE Symp. Foundations of Computer Science, pp. 427-436, 1992.[46] J.P. Stern, A New and Efficient All-or-Nothing Disclosure of Secrets Protocol Proc. Advances in Cryptology (Asiacrypt '98), pp. 357-371, 1998.
Index Terms:
Oblivious transfer, distributed oblivious transfer, private information retrieval.
Citation:
Wen-Guey Tzeng, "Efficient 1-Out-of-n Oblivious Transfer Schemes with Universally Usable Parameters," IEEE Transactions on Computers, vol. 53, no. 2, pp. 232-240, Feb. 2004, doi:10.1109/TC.2004.1261831
