Barnum, Crepeau, Gottesman, Tapp, and Smith (quant-ph 0205128) proposed methods for authentication of quantum messages. The first method is an interactive protocol (TQA') based on teleportation. The second method is a noninteractive protocol (QA) in which the sender first encrypts the message using a protocol QEnc and then encodes the quantum ciphertext with an error correcting code chosen secretly from a set (a purity test code (PTC)). Encryption was shown to be necessary for authentication. We augment the protocol QA with an extra step which recycles the entire encryption key provided QA accepts the message. We analyze the resulting integrated protocol for quantum authentication and key generation, which we call QA+KG. Our main result is a proof that QA+KG is universal composably (UC) secure in the Ben-Or-Mayers model (quant-ph 0409062). More specifically, this implies the UC-security of (a) QA, (b) recycling of the encryption key in QA, and (c) key-recycling of the encryption scheme QEnc by appending PTC. For an m-qubit message, encryption requires 2m bits of key; but PTC can be performed using only O(log m) + O(log e) bits of key for probability of failure e. Thus, we reduce the key required for both QA and QEnc, from linear to logarithmic net consumption, at the expense of one bit of back communication which can happen any time after the conclusion of QA and before reusing the key. UC-security of QA also extends security to settings not obvious from quant-ph 0205128. Our security proof structure is inspired by and similar to that of quant-ph 0205128, reducing the security of QA to that of TQA'. In the process, we define UC-secure entanglement, and prove the UC-security of the entanglement generating protocol given in quant-ph 0205128, which could be of independent interest.
In 2005, Damgard, Pedersen, and Salvail @cite_20 proposed key recycling for the encryption of classical messages by using the Wegman-Carter classical authentication scheme followed by a quantum encryption scheme based on key uncertainty or locking @cite_34 . Encryption of quantum messages was said to be possible in the introduction but no proof of this assertion was given in the text. Regardless, the results in @cite_20 are quite different from ours because encryption and authentication of classical messages are much weaker tasks cryptographically. Also, locking is highly non-composable when a quantum adversary has quantum memory and delays measurements. It is unclear how the analysis in @cite_20 fits into the composability framework, despite a claim (without formal definition or proof) of the composable security of the regenerated key. (We detail the differences here since an earlier version of our paper was rejected in 2007 by a referee who assumed this work to be similar to @cite_20 .)
@cite_34 @cite_20
1982305921 1498523337
We show that there exist bipartite quantum states which contain a large locked classical correlation that is unlocked by a disproportionately small amount of classical communication. In particular, there are (2n + 1)-qubit states for which a one-bit message doubles the optimal classical mutual information between measurement results on the subsystems, from n 2 bits to n bits. This phenomenon is impossible classically. However, states exhibiting this behavior need not be entangled. We study the range of states exhibiting this phenomenon and bound its magnitude. 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.