Quantum Information and Computation

A note on the quantum collision and set equality problems

ZhandryMark

Published May 1, 2015• 4 citations

Abstract

A collision for a function f is two distinct inputs x1 ≠ x2 such that f outputs the same value on both inputs: f(x1) = f(x2). The quantum query complexity of finding collisions has been shown [9, 2...

DOI: 10.5555/2871411.2871413

Related papers

A note on the quantum collision and set equality problems

Mark Zhandry

arXiv:1312.1027Quantum Information and ComputationMay 1, 201599 citations

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

Tianci Peng, Rui Xue

CybersecurityMay 8, 20260 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, 20180 citations

On Finding Quantum Multi-collisions

Qipeng Liu, Mark Zhandry

arXiv:1811.05385Nov 13, 20180 citations

Quantum lower bounds for the collision and the element distinctness problems

Yaoyun Shi

arXiv:quant-ph/0112086Annual Symposium on Foundations of Computer ScienceJun 26, 2003100 citations

Adversary lower bounds for the collision and the set equality problems

BelovsAleksandrs, RosmanisAnsis

We prove tight Ω(n1/3) lower bounds on the quantum query complexity of the Collision and the SET EQUALITY problems, provided that the size of the alphabet is large enough. We do this using the nega...

Quantum Information and ComputationMar 1, 20180 citations

Quantum Information and Computation

A note on the quantum collision and set equality problems

ZhandryMark

Published May 1, 2015• 4 citations

Publisher

Abstract

DOI: 10.5555/2871411.2871413

Related papers

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.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.1027Quantum Information and ComputationMay 1, 201599 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.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.

CybersecurityMay 8, 20260 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.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, 20180 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.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.05385Nov 13, 20180 citations

Quantum lower bounds for the collision and the element distinctness problems

Yaoyun Shi

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).

arXiv:quant-ph/0112086Annual Symposium on Foundations of Computer ScienceJun 26, 2003100 citations

Adversary lower bounds for the collision and the set equality problems

BelovsAleksandrs, RosmanisAnsis

Quantum Information and ComputationMar 1, 20180 citations

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.

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

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.

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.