Efficient oblivious transfer protocols

ABSTRACT

1 Introduction

Oblivious Transfer (OT) protocols allow one party, the sender, to transmit part of its inputs to another party, the chooser, in a manner that protects both of them: the sender is assured that the chooser does not receive more information than it is entitled, while the chooser is assured that the sender does not learn which part of the inputs it received. OT is used as a key component in many applications of cryptography. Its computational requirements are quite demanding and they are likely to be the bottleneck in many applications that invoke it.

1.1 Contributions.

This paper presents several significant improvements to oblivious transfer (OT) protocols of strings, and in particular: (i) Improving the efficiency of applications which many invocations of oblivious transfer. (ii) Providing the first two-round OT protocol whose security analysis does not invoke the random oracle model.

REFERENCES

• 1: W. Aiello, Y. Ishai and O. Reingold, Oblivious Commerce: How to Sell Digital Goods, Manuscript, 2000.
• 2: M. Bellare, J. Garay and T. Rabin. "Fast Batch Verification for Modular Exponentiation and Digital Signatures." Proc. Advances in Cryptology-Eurocrypt '98, LNCS (1403), Springer-Verlag, pp. 236-250, 1998.
• 3: Mihir Bellare , Silvio Micali, Non-interactive oblivious transfer and applications, Proceedings on Advances in cryptology, p.547-557, July 1989, Santa Barbara, California, United States
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 6: C. Cachin, S. Micaii and M. Stadler, Computationally Private Information Retrieval With Polylogarith. mic Communication, Advances in Cryptology - Eurocrypt '99, LNCS 1592, Springer-Verlag, 1999.
• 7: Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
• 8: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 9: R. Canetti and S. Goldwasser: An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack, Advances in Cryptology - EUROCRYPT '99, Springer-Verlag, 1999, pp. 90-106.
• 10: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 11: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 12: A. De Santis, G. Di Crescenzo, G. Persians, and M. Yung, On Monotone Formula Closure of SZK, Proc. of 35th IEEE Symposium on Foundations of Computer Science (FOCS '94), Santa Fe, New Mexico, USA, November 20-22, 1994, pp. 454-465.
• 13: W. Dai, Crypts++ 3.1 Benchmarks, available at http ://www. eskimo, com/'weidai/benchmarks, html
• 14: W. Diffie and M. Hellman, New directions in cryptography, IEEE 'Ira. Inform. Theory, 22 (6), 644-654, 1976.
• 15: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 16: Cynthia Dwork , Larry Stockmeyer , Moni Naor , Omer Reingold, Magic Functions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.523, October 17-18, 1999
• 17: C. Dwork , M. Naor, Zaps and their applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.283, November 12-14, 2000
• 18: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 19: A. Fiat, Batch RSA, J. of Crypt. 10(2): 75-88 (1997).
• 20: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 21: R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
• 22: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 23: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 24: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 25: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 26: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 27: M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
• 28: M. O. Rabin, "How to exchange secrets by oblivious transfer", Tech. Memo TR-81, Aiken Computation Laboratory, 1981.
• 29: Kazue Sako , Joe Kilian, Secure Voting Using Partially Compatible Homomorphisms, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.411-424, August 21-25, 1994
• 30: C. P. Schnorr, "Efficient Signature Generation by Smart Cards", J. of Crypt., 4(3), pp. 161-174, 1991.
• 31: V. Shoup Lower bounds for discrete logarithms and related problems, in Proc. Eurocrypt '97, Springer Verlag LNCS 1233, pp. 256-266, 1997.
• 32: V. Shoup and R. Gennaxo , Securing threshold eryptosystems against chosen ciphertext attack, Proc. Advances in Cryptology - Eurocrypt'98, Springer-Verlag LNCS 1403, 1998, pp. 1-16.
• 33: M. Stadler, Publicly verifiable secret sharing, Proe. Advances in Cryptology - EUROCRYPT '96, LNCS, vol. 1070, Springer, 1996, pp. 190-199.
• 34: A.C. Yao, "How to generate and exchange secrets", Proe. of the 27th IEEE Syrup. on Foundations of Computer Science, 1986, pp. 162-167.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Algorithms, Security, Standardization, Theory