Abstract
We present an asymptotically optimal reduction of one-out-of-two String Oblivious Transfer to one-out-of-two Bit Oblivious Transfer using Interactive Hashing in conjunction with Privacy Amplification. Interactive Hashing is used in an innovative way to test the receiver’s adherence to the protocol. We show that (1 + ε)k uses of Bit OT suffice to implement String OT for k-bit strings. Our protocol represents a two-fold improvement over the best constructions in the literature and is asymptotically optimal. We then show that our construction can also accommodate weaker versions of Bit OT, thereby obtaining a significantly lower expansion factor compared to previous constructions. Besides increasing efficiency, our constructions allow the use of any 2-universal family of Hash Functions for performing Privacy Amplification. Of independent interest, our reduction illustrates the power of Interactive Hashing as an ingredient in the design of cryptographic protocols.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-34547-3_36
Chapter PDF
Similar content being viewed by others
References
Bennett, C.H., Brassard, G., Crépeau, C., Maurer, U.: Generalized privacy amplification. IEEE Trans. on Info. Theory 41(6), 1915–1923 (1995)
Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM J. Comput. 17(2), 210–229 (1988)
Brassard, G., Crépeau, C., Wolf, S.: Oblivious transfers and privacy amplification. IEEE Transaction on Information Theory 16(4), 219–237 (2003)
Brassard, G., Crépeau, C., Santha, M.: Oblivious transfers and intersecting codes. IEEETIT: IEEE Transactions on Information Theory 42 (1996)
Cachin, C., Crépeau, C., Marcil, J.: Oblivious transfer with a memory-bounded receiver. In: IEEE Symposium on Foundations of Computer Science (1998)
Zong Ding, Y., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 446–472. Springer, Heidelberg (2004)
Dodis, Y., Micali, S.: Lower bounds for oblivious transfer reductions. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 42. Springer, Heidelberg (1999)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
Kilian, J.: Founding crytpography on oblivious transfer. In: STOC 1988: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 20–31. ACM Press, New York (1988)
Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. Journal of Cryptology 11(2) (1998)
Ostrovsky, R., Venkatesan, R., Yung, M.: Fair games against an all-powerful adversary. AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13 (1993)
Rabin, M.O.: How to exchange secrets by oblivious transfer. Technical Memo TR–81, Aiken Computation Laboratory. Harvard University (1981)
Stinson, D.R.: Some results on nonlinear zigzag functions. Journal of Combinatorial Mathematics and Combinatorial Computing 29, 127–138 (1999)
Wiesner, S.: Conjugate coding. SIGACT News 15(1), 78–88 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Crépeau, C., Savvides, G. (2006). Optimal Reductions Between Oblivious Transfers Using Interactive Hashing. In: Vaudenay, S. (eds) Advances in Cryptology - EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, vol 4004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11761679_13
Download citation
DOI: https://doi.org/10.1007/11761679_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34546-6
Online ISBN: 978-3-540-34547-3
eBook Packages: Computer ScienceComputer Science (R0)