The Universal Composable Security of Quantum Message Authentication with Key Recyling
arXiv:1610.09434
Abstract
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 revised version of our QCRYPT 2011 submission
References in corpus (13)
- Classical Communication Cost in Distributed Quantum Information Processing - A generalization of Quantum Communication Complexity
- Randomizing quantum states: Constructions and applications
- Optimal Encryption of Quantum Bits
- Authentication of Quantum Messages
- Oblivious remote state preparation
- Locking classical correlation in quantum states
- Locking of accessible information and implications for the security of quantum cryptography
- Key recycling in authentication
- On almost randomizing channels with a short Kraus decomposition
- How to reuse a one-time pad and other notes on authentication, encryption and protection of quantum information
- Quantum authentication with key recycling
- Approximate Randomization of Quantum States With Fewer Bits of Key
- New security notions and feasibility results for authentication of quantum data