Abstract
Assuming an insecure quantum channel and an authenticated classical channel, we propose an unconditionally secure scheme for encrypting classical messages under a shared key, where attempts to eavesdrop the ciphertext can be detected. If no eavesdropping is detected, we can securely re-use the entire key for encrypting new messages. If eavesdropping is detected, we must discard a number of key bits corresponding to the length of the message, but can re-use almost all of the rest. We show this is essentially optimal. Thus, provided the adversary does not interfere (too much) with the quantum channel, we can securely send an arbitrary number of message bits, independently of the length of the initial key. Moreover, the key-recycling mechanism only requires one-bit feedback. While ordinary quantum key distribution with a classical one time pad could be used instead to obtain a similar functionality, this would need more rounds of interaction and more communication.
Chapter PDF
Similar content being viewed by others
References
Ambainis, A., Mosca, M., Tapp, A., de Wolf, R.: Private quantum channels. In: Proceedings of the 41st IEEE Symposium on Foundations of Computer Science — FOCS 2000, pp. 547–553 (2000)
Barnum, H., Crépeau, C., Gottesman, D., Smith, A., Tapp, A.: Authentication of quantum messages. In: Proc. 43rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2002), pp. 449–458 (2002)
Ben-Or, M., Horodecki, M., Leung, D.W., Mayers, D., Oppenheim, J.: The universal composable security of quantum key distribution. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 386–406. Springer, Heidelberg (2005)
Bennett, C.H., Brassard, G., Breidbart, S.: Quantum cryptography II: How to re-use a one-time pad safely even if P = NP (1982) (unpublished manuscript)
Bhatia, R.: Matrix Analysis. Graduate Texts in Mathematics. Springer, Heidelberg (1997)
Carter, J.L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: Proceedings of the 9th ACM Symposium on Theory of Computing — STOC 1977, pp. 106–112. ACM Press, New York (1977)
Cleve, R., Gottesman, D., Lo, H.-K.: How to share a quantum secret. Physical Review Letter 83(3), 648–651 (1999)
Damgård, I.B., Pedersen, T.B., Salvail, L.: On the key-uncertainty of quantum ciphers and the computational security of one-way quantum transmission. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 91–108. Springer, Heidelberg (2004)
Damgård, I.B., Pedersen, T.B., Salvail, L.: A quantum cipher with near optimal key-recycling. rs RS-05-17, BRICS, Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Aarhus C, Denmark (2005)
Dziembowski, S., Maurer, U.M.: On generating the initial key in the bounded-storage model. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 126–137. Springer, Heidelberg (2004)
Lawrence, J., Brukner, Č., Zeilinger, A.: Mutually unbiased binary observable sets on N qubits. Physical Review A 65(3) (2002)
Leung, D.W.: Quantum vernam cipher. Quantum Information and Computation 2(1), 14–34 (2002)
Lu, C.-J.: Encryption against storage-bounded adversaries from on-line strong extractors. Journal of Cryptology 17(1), 27–42 (2004)
Nielsen, J.B.: Private communication (2005)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Oppenheim, J., Horodecki, M.: How to reuse a one-time pad and other notes on authentication, encryption and protection of quantum information, Available at http://arxiv.org/abs/quant-ph/0306161
Renner, R., König, R.: Universally composable privacy amplification against quantum adversaries. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 407–425. Springer, Heidelberg (2005)
Shor, P.W., Preskill, J.: Simple proof of security of the BB84 quantum key distribution protocol. Physical Review Letters 85, 441–444 (2000)
Vadhan, S.P.: On constructing locally computable extractors and cryptosystems in the bounded storage model. Journal of Cryptology 17(1), 43–77 (2004)
Wootters, W.K., Fields, B.D.: Optimal state-determination by mutually unbiased measurements. Annals of Physics 191(2), 363–381 (1989)
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
Damgård, I., Pedersen, T.B., Salvail, L. (2005). A Quantum Cipher with Near Optimal Key-Recycling. 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_30
Download citation
DOI: https://doi.org/10.1007/11535218_30
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)