PaperlayerView exact revision on arXiv

Source-linked AI summary

A Note on the Quantum Collision and Set Equality Problems

Mark Zhandry

arXiv:1312.1027v3cs.CCquant-ph

TL;DR

Prior bounds largely concern r-to-1 functions and require equal domain and codomain sizes, while random functions and cryptographically relevant smaller codomains fall outside those conditions. The paper uses Ambainis’s algorithm for an upper bound and distribution-distinguishing arguments, including a decomposition into smaller-range functions, for a lower bound. For random functions with M = Ω(N^1/2), collision finding with constant probability has quantum query complexity Θ(N^1/3).

  • Problem

    Prior bounds largely concern r-to-1 functions and require equal domain and codomain sizes, while random functions and cryptographically relevant smaller codomains fall outside those conditions.

    Source: §1 · pp. 2–3

  • Method

    The paper uses Ambainis’s algorithm for an upper bound and distribution-distinguishing arguments, including a decomposition into smaller-range functions, for a lower bound.

    Source: §2 · p. 4, §3 · p. 5, §3.3 · p. 8

  • Results

    For random functions with M = Ω(N^1/2), collision finding with constant probability has quantum query complexity Θ(N^1/3).

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    Characterizing collision difficulty for random functions informs understanding of the security of schemes that use hash functions.

    Source: §1 · p. 3

    Prior lower-bound approaches require equal domain and codomain sizes and do not directly apply to random functions, which are generally not r-to-one.

    Source: §1 · p. 2

Abstract

from arXiv · show

The results showing a quantum query complexity of $\Theta(N^{1/3})$ for the collision problem do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the range is no larger than the 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 range 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(N^{1/3})$ lower bound for the set equality problem. This new lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

1 Introduction

Prior quantum collision bounds focused on r-to-1 functions and equal domain and codomain sizes, leaving random functions and cryptographically relevant parameter ranges insufficiently covered. This work establishes tight collision bounds for random functions across sensible sizes and an optimal lower bound for set equality.

1 Introduction

  • Earlier bounds focused on r-to-1 functions, which random functions are not with overwhelming probability, and therefore do not directly apply.Random functions can have outputs with one preimage or many preimages.Source: §1 · pp. 1–2
  • Existing lower-bound approaches require the domain and codomain to be equal, while random-function collision questions also arise when the codomain is much smaller.Those approaches distinguish a two-to-one function from a permutation.Source: §1 · p. 2
  • For random functions, collision finding and element distinctness essentially coincide when N is quadratic in M, since injectivity and having a collision each occur with constant probability.A collision then distinguishes an injective function from one with a collision.Source: §1 · p. 2
  • The question matters for cryptographic hash functions, whose collision resistance is a main security requirement and whose domains may greatly exceed their codomains.Characterizing random-function collision difficulty informs the security of schemes that use hash functions.Source: §1 · pp. 2–3

1.1 This work

  • For random functions with M = Ω(N^1/2), finding a collision with constant probability requires and suffices with Θ(N^1/3) quantum queries.When M = o(N^1/2), collisions occur with probability approaching zero, so the problem becomes meaningless.Source: §1.1 · p. 3
  • The paper proves an Ω(N^1/3) lower bound for distinguishing identical from disjoint ranges of random injective functions in the set equality problem.The functions have domain [N], codomain [M] with M ≥ 2N, and the result improves the previously known Ω(N^1/5/log N) lower bound.Source: §1.1 · p. 3, §1 · p. 3
  • The set equality lower bound yields D(f) = ˜O(Q(f)^7) for every permutation-symmetric function f.The prior relationship was D(f) = ˜O(Q(f)^9), with logarithmic factors hidden.Source: §1.1 · p. 3, §1 · p. 3
  • The lower-bound proof improves Yuen’s random-function result beyond equal domain and codomain sizes using a different technique based on Zhandry’s distribution-distinguishing lemma.It first handles M ≤ N, extends to M = 2N, then decomposes general functions into component functions with M = 2N.Source: §1.1 · p. 4

2 The Upper Bound

Restricting a random function to a suitable random subset gives an O(N^1/3)-query collision-finding algorithm when M = Ω(N^1/2). The proof uses Ambainis’s element distinctness algorithm as a black box.

2 The Upper Bound

  • O(N^1/3) quantum queries find a collision with constant probability for a random function when M = Ω(N^1/2).The result uses Ambainis’s algorithm as a black box.Source: §2 · p. 4
  • A random subset of size M′ = N^1/2/2 contains exactly one collision with probability approaching 1/e, enabling Ambainis’s algorithm to find it in O((M′)^2/3) = O(N^1/3) queries.When M is much larger than M′, repeating the procedure can raise success probability arbitrarily high.Source: §2 · p. 4
  • When M′ is not significantly smaller than M, the algorithm can be adjusted to obtain success probability arbitrarily close to 1 − p, where p is the constant probability that no collision is found.The adjustment addresses the case where the initial subset procedure may find no collision.Source: §2 · p. 4

3 The Lower Bound

The proof bounds the success probability of quantum collision-finding on random functions, then extends the lower bound from equal-sized domains and ranges to general domain sizes. It uses distribution indistinguishability and hybrid arguments to handle the intermediate cases.

3 The Lower Bound

  • For random f:[M]→[N], q queries find a collision with probability at most C(q+1)^3/N, giving a bounded-error lower bound of Ω(N^1/3).The general-domain argument rounds M/N up to a power of two.Source: §3 · p. 4, §3.4 · p. 8
  • Zhandry’s distribution lemma bounds distinguishing probability by C′q^3/r when fixed-query probabilities are degree-at-most-k polynomials in 1/r; small-range distributions are compositions of random functions through [r].The composition is f=h∘g, where g maps into [r] and h maps from [r] to the output space.Source: §3 · p. 5

3.1 The case M = N

  • For M=N, the proof bounds distinguishing a random function from a random permutation by C′q^3/N, then uses that bound to limit collision-finding success.Two extra queries check whether the reported collision is valid.Source: §3.1 · p. 6

3.2 The case M = 2N

  • For M=2N, dropping an independent output bit converts a collision finder into one for the larger-range function, with success probability halved.The resulting success bound is ε<C′(q+2)^3/N.Source: §3.2 · p. 7

3.3 The case M = 2ℓN

  • For M=2^ℓN, hybrid distributions replace the function in stages, and any collision in the composition yields a collision in one component.The small-range distribution theorem bounds adjacent hybrid distinguishability; the M=2N result bounds component collision-finding.Source: §3.3 · pp. 7–8

3.4 General M

  • For general M, rounding M/N up to the nearest power of two transfers the collision-success bound to the original domain size.The proof first establishes the bound when M/N is a power of two.Source: §3.4 · p. 8

4 Lower Bound for Set Equality

The section proves an Ω(N^1/3) quantum-query lower bound for distinguishing identical from distinct ranges of random injective functions. The proof reduces the two cases to a chain of indistinguishable function distributions.

4 Lower Bound for Set Equality

  • O(q^3/N) bounds the success probability for distinguishing identical from distinct ranges of random injective f and g, with domain [N] and codomain [M] where M ≥ 2N.Theorem 4.1 therefore gives an Ω(N^1/3) query lower bound for constant-probability distinction.Source: §4 · pp. 8–9
  • In the first comparison, replacing the random injective f′ and g′ with random functions changes distinguishability by at most O(q^3/N).This compares the identical-range case with the intermediate distribution.Source: §4 · p. 9
  • The intermediate and distinct-range cases are also indistinguishable up to O(q^3/N), so the identical-range and distinct-range cases inherit the same bound.The proof treats the pair of functions as one random function and applies Lemma 3.4.Source: §4 · p. 9

5 Conclusion and Open Problems

The paper establishes a Θ(N^1/3) quantum-query complexity for finding collisions in random functions and points to non-uniform output distributions as future work.

5 Conclusion and Open Problems

  • Θ(N^1/3) quantum queries are necessary and sufficient to find a collision in a random function with bounded error.Source: §5 · p. 9
  • A future direction is to study random functions whose outputs follow non-uniform distributions, including distributions characterized by Rényi entropy H.Source: §5 · p. 9
  • The paper asks whether a Θ(2^H/3) query bound applies when output entropy is H.Source: §5 · p. 9
Loading 1312.1027v3…