Abstract
Perfectly secret message transmission can be realized with only partially secret and weakly correlated information shared by the parties as soon as this information allows for the extraction of information-theoretically secret bits. The best known upper bound on the rate S at which such key bits can be generated has been the intrinsic information of the distribution modeling the parties’, including the adversary’s, knowledge. Based on a new property of the secret-key rate S, we introduce a conditional mutual information measure which is a stronger upper bound on S. Having thus seen that the intrinsic information of a distribution P is not always suitable for determining the number of secret bits extractable from P, we prove a different significance of it in the same context: It is a lower bound on the number of key bits required to generate P by public communication. Taken together, these two results imply that sometimes, (a possibly arbitrarily large fraction of) the correlation contained in distributed information cannot be extracted in the form of secret keys by any protocol.
Chapter PDF
Similar content being viewed by others
Keywords
References
I. Csiszár and J. Körner, Broadcast channels with confidential messages, IEEE Transactions on Information Theory, Vol. IT-24, pp. 339–348, 1978.
N. Gisin, R. Renner, and S. Wolf, Linking classical and quantum key agreement: is there a classical analog to bound entanglement?, Algorithmica, Vol. 34, pp. 389–412, 2002.
N. Gisin and S. Wolf, Linking classical and quantum key agreement: is there “bound information”?, Proceedings of CRYPTO 2000, Lecture Notes in Computer Science, Vol. 1880, pp. 482–500, Springer-Verlag, 2000.
M. Horodecki, P. Horodecki, and R. Horodecki, Mixed-state entanglement and distillation: is there a “bound” entanglement in nature?, Phys. Rev. Lett., Vol. 80, pp. 5239–5242, 1998.
P. Horodecki, Separability criterion and inseparable mixed states with positive partial transposition, Phys. Lett. A, Vol. 232, p. 333, 1997.
U. Maurer, Secret key agreement by public discussion from common information, IEEE Transactions on Information Theory, Vol. 39, No. 3, pp. 733–742, 1993.
U. Maurer and S. Wolf, Information-theoretic key agreement: from weak to strong secrecy for free, Proceedings of EUROCRYPT 2000, Lecture Notes in Computer Science, Vol. 1807, pp. 352–368, Springer-Verlag, 2000.
U. Maurer and S. Wolf, Unconditionally secure key agreement and the intrinsic conditional information, IEEE Transactions on Information Theory, Vol. 45, No. 2, pp. 499–514, 1999.
U. Maurer and S. Wolf, Towards characterizing when information-theoretic secret key agreement is possible, Proceedings of ASIACRYPT’ 96, Lecture Notes in Computer Science, Vol. 1163, pp. 196–209, Springer-Verlag, 1996.
S. Popescu and D. Rohrlich, Thermodynamics and the measure of entanglement, quant-ph/9610044, 1996.
C. E. Shannon, Communication theory of secrecy systems, Bell System Technical Journal, Vol. 28, pp. 656–715, 1949.
F. Spedalieri, personal communication, 2003.
G. S. Vernam, Cipher printing telegraph systems for secret wire and radio telegraphic communications, Journal of the American Institute for Electrical Engineers, Vol. 55, pp. 109–115, 1926.
A. D. Wyner, The wire-tap channel, Bell System Technical Journal, Vol. 54, No. 8, pp. 1355–1387, 1975.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Renner, R., Wolf, S. (2003). New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_35
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive