Universal composable security of quantum message authentication with key recycling

Debbie Leung (Institute for Quantum Computing, University of Waterloo), Patrick Hayden (School of Computer Science, McGill University) and Dominic Mayers (Caltech)

 

Barnum, Crepeau, Gottesman, Tapp, and Smith (BCGST02) 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 and then encodes the quantum ciphertext with an error detecting code chosen secretly (a purity test code (PTC)). Encryption was shown necessary for authentication.

We augment the protocol QA with an extra step which recycle the entire encryption key when QA accepts the message. We analyze it as a pair of protocols (quantum-authentication)+(key-generation) (QA+KG). Our main result is a proof that QA+KG is universally composable (UC) secure in the Ben-Or--Mayers model. More specifically, this implies the UC-security of (a) QA, (b) recycling of the encryption key in QA,
and (c), key-recycling of QEnc by appending PTC. For an m-qubit message, encryption requires 2m bits of key; PTC requires only $O(log m) + O(log(epsilon))$ bits of key, for probability of failure epsilon. 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 BCGST02.

Our security proof structure is inspired by and similar to that of BCGST02, reducing the security of QA to that of TQA'. In the processing, we define UC-secure entanglement, and prove the UC-security of the entanglement generating protocol given by BCGST02, which can be of independent interest.