Abstract
Since bit and string oblivious transfer and commitment, two primitives of paramount importance in secure two- and multi-party computation, cannot be realized in an unconditionally secure way for both parties from scratch, reductions to weak information-theoretic primitives as well as between different variants of the functionalities are of great interest. In this context, we introduce three independent monotones—quantities that cannot be increased by any protocol|and use them to derive lower bounds on the possibility and efficiency of such reductions. An example is the transition between different versions of oblivious transfer, for which we also propose a new protocol allowing to increase the number of messages the receiver can choose from at the price of a reduction of their length. Our scheme matches the new lower bound and is, therefore, optimal.
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
Beaver, D.: Precomputing oblivious transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995)
Blundo, C., Masucci, B., Stinson, D.R., Wei, R.: Constructions and bounds for unconditionally secure non-interactive commitment schemes. Designs, Codes, and Cryptography 26(1-3), 97–110 (2002)
Brassard, G., Crépeau, C., Wolf, S.: Oblivious transfers and privacy amplification. Journal of Cryptology 16(4), 219–237 (2003)
Cerf, N.J., Massar, S., Schneider, S.: Multipartite classical and quantum secrecy monotones. Phys. Rev. A 66(042309) (2002)
Crépeau, C.: Correct and private reductions among oblivious transfers. Ph.D. thesis, MIT (1990)
Crépeau, C.: Efficient cryptographic protocols based on noisy channels. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 306–317. Springer, Heidelberg (1997)
Crépeau, C., Morozov, K., Wolf, S.: Efficient unconditional oblivious transfer from almost any noisy channel. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 47–59. Springer, Heidelberg (2005)
Crépeau, C., Sántha, M.: On the reversibility of oblivious transfer. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 106–113. Springer, Heidelberg (1991)
Dodis, Y., Micali, S.: Lower bounds for oblivious transfer reductions. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 42–55. Springer, Heidelberg (1999)
Fitzi, M., Wolf, S., Wullschleger, J.: Pseudo-signatures, broadcast, and multi-party computation from correlated randomness. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 562–578. Springer, Heidelberg (2004)
Gacs, P., Körner, J.: Common information is far less than mutual information. Probl. Contr. Inform. Theory 2, 149–162 (1973)
Imai, H., Müller-Quade, J., Nascimento, A., Winter, A.: Rates for bit commitment and coin tossing from noisy correlation. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT 2004). IEEE, Los Alamitos (2004)
Maurer, U.: Information-theoretic cryptography. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 47–64. Springer, Heidelberg (1999)
Maurer, U., Wolf, S.: Unconditionally secure key agreement and the intrinsic conditional information. IEEE Transactions on Information Theory 45(2), 499–514 (1999)
Nascimento, A.C.A., Müller-Quade, J., Otsuka, A., Imai, H.: Unconditionally secure homomorphic pre-distributed commitments. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 87–97. Springer, Heidelberg (2003)
Renner, R., Wolf, S.: New bounds in secret-key agreement: the gap between formation and secrecy extraction. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 562–577. Springer, Heidelberg (2003)
Rivest, R.L.: Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer (1999) (unpublished manuscript)
Wolf, S., Wullschleger, J.: Zero-error information and applications in cryptography. In: Proceedings of 2004 IEEE Information Theory Workshop, ITW 2004 (2004)
Wolf, S., Wullschleger, J.: Oblivious transfer is symmetric. Cryptology ePrint Archive, Report 2004/336 (2004), http://eprint.iacr.org/2004/336
Wolf, S., Wullschleger, J.: Oblivious transfer and quantum non-locality. Quantum Physics e-print Archive, quant-ph/0502030 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wolf, S., Wullschleger, J. (2005). New Monotones and Lower Bounds in Unconditional Two-Party Computation. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_28
Download citation
DOI: https://doi.org/10.1007/11535218_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28114-6
Online ISBN: 978-3-540-31870-5
eBook Packages: Computer ScienceComputer Science (R0)