We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i) ciphertext unforgeability, (ii) indistinguishability under adaptive chosen-ciphertext attack, and (iii) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies ( INT - CTXT ), (ii) implies ( IND - CCA2 ), and (iii) implies ( AE ). All of our new notions also imply ( QIND - CPA ) privacy. Combining one-time authentication and classical pseudorandomness, we construct symmetric-key quantum encryption schemes for each of these new security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.
@cite_18: 
@cite_25: 
@cite_22: We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) as well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds.
@cite_7: We introduce the notion of nonmalleability of a quantum state encryption scheme (in dimension d): in addition to the requirement that an adversary cannot learn information about the state, here we demand that no controlled modification of the encrypted state can be effected. We show that such a scheme is equivalent to a unitary 2-design [Dankert, et al, e-print arXiv:quant-ph 0606161], as opposed to normal encryption which is a unitary 1-design. Our other main results include a new proof of the lower bound of (d2−1)2+1 on the number of unitaries in a 2-design [Gross, et al, J. Math. Phys. 48, 052104 (2007)], which lends itself to a generalization to approximate 2-design. Furthermore, while in prime power dimension there is a unitary 2-design with ≤d5 elements, we show that there are always approximate 2-designs with O(ϵ−2d4 log d) elements.
@cite_28: 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.
@cite_21: Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting. In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.
@cite_24: Quantum message authentication codes are families of keyed encoding and decoding maps that enable the detection of tampering on encoded quantum data. Here, we study a new class of simulators for quantum message authentication schemes, and show how they are applied in the context of two codes: the Clifford and the trap code. Our results show for the first time that these codes admit an efficient simulation (assuming that the adversary is efficient). Such efficient simulation is typically crucial in order to establish a composable notion of security.
@cite_27: We provide the first two-party protocol allowing Alice and Bob to evaluate privately even against active adversaries any completely positive, trace-preserving map @math @math , given as a quantum circuit, upon their joint quantum input state @math . Our protocol leaks no more to any active adversary than an ideal functionality for @math provided Alice and Bob have the cryptographic resources for active secure two-party classical computation. Our protocol is constructed from the protocol for the same task secure against specious adversaries presented in [4].
@cite_2: We show that a family of quantum authentication protocols introduced in [, FOCS 2002] can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this family of protocols, i.e., there exists an adversarial strategy to obtain all non-recycled bits. Previous works recycled less key and only gave partial security proofs, since they did not consider all possible distinguishers (environments) that may be used to distinguish the real setting from the ideal secure quantum channel and secret key resource.
@cite_12: 
@cite_20: 
@cite_11: Fully homomorphic encryption is an encryption method with the property that any computation on the plaintext can be performed by a party having access to the ciphertext only. Here, we formally define and give schemes for quantum homomorphic encryption, which is the encryption of quantum information such that quantum computations can be performed given the ciphertext only. Our schemes allow for arbitrary Clifford group gates, but become inefficient for circuits with large complexity, measured in terms of the non-Clifford portion of the circuit (we use the “ ( 8 )” non-Clifford group gate, also known as the ( T )-gate).
Computationally-secure quantum encryption has garnered significant interest in the past few years, beginning with basic security notions like and @cite_11 @cite_21 , and then with more advanced concepts such as quantum fully-homomorphic encryption (QFHE) @cite_11 @cite_20 . For authentication, uncloneability, and non-malleability, the one-time setting has received considerable attention (see, e.g., @cite_7 @cite_27 @cite_28 @cite_22 @cite_18 @cite_24 @cite_2 @cite_12 .) We will make use of the authentication definition of @cite_27 , a characterization lemma of @cite_18 , and a simulation adversary of @cite_24 . For classical notions of unforgeability and chosen-ciphertext security, see e.g. @cite_25 .