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

Quantum Collision-Resistance of Non-Uniformly Distributed Functions.

Ehsan Ebrahimi, Gelo Noel M. Tabia, Dominique Unruh

Published Jan 1, 2016• 1 citation
OpenAlex

Abstract

We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a distribution with min-entropy k. We prove that Ω(2) quantum queries are necessary to find a collision for function f . This is needed in some security proofs in the quantum random oracle model (e.g. Fujisaki-Okamoto transform).

Related papers

Quantum collision-resistance of non-uniformly distributed functions: upper and lower bounds

Ehsan Ebrahimi, Dominique Unruh

We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a non-uniform distribution D. We derive some upper bounds and lower bounds depending on the min-entropy and the collision-entropy of D. In particular, we improve the previous lower bound by Ebrahimi Targhi et al. from \Omega(2^{k/9}) to \Omega(2^{k/5}) where k is the min-entropy of D.

Quantum Information and Computation•Dec 1, 2018•2 citations

An Improved Lower Bound for the Quantum Query Complexity of Collision Finding in Hash Functions with Non-Uniformly Distributed Images

Marko Balogh

This work proves an improved lower bound for the quantum query complexity of collision- finding in hash functions whose images are distributed according to a non-uniform distribution. Recent work by [TTU16] applied the leftover hash lemma to show that at least Omega(2k/9) quantum queries are necessary to find a collision when the image distribution has min-entropy k. In comparison, a result by [Zha15] implies that Omega(2k/3) quantum queries are necessary if the distribution is uniform. In this paper the lower bound complexity of [Zha15] is extended directly to the non-uniform case using a chain of reductions which convert collisions in min-entropy k distributions into collisions in the uniform distribution with constant probability. This result shows a minimum security guarantee for hash functions under more general assumptions in which the image distribution may not be uniform.

•May 26, 2017•0 citations

Quantum Lower Bounds for Collision Problems

Pan Peng, Jingyu Wu

We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ and every feasible alphabet size $q\ge n/k$. The lower bounds are $Ω_k(n^{1/2-1/(2(2^k-1))})$ for unrestricted adaptive algorithms and $Ω_k(n^{1-1/k})$ for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound $Ω_k(\sqrt{n/k})$ for $k$-to-one Testing when $q\ge n$, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.

quant-pharXiv:2611.01767•Nov 3, 2026•0 citations

On finding quantum multi-collisions in non-uniform random functions

Tianci Peng, Rui Xue

Abstract Collision resistance is one of the most fundamental properties in cryptography. With the development of quantum computing, significant attention has been directed toward understanding the quantum query complexity of collision-finding problems in hash functions. The quantum query complexity of collision-finding in general non-uniform random functions remained an open problem until the recent work of Peng et al. (ASIACRYPT 2025), who nearly resolved it by introducing a novel parameter $$\gamma$$ γ . Based on this parameter, they established an upper bound of $$O(\gamma ^{1/6})$$ O ( γ 1 / 6 ) and a matching lower bound of $$\tilde{\Omega }(\gamma ^{1/6})$$ Ω ~ ( γ 1 / 6 ) . However, the quantum query complexity of finding multi-collisions in non-uniform random functions has remained open. A s -collision to a function f is a set of distinct input $$x_1,\dots , x_s$$ x 1 , ⋯ , x s such that $$f(x_1)=f(x_2)\dots =f(x_s)$$ f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter $$\gamma _s$$ γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of $$O(\gamma _s)$$ O ( γ s ) and a lower bound of $$\tilde{\Omega }(\gamma _s)$$ Ω ~ ( γ s ) —thereby nearly resolving this open problem. Moreover, although the existing results for 2-collisions do not generalize straightforwardly to the case of s -collision ( $$s>2$$ s > 2 ), we demonstrate that the result of Peng et al. can be viewed as a special case of our more general framework. This clearly establishes our work as a direct generalization of their contribution.

Cybersecurity•May 8, 2026•0 citations

Quantum Collision Resistance of Double-Block-Length Hashing

Shoichi Hirose, Hidenori KUWAKADO

In 2005, Nandi introduced a class of double-block-length compression functions hπ (x) := (h(x) , h( π(x) ) ), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of hπ is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of hπ and the Merkle-Damåard hash function using hπ in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of hπ may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for hπ with only O(2n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of hπ. This condition states that any collision attack needs Ω(22n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry's compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using hπ can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 3, 2024•1 citation

A note on the quantum collision and set equality problems

Mark Zhandry

A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

arXiv:1312.1027•Quantum Information and Computation•May 1, 2015•138 citations
We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a distribution with min-entropy k. We prove that Ω(2) quantum queries are necessary to find a collision for function f . This is needed in some security proofs in the quantum random oracle model (e.g. Fujisaki-Okamoto transform).
This work proves an improved lower bound for the quantum query complexity of collision- finding in hash functions whose images are distributed according to a non-uniform distribution. Recent work by [TTU16] applied the leftover hash lemma to show that at least Omega(2k/9) quantum queries are necessary to find a collision when the image distribution has min-entropy k. In comparison, a result by [Zha15] implies that Omega(2k/3) quantum queries are necessary if the distribution is uniform. In this paper the lower bound complexity of [Zha15] is extended directly to the non-uniform case using a chain of reductions which convert collisions in min-entropy k distributions into collisions in the uniform distribution with constant probability. This result shows a minimum security guarantee for hash functions under more general assumptions in which the image distribution may not be uniform.
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised kkk-to-one Finding on an exactly kkk-to-one input string x∈Zqnx\in\mathbb Z_q^nx∈Zqn​, for every fixed k≥2k\ge2k≥2 and every feasible alphabet size q≥n/kq\ge n/kq≥n/k. The lower bounds are Ωk(n1/2−1/(2(2k−1)))Ω_k(n^{1/2-1/(2(2^k-1))})Ωk​(n1/2−1/(2(2k−1))) for unrestricted adaptive algorithms and Ωk(n1−1/k)Ω_k(n^{1-1/k})Ωk​(n1−1/k) for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound Ωk(n/k)Ω_k(\sqrt{n/k})Ωk​(n/k​) for kkk-to-one Testing when q≥nq\ge nq≥n, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
Abstract Collision resistance is one of the most fundamental properties in cryptography. With the development of quantum computing, significant attention has been directed toward understanding the quantum query complexity of collision-finding problems in hash functions. The quantum query complexity of collision-finding in general non-uniform random functions remained an open problem until the recent work of Peng et al. (ASIACRYPT 2025), who nearly resolved it by introducing a novel parameter γ\gammaγ γ . Based on this parameter, they established an upper bound of O(γ1/6)O(\gamma ^{1/6})O(γ1/6) O ( γ 1 / 6 ) and a matching lower bound of Ω~(γ1/6)\tilde{\Omega }(\gamma ^{1/6})Ω~(γ1/6) Ω ~ ( γ 1 / 6 ) . However, the quantum query complexity of finding multi-collisions in non-uniform random functions has remained open. A s -collision to a function f is a set of distinct input x1,…,xsx_1,\dots , x_sx1​,…,xs​ x 1 , ⋯ , x s such that f(x1)=f(x2)⋯=f(xs)f(x_1)=f(x_2)\dots =f(x_s)f(x1​)=f(x2​)⋯=f(xs​) f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter γs\gamma _sγs​ γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of O(γs)O(\gamma _s)O(γs​) O ( γ s ) and a lower bound of Ω~(γs)\tilde{\Omega }(\gamma _s)Ω~(γs​) Ω ~ ( γ s ) —thereby nearly resolving this open problem. Moreover, although the existing results for 2-collisions do not generalize straightforwardly to the case of s -collision ( s>2s>2s>2 s > 2 ), we demonstrate that the result of Peng et al. can be viewed as a special case of our more general framework. This clearly establishes our work as a direct generalization of their contribution.
In 2005, Nandi introduced a class of double-block-length compression functions hπ (x) := (h(x) , h( π(x) ) ), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of hπ is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of hπ and the Merkle-Damåard hash function using hπ in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of hπ may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for hπ with only O(2n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of hπ. This condition states that any collision attack needs Ω(22n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry's compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using hπ can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.
A collision for a function fff is two distinct inputs x1≠x2x_1\neq x_2x1​=x2​ such that fff outputs the same value on both inputs: f(x1)=f(x2)f(x_1)=f(x_2)f(x1​)=f(x2​). The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be Θ(N1/3)\Theta(N^{1/3})Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3)\Omega(N^{1/3})Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to rrr-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of Θ(N1/3)\Theta(N^{1/3})Θ(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal Ω(M1/3)\Omega(M^{1/3})Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.