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 Information and Computation

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

Ehsan Ebrahimi, Dominique Unruh

Published Dec 1, 2018• 2 citations
Publisher

Abstract

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.

DOI
10.26421/qic18.15-16-4

Related papers

Quantum Collision-Resistance of Non-Uniformly Distributed Functions.

Ehsan Ebrahimi, Gelo Noel M. Tabia, Dominique Unruh

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).

•Jan 1, 2016•1 citation

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

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

On Finding Quantum Multi-collisions.

Qipeng Liu, Mark Zhandry

A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, \(\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) \) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

•Jan 1, 2018•0 citations

On Finding Quantum Multi-collisions

Qipeng Liu, Mark Zhandry

A $k$-collision for a compressing hash function $H$ is a set of $k$ distinct inputs that all map to the same output. In this work, we show that for any constant $k$, $Θ\left(N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right)$ quantum queries are both necessary and sufficient to achieve a $k$-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

arXiv:1811.05385•Nov 13, 2018•2 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
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.
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.
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.
A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, Θ(N12(1−12k−1))\varTheta \left( N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) Θ(N21​(1−2k−11​)) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
A kkk-collision for a compressing hash function HHH is a set of kkk distinct inputs that all map to the same output. In this work, we show that for any constant kkk, Θ(N12(1−12k−1))Θ\left(N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right)Θ(N21​(1−2k−11​)) quantum queries are both necessary and sufficient to achieve a kkk-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.
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.