Abstract
A completely insecure communication channel can only be transformed into an unconditionally secure channel if some information-theoretic primitive is given to start from. All previous approaches to realizing such authenticity and privacy from weak primitives were symmetric in the sense that security for both parties was achieved. We show that asymmetric information-theoretic security can, however, be obtained at a substantially lower price than two-way security|like in the computational-security setting, as the example of public-key cryptography demonstrates. In addition to this, we show that also an unconditionally secure bidirectional channel can be obtained under weaker conditions than previously known. One consequence of these results is that the assumption usually made in the context of quantum key distribution that the two parties share a short key initially is unnecessarily strong.
Chapter PDF
Similar content being viewed by others
References
Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pp. 175–179 (1984)
Bennett, C.H., Brassard, G., Crépeau, C., Maurer, U.M.: Generalized privacy amplification. IEEE Trans. on Information Theory 41(6), 1915–1923 (1995)
Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM Journal on Computing 17, 210–229 (1988)
Cachin, C.: Entropy measures and unconditional security in cryptography, Ph. D. Thesis, ETH Zürich, Hartung-Gorre Verlag, Konstanz (1997)
Cover, T.M., Thomas, J.A.: Elements of information theory. Wiley Series in Telecommunications (1992)
Csiszár, I., Körner, J.: Broadcast channels with confidential messages. IEEE Trans. on Information Theory 24, 339–348 (1978)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. on Information Theory 22(6), 644–654 (1976)
Dodis, Y., Smith, A.: Fooling an unbounded adversary with a short key: a notion of indistinguishability, relations to extractors, and lower bounds (2003) (manuscript)
Dodis, Y., Spencer, J.: On the (non)universality of the one-time pad. In: Proceedings of FOCS 2002, pp. 376–385 (2002)
Forney Jr., G.D.: Concatenated codes, Massachusetts Institute of Technology, Cambridge, Massachusetts (1966)
Gemmell, P., Naor, M.: Codes for interactive authentication. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 355–367. Springer, Heidelberg (1994)
König, R., Maurer, U.M., Renner, R.: On the power of quantum memory (2003), available on http://www.arxiv.org quant-ph/0305154
Maurer, U.M.: Secret key agreement by public discussion from common information. IEEE Trans. on Information Theory 39(3), 733–742 (1993)
Maurer, U.M.: Information-theoretically secure secret-key agreement by NOT authenticated public discussion. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 209–225. Springer, Heidelberg (1997)
Maurer, U.M.: Information-theoretic cryptography. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 47–64. Springer, Heidelberg (1999)
Maurer, U.M., Schmid, P.: A calculus for security bootstrapping in distributed systems. Journal of Computer Security 4(1), 55–80 (1996)
Maurer, U.M., Wolf, S.: Secret-key agreement over unauthenticated public channels – Parts I–III. IEEE Trans. on Information Theory 49(4), 822–851 (2003)
McInnes, J.L., Pinkas, B.: On the impossibility of private key cryptography with weakly random keys. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 421–436. Springer, Heidelberg (1991)
Renner, R., Wolf, S.: Unconditional authenticity and privacy from an arbitrarily weak secret and completely insecure communication. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 78–95. Springer, Heidelberg (2003)
Russell, A., Wang, H.: How to fool an unbounded adversary with a short key. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 133–148. Springer, Heidelberg (2002)
Shannon, C.E.: Communication theory of secrecy systems. Bell System Technical Journal 28, 656–715 (1949)
Wyner, D.: The wire-tap channel. Bell System Technical Journal 54(8), 1355–1387 (1975)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Renner, R., Wolf, S. (2004). The Exact Price for Unconditionally Secure Asymmetric Cryptography. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive