Abstract
Assume \( \mathcal{A} \) owns two secret k-bit strings. She is willing to disclose one of them to \( \mathcal{B} \), at his choosing, provided he does not learn anything about the other string. Conversely, \( \mathcal{B} \) does not want \( \mathcal{A} \) to learn which secret he chose to learn. A protocol for the above task is said to implement One-out-of-two String Oblivious Transfer, denoted ( 21 )-OTk. This primitive is particularly useful in a variety of cryptographic settings. An apparently simpler task corresponds to the case k = 1 of two one-bit secrets: this is known as One-out-of-two Bit Oblivious Transfer, denoted ( 21 )-OT. We address the question of reducing ( 21 )-OTk to ( 21 )-OT. This question is not new: it was introduced in 1986. However, most solutions until now have implicitly or explicitly depended on the notion of self-intersecting codes. It can be proved that this restriction makes it asymptotically impossible to implement ( 21 )-OTk with fewer than about 3.5277k instances of ( 21 )-OT. The current paper introduces the idea of using privacy amplification as underlying technique to reduce ( 21 )-OTk to ( 21 )-OT. This allows for more efficient solutions at the cost of an exponentially small probability of failure: it is sufficient to use slightly more than 2k instances of ( 21 )-OT in order to implement ( 21 )-OTk. Moreover, we show that privacy amplification allows for the efficient implementation of ( 21 )-OTk from generalized versions of ( 21 )-OT that would not have been suitable for the earlier techniques based on self-intersecting codes. An application of this more general reduction is given.
Supported in part by Canada’s NSERC, The Canada Council and Québec’s FCAR.
Supported in part by Québec’s FCAR and Canada’s NSERC.
Chapter PDF
Similar content being viewed by others
Key Words
References
C. H. Bennett, G. Brassard, C. Crépeau and U. M. Maurer, “Generalized privacy amplification”, IEEE Transaction on Information Theory, Vol. 41, no. 6, November 1995, pp. 1915–1923.
C. H. Bennett, G. Brassard and J.-M. Robert, “Privacy amplification by public discussion”, SIAM Journal on Computing, Vol. 17, no. 2, April 1988, pp. 210–229.
G. Brassard, C. Crépeau and J.-M. Robert, “Information theoretic reductions among disclosure problems”, Proceedings of 27th Annual IEEE Symposium on Foundations of Computer Science, 1986, pp. 168–173.
G. Brassard, C. Crépeau and J.-M. Robert, “All-or-nothing disclosure of secrets”, Advances in Cryptology: Proceedings of Crypto’ 86, Springer-Verlag, 1987, pp. 234–238.
G. Brassard, C. Crépeau and M. Sántha, “Oblivious transfers and intersecting codes”, IEEE Transactions on Information Theory, Vol. 42, no. 6, November 1996, pp. 1769–1780.
C. Cachin, “Smooth entropy and Rényi entropy”, Advances in Cryptology: Proceedings of Eurocrypt’ 97, Springer-Verlag, 1997.
J. L. Carter and M. N. Wegman, “New hash functions and their use in authentication and set equality”, Journal of Computer and System Sciences, Vol. 22, 1981, pp. 265–279.
G. D. Cohen and A. Lempel, “Linear intersecting codes”, Discrete Mathematics, Vol. 56, 1985, pp. 35–43.
G. D. Cohen and G. Zémor, “Intersecting codes and independent families”, IEEE Transactions on Information Theory, Vol. 40, no. 6, November 1994, pp. 1872–1881.
C. Crépeau, “Verifiable disclosure of secrets and application”, Advances in Cryptology: Proceedings of Eurocrypt’ 89, Springer-Verlag, 1990, pp. 181–191.
C. Crépeau, Correct and Private Reductions Among Oblivious Transfers, PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1990. Supervised by Silvio Micali.
C. Crépeau, J. van de Graaf and A. Tapp, “Committed oblivious transfer and private multi-party computations”, Advances in Cryptology: Proceedings of Crypto’ 95, Springer-Verlag, 1995, pp. 110–123.
C. Crépeau and M. Sántha, “On the reversibility of oblivious transfer”, Advances in Cryptology: Proceedings of Eurocrypt’ 91, Springer-Verlag, 1991, pp. 106–113.
C. Crépeau and M. Sántha, “Efficient reductions among oblivious transfer protocols based on new self-intersecting codes”, Sequences II, Methods in Communications, Security and Computer Science, Springer-Verlag, 1991, pp. 360–368.
S. Even, O. Goldreich and A. Lempel, “A randomized protocol for signing contracts”, Proceedings of Crypto 82, Plenum Press, New York, 1983, pp. 205–210.
S. Goldwasser, S. Micali and C. Rackoff, “The knowledge complexity of interactive proof-systems”, SIAM Journal on Computing, Vol. 18, 1989, pp. 186–208.
J. Kilian, “Founding cryptography on oblivious transfer”, Proceedings of 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 20–31.
M. O. Rabin, “How to exchange secrets by oblivious transfer”, Technical Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.
A. Rényi, Probability Theory, North Holland, 1970.
D. R. Stinson, Private communication, 12 February 1997.
S. Wiesner, “Conjugate coding”, Sigact News, Vol. 15, no. 1, 1983, pp. 78–88. Original manuscript written circa 1970.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brassard, G., Crépeau, C. (1997). Oblivious Transfers and Privacy Amplification. In: Fumy, W. (eds) Advances in Cryptology — EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-69053-0_23
Download citation
DOI: https://doi.org/10.1007/3-540-69053-0_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62975-7
Online ISBN: 978-3-540-69053-5
eBook Packages: Springer Book Archive