Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Parallel Quantum Pebbling: Analyzing the Post-Quantum Security of iMHFs.

Jeremiah Blocki, Seunghoon Lee

Published Oct 8, 2021• 0 citations
OpenAlex

Abstract

The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum attacker running Grover's algorithm only requires $\mathcal{O}(\sqrt{m})$ blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function $f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for the graph $G$ does not necessarily imply the existence of a quantum circuit with comparable complexity -- in contrast to the classical setting where any efficient pebbling strategy for $G$ corresponds to an algorithm with comparable complexity evaluating $f_{G,H}$. Motivated by this observation we introduce a new (parallel) quantum pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new quantum pebbling game to analyze the quantum space-time complexity of several important graphs: the line graph, Argon2i-A, Argon2i-B, and DRSample. (See the paper for the full abstract.)

Related papers

Quantum Hashing: A Theoretical Framework for Post-Quantum Secure Data Structures

Pulkit Sharma

The rapid advancement of quantum computing presents a fundamental challenge to modern cryptographic security, particularly in the domain of hash functions that ensure data integrity, authentication, and blockchain security. Traditional crypto graphic hash functions such as SHA-256, SHA-3, and BLAKE2 rely on computational hardness assumptions that become obsolete in the presence of large-scale quantum computers. Shor’s algorithm can efficiently break RSA and ECC-based cryptosys tems, while Grover’s algorithm reduces the security of traditional hash functions by square root complexity, significantly weakening their preimage and collision resistance. This quantum threat necessitates the development of post-quantum secure hashing techniques that remain resilient against both classical and quantum adversaries. This paper proposes Quantum Hashing, a novel cryptographic framework that integrates quantum entanglement, lattice-based cryptography, and hybrid quantum classical hashing to construct post-quantum secure hash functions. We introduce a formal model for Quantum Collision Resistance (QCR) and provide entropy-based ran domness enhancement to ensure unpredictable hash outputs. Unlike classical hashing approaches, our framework leverages the hardness of lattice problems (e.g., Shortest Vector Problem, Learning with Errors) to withstand quantum attacks while incorpo rating Quantum Key Distribution (QKD) mechanisms to enhance entropy and key management. Furthermore, we evaluate the security of Quantum Hashing under various attack models, comparing its resistance against Grover’s search and collision attacks. We benchmark its performance against NIST Post-Quantum Cryptography (PQC) final ists, including CRYSTALS-DILITHIUM, SPHINCS+, and Falcon, demonstrating that our approach offers superior resilience while maintaining computational feasibility. Additionally, we present an implementation of Quantum Hashing using Qiskit, show casing its practical applicability in quantum circuits and quantum-secure blockchain architectures. Our findings highlight that Quantum Hashing provides a scalable, entropy-efficient, and post-quantum resilient cryptographic primitive suitable for next-generation cryptographic applications. This work paves the way for secure post-quantum digital signatures, blockchain consensus mechanisms, and zero-knowledge proof systems that require tamper-resistant hashing in a quantum computing era.

•Apr 9, 2025•0 citations

A Note on Quantum Security for Post-Quantum Cryptography.

Fang Song

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

•Jan 1, 2014•0 citations

On quantum preimage attacks

Răzvan Roşie

We propose a preimage attack against cryptographic hash functions based on the speedup enabled by quantum computing. Preimage resistance is a fundamental property cryptographic hash functions must possess. The motivation behind this work relies in the lack of conventional attacks against newly introduced hash schemes such as the recently elected SHA-3 standard. The proposed algorithm consists of two parts: a classical one running in O(log |S|), where S represents the searched space, and a quantum part that contains the bulk of the Deutsch-Jozsa circuit. The mixed approach we follow makes use of the quantum parallelism concept to check the existence of an argument (preimage) for a given hash value (image) in the preestablished search space. For this purpose, we explain how a non-unitary measurement gate can be used to determine if S contains the target value. Our method is entirely theoretical and is based on the assumptions that a hash function can be implemented by a quantum computer and the key measurement gate we describe is physically realizable. Finally, we present how the algorithm finds a solution on S.

arXiv:1412.3164•Dec 10, 2014•0 citations

Computational Bounds for fff-Routing

Oren Renard, Nicholas Spooner

The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers; our new techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and sufficiently small constant $ε>0$, a uniformly generated strategy using $q$ qubits and having description length $\mathrm{poly}(q)$, with success probability at least $1-ε$ on every input, implies the following computational bounds on $f$: 1. If the strategies are arbitrary quantum channels, then $f\in\mathrm{QSZK}(\mathrm{poly}(nq))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero knowledge proofs in which the verifier runs in time $T$ (and the simulator in time $\mathrm{poly}(T)$). 2. If the strategies are explicit Pauli-sparse unitaries on $q$ qubits that have at most $s$ nonzero Pauli coefficients, then $f\in\mathrm{DTIME}(\mathrm{poly}(nqs))$. 3. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in\mathrm{DTIME}(\mathrm{poly}(nq2^t))$. Time and space hierarchies then yield explicit functions secure against polynomial and even quasipolynomial qubits $q$ under our computational restrictions. These bounds exceed the $q\le\log n$ bound of Bluhm, Christandl, and Speelman (2022) for inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.

quant-pharXiv:2609.40278•Oct 1, 2026•0 citations

Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes

Vlad Gheorghiu, Michele Mosca

Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.

arXiv:1902.02332•Feb 6, 2019•28 citations

Post-Quantum Multi-Party Computation

Agarwal, Amit, James Bartusek, Vipul Goyal +2 more

We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.

arXiv:2005.12904•May 23, 2020•1 citation
The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function fff with a static data-dependency graph GGG. Of particular interest in the field of cryptography are data-independent memory-hard functions fG,Hf_{G,H}fG,H​ which are defined by a directed acyclic graph (DAG) GGG and a cryptographic hash function HHH. The pebbling complexity of the graph GGG characterizes the amortized cost of evaluating fG,Hf_{G,H}fG,H​ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain X\mathcal{X}X, i.e., given y∈{0,1}∗y \in \{0,1\}^*y∈{0,1}∗ find x∈Xx \in \mathcal{X}x∈X such that fG,H(x)=yf_{G,H}(x)=yfG,H​(x)=y. While a classical attacker will need to evaluate the function fG,Hf_{G,H}fG,H​ at least m=∣X∣m=|\mathcal{X}|m=∣X∣ times a quantum attacker running Grover's algorithm only requires O(m)\mathcal{O}(\sqrt{m})O(m​) blackbox calls to a quantum circuit CG,HC_{G,H}CG,H​ evaluating the function fG,Hf_{G,H}fG,H​. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit CG,HC_{G,H}CG,H​. We first observe that a legal black pebbling strategy for the graph GGG does not necessarily imply the existence of a quantum circuit with comparable complexity -- in contrast to the classical setting where any efficient pebbling strategy for GGG corresponds to an algorithm with comparable complexity evaluating fG,Hf_{G,H}fG,H​. Motivated by this observation we introduce a new (parallel) quantum pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new quantum pebbling game to analyze the quantum space-time complexity of several important graphs: the line graph, Argon2i-A, Argon2i-B, and DRSample. (See the paper for the full abstract.)
The rapid advancement of quantum computing presents a fundamental challenge to modern cryptographic security, particularly in the domain of hash functions that ensure data integrity, authentication, and blockchain security. Traditional crypto graphic hash functions such as SHA-256, SHA-3, and BLAKE2 rely on computational hardness assumptions that become obsolete in the presence of large-scale quantum computers. Shor’s algorithm can efficiently break RSA and ECC-based cryptosys tems, while Grover’s algorithm reduces the security of traditional hash functions by square root complexity, significantly weakening their preimage and collision resistance. This quantum threat necessitates the development of post-quantum secure hashing techniques that remain resilient against both classical and quantum adversaries. This paper proposes Quantum Hashing, a novel cryptographic framework that integrates quantum entanglement, lattice-based cryptography, and hybrid quantum classical hashing to construct post-quantum secure hash functions. We introduce a formal model for Quantum Collision Resistance (QCR) and provide entropy-based ran domness enhancement to ensure unpredictable hash outputs. Unlike classical hashing approaches, our framework leverages the hardness of lattice problems (e.g., Shortest Vector Problem, Learning with Errors) to withstand quantum attacks while incorpo rating Quantum Key Distribution (QKD) mechanisms to enhance entropy and key management. Furthermore, we evaluate the security of Quantum Hashing under various attack models, comparing its resistance against Grover’s search and collision attacks. We benchmark its performance against NIST Post-Quantum Cryptography (PQC) final ists, including CRYSTALS-DILITHIUM, SPHINCS+, and Falcon, demonstrating that our approach offers superior resilience while maintaining computational feasibility. Additionally, we present an implementation of Quantum Hashing using Qiskit, show casing its practical applicability in quantum circuits and quantum-secure blockchain architectures. Our findings highlight that Quantum Hashing provides a scalable, entropy-efficient, and post-quantum resilient cryptographic primitive suitable for next-generation cryptographic applications. This work paves the way for secure post-quantum digital signatures, blockchain consensus mechanisms, and zero-knowledge proof systems that require tamper-resistant hashing in a quantum computing era.
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
We propose a preimage attack against cryptographic hash functions based on the speedup enabled by quantum computing. Preimage resistance is a fundamental property cryptographic hash functions must possess. The motivation behind this work relies in the lack of conventional attacks against newly introduced hash schemes such as the recently elected SHA-3 standard. The proposed algorithm consists of two parts: a classical one running in O(log |S|), where S represents the searched space, and a quantum part that contains the bulk of the Deutsch-Jozsa circuit. The mixed approach we follow makes use of the quantum parallelism concept to check the existence of an argument (preimage) for a given hash value (image) in the preestablished search space. For this purpose, we explain how a non-unitary measurement gate can be used to determine if S contains the target value. Our method is entirely theoretical and is based on the assumptions that a hash function can be implemented by a quantum computer and the key measurement gate we describe is physically realizable. Finally, we present how the algorithm finds a solution on S.
The fff-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers; our new techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length nnn and sufficiently small constant ε>0ε>0ε>0, a uniformly generated strategy using qqq qubits and having description length poly(q)\mathrm{poly}(q)poly(q), with success probability at least 1−ε1-ε1−ε on every input, implies the following computational bounds on fff: 1. If the strategies are arbitrary quantum channels, then f∈QSZK(poly(nq))f\in\mathrm{QSZK}(\mathrm{poly}(nq))f∈QSZK(poly(nq)), where QSZK(T)\mathrm{QSZK}(T)QSZK(T) is the class of languages having quantum statistical zero knowledge proofs in which the verifier runs in time TTT (and the simulator in time poly(T)\mathrm{poly}(T)poly(T)). 2. If the strategies are explicit Pauli-sparse unitaries on qqq qubits that have at most sss nonzero Pauli coefficients, then f∈DTIME(poly(nqs))f\in\mathrm{DTIME}(\mathrm{poly}(nqs))f∈DTIME(poly(nqs)). 3. If the strategies are Clifford+T circuits using at most ttt magic gates, then f∈DTIME(poly(nq2t))f\in\mathrm{DTIME}(\mathrm{poly}(nq2^t))f∈DTIME(poly(nq2t)). Time and space hierarchies then yield explicit functions secure against polynomial and even quasipolynomial qubits qqq under our computational restrictions. These bounds exceed the q≤log⁡nq\le\log nq≤logn bound of Bluhm, Christandl, and Speelman (2022) for inner product function f=IPf=\mathrm{IP}f=IP, at the cost of restricting adversarial computation and increasing honest evaluation complexity.
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.
We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.