Indifferentiability is an important cryptographic paradigm for analyzing the security of ideal objects—both in a classical and quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction to be “as good as” an ideal object. A paradigmatic application of the framework is showing that a hash function does not have structural weaknesses, by proving it to be indifferentiable from a random oracle. Despite its generality, indifferentiability is not known to offer security against pre-processing attacks, in which the adversary gains access to classical or quantum advice that is relevant to the particular construction. In this work, we show that indifferentiability is generically insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable with pre-computation from a random oracle. This yields the first, and tight, quantum space-time trade-offs for one-round sponge inversion.
Indifferentiability is an important cryptographic paradigm for analyzing the security of ideal objects—both in a classical and quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction to be “as good as” an ideal object. A paradigmatic application of the framework is showing that a hash function does not have structural weaknesses, by proving it to be indifferentiable from a random oracle. Despite its generality, indifferentiability is not known to offer security against pre-processing attacks, in which the adversary gains access to classical or quantum advice that is relevant to the particular construction. In this work, we show that indifferentiability is generically insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable with pre-computation from a random oracle. This yields the first, and tight, quantum space-time trade-offs for one-round sponge inversion.
Game-playing proofs constitute a powerful framework for non-quantum cryptographic security arguments, most notably applied in the context of indifferentiability. An essential ingredient in such proofs is lazy sampling of random primitives. We develop a quantum game-playing proof framework by generalizing two recently developed proof techniques. First, we describe how Zhandry's compressed quantum oracles~(Crypto'19) can be used to do quantum lazy sampling of a class of non-uniform function distributions. Second, we observe how Unruh's one-way-to-hiding lemma~(Eurocrypt'14) can also be applied to compressed oracles, providing a quantum counterpart to the fundamental lemma of game-playing. Subsequently, we use our game-playing framework to prove quantum indifferentiability of the sponge construction, assuming a random internal function.
Shor’s quantum factoring algorithm and a few other efficient quantum algorithms break many clas-sical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quan-tum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are “quantum-friendly”. We characterize sufficient conditions such that a classical reduction can be “lifted ” to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in [BDH11] carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [BDH11] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these results, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [Zha12b] and the simple hybrid arguments framework in [HSS11]) can be reformulated under our unified framework. 1
Shor's quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against \emph{quantum} attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as no-cloning. This work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are "quantum-friendly". We characterize sufficient conditions such that a classical reduction can be "lifted" to the quantum setting. We then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in~\cite{BDH11} carry over to the quantum setting. Namely, assuming existence of (classical) one-way functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in~\cite{BDH11} is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model~\cite{Zha12ibe} and the simple hybrid arguments framework in~\cite{HSS11}) can be reformulated under our unified framework.
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: — There are NP search problems solvable by quantum polynomial-time (QPT) machines but not classical probabilistic polynomial-time (PPT) machines. — There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar counterexamples exist for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the counterexample does not necessarily extend to the case of other cryptographic objects such as PRGs. — There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin. — Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction. By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.
In cryptography, generic transformations are often used to strengthen simpler but weaker schemes, into more sophisticated and stronger ones. This thesis aims to establish rigorous, provable notions of security for various such transformations that are relevant in the scope of post-quantum cryptography. We achieve this via formal mathematical proofs, and in some cases, via proposing new security definitions, when existing ones are inadequate. Most analyses are treated in an idealized setting known as the random oracle model.
The emergence of quantum computing has provided new paradigms for cryptography. On the one hand, it poses significant new threats to existing classically cryptographic systems, requiring the community to define new security models that capture what a quantum adversary can do. On the other hand, it gives us new tools to design cryptographic protocols, with weaker assumptions than in the classical world, or even protocols that are impossible classically. In this survey, we first give an overview of new security definitions for classical cryptography, considering quantum adversaries who can either only use local quantum computation (post-quantum security), or even send quantum messages and in particular have access to oracle in superposition (quantum security). We explore these new notions through the examples of commitments, zero-knowledge proofs, encryption, and signatures. Then, we present what is arguably the most famous application of quantum cryptography: quantum key distribution (QKD) protocols that take advantage of unique properties of quantum mechanics to provide secure communication unconditionally. We also explore cryptography beyond QKD, focusing on unclonable cryptography: a family of cryptographic functionalities, built with quantum states, and designed to be resistant to counterfeit by leveraging the “no-cloning” theorem. We examine in particular quantum money, but also the recent notions of unclonable encryption and copy-protection, including related variants. By presenting a comprehensive survey of these topics, this paper aims to provide a thorough understanding of the current landscape and future potential of quantum cryptography.