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
A Note on the Instantiability of the Quantum Random Oracle
In a highly influential paper from fifteen years ago [10], Canetti, Goldreich, and Halevi showed a fundamental separation between the Random Oracle Model (ROM) and the standard model. They constructed a signature scheme which can be proven secure in the ROM, but is insecure when instantiated with any hash function (and thus insecure in the standard model). In 2011, Boneh et al. defined the notion of the Quantum Random Oracle Model (QROM), where queries to the random oracle may be made in quantum superposition. Because the QROM generalizes the ROM, a proof of security in the QROM is stronger than one in the ROM. This leaves open the possibility that security in the QROM could imply security in the standard model.
In this work, we show that this is not the case, and that security in the QROM cannot imply standardmodel security. We do this by showing that the original schemes that show a separation between the standard model and the ROM are also secure in the QROM. We consider two schemes that establish such a separation, one with lengthrestricted messages, and one without, and show both to be secure in the QROM. Our results give further understanding to the landscape of proofs in the ROM versus the QROM or standard model, and point towards the QROM and ROM being much closer to each other than either is to standard model security.
more »
« less
 Award ID(s):
 1901624
 NSFPAR ID:
 10164364
 Date Published:
 Journal Name:
 PostQuantum Cryptography. PQCrypto 2020. Lecture Notes in Computer Science
 Volume:
 12100
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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

The quantum random oracle model (QROM) has become the standard model in which to prove the postquantum security of randomoraclebased constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary’s queries, a crucial feature of many classical ROM proofs, including all proofs of indifferentiability for hash function domain extension. In this work, we give a new QROM proof technique that overcomes this “recording barrier”. We do so by giving a new “compressed oracle” which allows for efficient onthefly simulation of random oracles, roughly analogous to the usual classical simulation. We then use this new technique to give the first proof of quantum indifferentiability for the MerkleDamgård domain extender for hash functions. We also give a proof of security for the FujisakiOkamoto transformation; previous proofs required modifying the scheme to include an additional hash term. Given the threat posed by quantum computers and the push toward quantumresistant cryptosystems, our work represents an important tool for efficient postquantum cryptosystems.more » « less

We give an attributebased encryption system for Turing Machines that is provably secure assuming only the existence of identitybased encryption (IBE) for large identity spaces. Currently, IBE is known to be realizable from most mainstream number theoretic assumptions that imply public key cryptography including factoring, the search DiffieHellman assumption, and the Learning with Errors assumption. Our core construction provides security against an attacker that makes a single key query for a machine before declaring a challenge string that is associated with the challenge ciphertext. We build our construction by leveraging a Garbled RAM construction of Gentry, Halevi, Raykova, and Wichs; however, to prove security we need to introduce a new notion of security called iterated simulation security. We then show how to transform our core construction into one that is secure for an apriori bounded number of key queries that can occur either before or after the challenge ciphertext. We do this by first showing how one can use a special type of noncommitting encryption to transform a system that is secure only if a single key is chosen before the challenge ciphertext is declared into one where the single key can be requested either before or after the challenge ciphertext. We give a simple construction of this noncommitting encryption from public key encryption in the Random Oracle Model. Next, one can apply standard combinatorial techniques to lift from singlekey adaptive security to key adaptive security.more » « less

Abstract We discuss quantum position verification (QPV) protocols in which the verifiers create and send singlequbit states to the prover. QPV protocols using singlequbit states are known to be insecure against adversaries that share a small number of entangled qubits. We introduce QPV protocols that are practically secure: they only require singlequbit states from each of the verifiers, yet their security is broken if the adversaries sharing an impractically large number of entangled qubits employ teleportationbased attacks. These protocols are a modification of known QPV protocols in which we include a classical random oracle without altering the amount of quantum resources needed by the verifiers. We present a cheating strategy that requires a number of entangled qubits shared among the adversaries that grows exponentially with the size of the classical input of the random oracle.more » « less