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 nocloning. 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 chosenciphertext 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 INTCTXT , (ii) implies INDCCA2 , and (iii) implies AE . All of our new notions also imply QINDCPA privacy. Combining onetime authentication and classical pseudorandomness, we construct symmetrickey 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 onetime quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.
more »
« less
QuantumAccessSecure Message Authentication via BlindUnforgeability
Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition.
We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUFCMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantumquerysecure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hashandMAC” paradigm and the Lamport onetime digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantumsecure hash functions called Bernoullipreserving.
Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.
more »
« less
 NSFPAR ID:
 10164363
 Date Published:
 Journal Name:
 Advances in Cryptology – EUROCRYPT 2020
 Volume:
 12107
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Largescale quantum computing is a significant threat to classical publickey cryptography. In strong "quantum access" security models, numerous symmetrickey cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to nonadaptive (i.e., prechallenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum randomaccess codes, we show that the standard PRF and PRPbased encryption schemes are QCCA1secure when instantiated with quantumsecure primitives. We then revisit standard INDCPAsecure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (largemodulus version of) the wellknown BernsteinVazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., postquantum chosenplaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosenciphertext attacks (e.g., as a result of deployment in an inappropriate realworld setting) then quantum attacks are even more devastating than classical ones.more » « less

Public key quantum money can be seen as a version of the quantum nocloning theorem that holds even when the quantum states can be verified by the adversary. In this work, we investigate quantum lightning where nocloning holds even when the adversary herself gener ates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results: – We demonstrate the usefulness of quantum lightning beyond quan tum money by showing several potential applications, such as gen erating random strings with a proof of entropy, to completely decen tralized cryptocurrency without a blockchain, where transactions is instant and local. – We give Either/Or results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quan tum money or lightning. Given the difficulty in constructing public key quantum money, this suggests that natural schemes do attain strong security guarantees. – We show that instantiating the quantum money scheme of Aaron son and Christiano [STOC’12] with indistinguishability obfuscation that is secure against quantum computers yields a secure quantum money scheme. This construction can be seen as an instance of our Either/Or result for signatures, giving the first separation between two security notions for signatures from the literature. – Finally, we give a plausible construction for quantum lightning, which we prove secure under an assumption related to the multi collision resistance of degree2 hash functions. Our construction is inspired by our Either/Or result for hash functions, and yields the first plausible standard model instantiation of a noncollapsing col lision resistant hash function. This improves on a result of Unruh [Eurocrypt’16] which is relative to a quantum oracle.more » « less

A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multisolution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an averagecase unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique of Zhandry (Crypto'19). As an application, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, the Bitcoin backbone (Eurocrypt'15), against quantum adversaries, while honest parties are classical and show that protocol's security holds under a quantum analogue of the classical “honest majority'' assumption. Our analysis indicates that the security of Bitcoin backbone is guaranteed provided the number of adversarial quantum queries is bounded so that each quantum query is worth O ( p − 1 / 2 ) classical ones, where p is the success probability of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.more » « less

Formulating cryptographic definitions to protect against software piracy is an important research direction that has not received much attention. Since natural definitions using classical cryptography are impossible to achieve (as classical programs can always be copied), this directs us towards using techniques from quantum computing. The seminal work of Aaronson [CCC'09] introduced the notion of quantum copyprotection precisely to address the problem of software antipiracy. However, despite being one of the most important problems in quantum cryptography, there are no provably secure solutions of quantum copyprotection known for {\em any} class of functions. We formulate an alternative definition for tackling software piracy, called quantum secure software leasing (QSSL). While weaker than quantum copyprotection, QSSL is still meaningful and has interesting applications in software antipiracy. We present a construction of QSSL for a subclass of evasive circuits (that includes natural implementations of point functions, conjunctions with wild cards, and affine testers) based on concrete cryptographic assumptions. Our construction is the first provably secure solution, based on concrete cryptographic assumptions, for software antipiracy. To complement our positive result, we show, based on cryptographic assumptions, that there is a class of quantum unlearnable functions for which QSSL does not exist. In particular, our impossibility result also rules out quantum copyprotection [Aaronson CCC'09] for an arbitrary class of quantum unlearnable functions; resolving an important open problem on the possibility of constructing copyprotection for arbitrary quantum unlearnable circuits.more » « less