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.
A second alternative is TQA -- teleport the quantum message using ebits obtained by potentially insecure means in addition to an insecure forward classical channel that needs classical message authentication. (Since we prove the composable security of EBIT[PTC] and the Wegman-Carter scheme is composably secure @cite_42 , this method is composably secure.) Classical message authentication requires a long key, but most of it can be reused securely regardless of the authentication result. EBIT[PTC] uses a small key and back communication, and generates a quantum key. (Thus, back communication is needed during the protocol itself, unlike for QA+KG.) Compared to QA+KG, this scheme uses a similar amount of quantum communication, more initial key and forward classical communication, in addition to a similar amount of classical back communication. But TQA offers two advantages over QA+KG. First, failing PTC when generating ebits does not destroy the quantum message itself (so the message is not only authenticated, but protected). Second, the classical authentication key is always recycled.
@cite_42
2136675218
In their seminal work on authentication, Wegman and Carter propose that to authenticate multiple messages, it is sufficient to reuse the same hash function as long as each tag is encrypted with a one-time pad. They argue that because the one-time pad is perfectly hiding, the hash function used remains completely unknown to the adversary. Since their proof is not composable, we revisit it using a composable security framework. It turns out that the above argument is insufficient: if the adversary learns whether a corrupted message was accepted or rejected, information about the hash function is leaked, and after a bounded finite amount of rounds it is completely known. We show however that this leak is very small: Wegman and Carter's protocol is still ( ) -secure, if ( ) -almost strongly universal (_2 ) hash functions are used. This implies that the secret key corresponding to the choice of hash function can be reused in the next round of authentication without any additional error than this ( ) . We also show that if the players have a mild form of synchronization, namely that the receiver knows when a message should be received, the key can be recycled for any arbitrary task, not only new rounds of authentication.