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.
The sponge is a cryptographic construction that turns a public permutation into a hash function. When the Keccak permutation is used, the resulting design constitutes the Secure Hash Algorithm 3 (SHA-3), standardized by the National Institute of Standards and Technology (NIST). SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption. While one can consider many security properties for the sponge, the ultimate one is indifferentiability from a random oracle, or simply indifferentiability. The sponge was proved indifferentiable against classical adversaries by Bertoni et al. in 2008. Despite significant efforts in the years since, little is known about sponge security against quantum adversaries, even for simple properties like preimage or collision resistance beyond a single round. This is primarily due to the lack of a satisfactory quantum analog of the lazy sampling technique for permutations. In this work, we develop a specialized technique that overcomes this barrier in the case of the sponge. We prove that the sponge is in fact indifferentiable from a random oracle against quantum adversaries. Our result establishes that the domain extension technique behind SHA-3 is secure in the post-quantum setting. Our indifferentiability bound for the sponge is a loose, but we also give bounds on preimage and collision resistance that are tighter.
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.
Most interesting cryptography happens in the computational realm where all parties can only perform efficient computations. On one hand, without this constraint many practically relevant cryptographic tasks are infeasible; on the other, this constraint still captures the power of any physical attacker with limited resources. Classically, if the task of attacking almost any interesting computational cryptography is provably hard, then we would also derive from it the existence of one-way functions, and thus P ≠ NP as well. Quantum mechanics offers a more complete model of physical information in the real world. Recent works have proved oracle separations (Kretschmer’21; Kretschmer, Qian, Sinha, Tal’23; Lombardi, Ma, Wright’23) suggesting that computationally secure quantum cryptography could exist even if P = NP, or in other words, that classical cryptography is infeasible. This hints at the possibility of constructing a quantum cryptosystem and establishing its security without unproven assumptions, liberating cryptographers from the perpetual cat-and-mousegame. In this dissertation, we make initial progress towards this goal by developing a theory of quantum computational cryptography without assuming the existence ofone-way functions. More specifically, we establish the following results: • We introduce a simple and natural quantum cryptographic primitive called EFI pairs, and prove its existential equivalence to various other quantum cryptographic primitives, including commitment schemes, oblivious transfer, and zero knowledge.• We establish the “minimality” of EFI pairs by showing that their existence is implied by many natural cryptographic primitives. EFI pairs thus appear easier to construct than other primitives. • We show that the existence of EFI pairs (and the existentially equivalent primitives) is robust by showing how to upgrade various notions of “weak” security to standard security without any additional assumption. • We finally construct commitment schemes, oblivious transfer, and zero knowledge unconditionally if a piece of quantum advice is allowed. In contrast, classical analogues of these are impossible without first settling P ≠ NP even if we allow randomized advice.
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.
The advancement of quantum computing poses emerging challenges to cryptographic hash functions that underpin modern cyber defense systems. In particular, Grover’s algorithm theoretically offers a quadratic speedup for preimage search, potentially reducing the effective security margin of hash-based primitives used to protect long-lived strategic data. This study adopts a structure-oriented perspective to analyze ARX-like and sponge-like hash constructions using Grover-based oracle modeling. Reversible toy hash abstractions are employed to construct quantum oracles and simulate Grover attacks under both ideal (noise-free) and Noisy Intermediate-Scale Quantum (NISQ) conditions. The analysis evaluates success probability, oracle cost, and noise sensitivity. Results show non-monotonic amplitude amplification under ideal conditions, with structural differences affecting phase behavior. However, under realistic noise, amplitude amplification is significantly attenuated for both constructions, limiting practical quantum advantage. The findings further show that oracle complexity, reflected in circuit depth and multi-qubit gate usage, plays a dominant role in determining attack feasibility beyond asymptotic complexity reductions. This work provides a structure-level framework for assessing quantum risks to cryptographic hash functions and supports informed post-quantum cyber defense planning.