betaFeedback

WorksPhysics and Astronomy

Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types

Abstract

We determine the bounded-error quantum query complexity of finding one rr-collision in an NN-input function of prescribed type, which specifies all equality-class sizes. For every fixed maximum class size and collision order, we give a tight bound as the maximum of scales determined by the numbers of classes of size at least 2,…,r2,\ldots,r. The lower bound holds for a uniformly random function of that type, and a matching algorithm succeeds on every such function. No intermediate class size is required to occur, and every feasible output alphabet is allowed. The characterization connects the abundant-collision regime associated with set equality to the sparse-target regime of kk-distinctness. In particular, finding the unique (k+1)(k+1)-collision in type (kn,k+1)(k^n,k+1) has complexity Θk(N3/4−1/[4(2k+1−1)])Θ_k(N^{3/4-1/[4(2^{k+1}-1)]}), where N=kn+k+1N=kn+k+1, resolving an open problem of Belovs. For the lower bound, we introduce a filtered compressed permutation oracle that projects onto a harmonic database subspace after each complete function query. Its O(T/N)O(T/N) comparison error over TT queries overcomes the square-root limitation of the unfiltered process. Hidden capacity extensions and moment estimates retain the populations at each intermediate collision order. Matching upper bounds use sampled collision lists and colored adaptive learning graphs, with a coherent decision-to-search conversion that avoids logarithmic overhead. We also give an alternative nested quantum-walk algorithm for three-collision search, matching the bound up to polylogarithmic factors.

Introduction

Quantum query complexity provides a framework for understanding the power and limitations of quantum algorithms when access to the input is restricted to oracle queries. In the worst-case setting, an algorithm must succeed on every input satisfying the promise. The polynomial method [5] and the adversary method [2, 18] are central tools for proving quantum query lower bounds. The general adversary bound characterizes bounded-error query complexity for function evaluation up to constant factors, but constructing suitable adversary matrices and bounding their norms can be technically demanding.

In the average-case setting, an algorithm’s success probability is averaged over a prescribed input distribution. A lower bound for such a distribution also gives a worst-case lower bound whenever its support consists of valid inputs. The structure of the distribution offers an additional way to analyze the information acquired through queries. Zhandry’s compressed-oracle technique [27] can be viewed as a quantum analogue of lazy sampling: it represents a random function by a superposition of small, orthogonal databases. Each query changes the database by a bounded amount, and successful search can be related to the amplitude of databases containing the required witnesses. A lower bound can therefore be obtained by controlling how quickly these witnesses form.

The original construction exploits the independence of function values at different inputs. Extending this approach to correlated distributions is substantially more difficult. For a random permutation, injectivity couples the values across the domain; for a random function with prescribed multiplicities, observing one value constrains the multiplicities remaining elsewhere. Compressed permutation oracles [14, 15] provide a way to represent these dependencies through partial injections. They also suggest a route to collision bounds under exact-multiplicity promises, where the independence needed by the original compressed oracle is unavailable.

Collision search under such promises includes two different regimes. In the first, many equality classes can supply a target collision. A basic example is a function of pure type (kn)(k^n), in which every image value has exactly kk preimages. For 2≤r≤k2 \le r \le k, every class contains an rr-collision. This is the abundant-collision regime familiar from the collision problem and from the equal-image case of set equality [11, 9]. In the second regime, only a few classes contain a target collision, while smaller collisions may be plentiful. This is the situation underlying rr-distinctness. The type (kn,k+1)(k^n,k+1) isolates the difficulty: there is one (k+1)(k+1)-collision to find, surrounded by nn classes of size kk. We study these two collision-search regimes within a single exact-type formulation.

We consider functions f:[N]→Zqf : [N] \to\mathbb{Z}_q of exact type

λ=(1n1,…,KnK),N=∑d=1Kdnd.\lambda= (1^{n_1}, \ldots, K^{n_K}), \qquad N = \sum_{d=1}^{K} d n_d.

This means that exactly ndn_d distinct output values have dd preimages. Define the tail counts Bj=∑d=jKndB_j = \sum_{d=j}^{K} n_d and set M=Br≥1M = B_r \ge1. The alphabet is feasible precisely when q≥B1q \ge B_1. An rr-collision is a list of rr distinct inputs with the same function value. The algorithm may know the numbers ndn_d, but it receives only the ordinary function oracle. It is not given the members of any equality class. Throughout the main result, KK and rr are fixed and one collision is requested.

The type affects which partial collisions are useful. A repeated pair is progress toward a triple only if its equality class has another element. With one triple and many two-element classes, most pairs cannot be extended. When eligible classes are abundant, on the other hand, tables of partial collisions can be built and extended by quantum search. The number MM of target classes alone does not capture both behaviors: the intermediate populations B2,…,Br−1B_2,\ldots,B_{r-1} also matter.

This dependence on the type is the subject of an explicit open question of Belovs [8, Section 7]. After proving a tight lower bound for unrestricted rr-distinctness over sufficiently large alphabets, he asked whether the same bound holds with one rr-element class, linearly many (r−1)(r-1)-element classes, and no classes of other sizes. In our notation this is the type (kn,k+1)(k^n,k+1) with r=k+1r=k+1. He also asked for a tight characterization for an arbitrary prescribed partition. We resolve both questions for every bounded type, uniformly over all alphabets that realize the type. The resulting formula connects the abundant-collision and sparse-target regimes through the full sequence of intermediate populations.

Our contributions

We determine, up to constant factors, the quantum query complexity of finding an rr-collision in a function of arbitrary prescribed bounded type. Our characterization gives matching lower and upper bounds throughout the abundant-collision and sparse-target regimes.

For the tail counts BjB_j defined above, write

Qr(λ)=max⁡2≤j≤r(N2j−1∏i=2j−1Bi2i−2M2j−2)1/(2j−1),M=Br,(1)Q_r(\lambda)=\max_{2\le j\le r}\left(\frac{N^{2^{j-1}}\prod_{i=2}^{j-1}B_i^{2^{i-2}}}{M^{2^{j-2}}}\right)^{1/(2^j-1)},\qquad M=B_r, \tag*{(1)}

where an empty product equals one.

Theorem 1.1 (Quantum search for a prescribed bounded type). Fix K≥r≥2K\ge r\ge2. For every sufficiently large NN, every exact type λ\lambda of maximum class size at most KK with Br≥1B_r\ge1, and every alphabet q≥B1q\ge B_1, the worst-case quantum query complexity of finding one rr-collision with probability at least 2/32/3 is

ΘK,r(Qr(λ)).\Theta_{K,r}(Q_r(\lambda)).

The type may be supplied to the algorithm. The lower bound also holds when success is averaged over the uniform distribution of functions of that exact type. The constants are independent of the alphabet and the type.

Although the expression in (1) involves several scales, it is a single characterization valid for every bounded type. Each scale captures a possible obstruction at an intermediate collision order. The following examples illustrate the range of the theorem.

Example 1 (Pure type (kn)(k^n)): Let N=knN=kn and fix 2≤r≤k2\le r\le k. All relevant tail counts equal n=Θk(N)n=\Theta_k(N), so Theorem 1.1 gives

Θk,r(N(2r−1)/(2r−1)).\Theta_{k,r}\left(N^{(2^r-1)/(2^r-1)}\right).

This recovers the single-target specialization of our earlier multi-collision bounds [23]. When r=kr=k, it also recovers the tight adaptive bound of Peng and Wu [24] for promised kk-to-one finding, with the matching algorithm supplied by Liu and Zhandry [19]. Thus both single-target pure-type lower bounds are contained in the characterization for arbitrary bounded types. In particular, the pair-finding scale is Θ(N1/3)\Theta(N^{1/3}), and higher collision orders are covered even though the input has no equality classes of intermediate sizes.

Example 2 (Exceptional type (kn,k+1)(k^n,k+1)): Here N=kn+k+1N=kn+k+1, and the task is to find the unique (k+1)(k+1)-collision. The tail counts are B2=⋯=Bk=n+1=Θk(N)B_2=\cdots=B_k=n+1=\Theta_k(N) and Bk+1=1B_{k+1}=1. Substitution in Theorem 1.1 gives the following consequence.

Corollary 1.2 (Tight search on the exceptional type). For fixed k≥2k \ge2, the bounded-error function-query complexity of finding the unique (k+1)(k+1)-collision in type (kn,k+1)(k^n,k+1) is

Θk(N3/4−1/[4(2k+1−1)])\Theta_k\left(N^{3/4-1/[4(2^{k+1}-1)]}\right)

for every feasible alphabet q≥n+1q \ge n+1.

Indeed, the jjth scale in (1) is Θk(N3/4−1/[4(2j−1)])\Theta_k\left(N^{3/4-1/[4(2^j-1)]}\right), which increases with jj. This resolves the open problem posed by Belovs in [8 Section 7]. His analysis of hard input types uses linearly many classes of every smaller size. Our lower bound attains the same distinctness exponent when all non-target classes have size kk, with no singletons or other intermediate class sizes. The general theorem likewise imposes no linear-population assumption on any intermediate class size. The bound also holds for the smallest feasible alphabet, q=n+1q=n+1, so no additional large-alphabet assumption is needed.

Example 3 (Type (1n,2b,3)(1^n,2^b,3)): Set N=n+2b+3N=n+2b+3. Since M=1M=1 and B2=b+1B_2=b+1, the tight complexity of finding the unique triple is

Θ(max⁡{N2/3,N4/7(b+1)1/7}).(2)\Theta\left(\max\left\{N^{2/3},N^{4/7}(b+1)^{1/7}\right\}\right). \tag*{(2)}

The two terms balance at b+1≍N2/3b+1\asymp N^{2/3}. Below this scale, the element-distinctness term dominates; above it, the population of non-extendable pairs determines the complexity. In particular, b=O(1)b=O(1) gives Θ(n2/3)\Theta(n^{2/3}), the element-distinctness scale, whereas b=Ω(n)b=\Omega(n) gives b=Θ(N)b=\Theta(N) and complexity Θ(N5/7)\Theta(N^{5/7}), matching the worst-case three-distinctness exponent. Thus the number of pairs controls a transition between two familiar query bounds.

Beyond this characterization, our contributions include both lower-bound techniques and matching algorithms.

A common framework for collision and distinctness regimes. The complexity formula places the abundant-collision regime associated with collision and set equality and the sparse-target regime associated with kk-distinctness in one quantitative framework. It identifies how the populations at successive collision orders govern the transition between them. Our lower-bound argument tracks partial records within equality classes, so the intermediate levels remain available even when the input contains no actual classes of those sizes. This permits a uniform analysis of types that previously required different treatments. Our bounds require neither linearly many classes of each intermediate size nor a large-alphabet assumption: they hold uniformly for every q≥B1q \ge B_1, including the smallest feasible alphabet q=B1q=B_1, with constants independent of qq.

Filtered CPO beyond the square-root scale. We introduce a filtered compressed permutation oracle (filtered CPO) process for analyzing complete function queries. After each such query, the process projects the database onto its harmonic subspace. We prove an O(T/N)O(T/N) comparison with the real function-query evolution, which remains small for T=o(N)T=o(N) (Corollary 4.19). This enables lower bounds beyond the square-root horizon of ordinary CPO soundness [15], including the distinctness scales above. We also prove that the unfiltered process has an intrinsic square-root obstruction even on complete function-query blocks (Proposition 4.16). The filtered process, together with hidden capacity extensions and moment estimates in terms of tail counts, supplies the lower bound in Theorem 1.1.

Matching upper bounds via adaptive learning graphs. We give function-query algorithms attaining OK,r(Qr(λ))O_{K,r}(Q_r(\lambda)) on every input of the prescribed type, without logarithmic overhead (Theorem 8.1). For scales at most N\sqrt{N}, sampled collision tables and Grover enumeration suffice. For larger scales, we develop a colored adaptive learning graph (ALG) whose costs depend on the intermediate populations. Ordered restriction of the input roles supplies the required bounds on prefix populations, and a coherent decision-to-search conversion has only constant overhead. These constructions establish the matching upper bound across the full range of bounded types.

An alternative nested quantum-walk algorithm. For three-collision search, we also give a nested quantum random walk (nested QRW) with query complexity

O~K(max⁡{N2/3M−1/3, N4/7B21/7M−2/7})\widetilde{O}_{K}\left(\max\left\{N^{2/3}M^{-1/3},\ N^{4/7}B_{2}^{1/7}M^{-2/7}\right\}\right)

matching the type-dependent lower bound up to polylogarithmic factors (Theorem A.1). Its main ingredient is a reversible inner-buffer update that retains all eligible pairs, including overlapping pairs. The stationary-distribution, spectral-gap, and initialization analyses are given in Appendix § 12. This provides a separate quantum-walk construction for the three-collision bound for arbitrary bounded types.

Related work

Collision and set equality. Brassard, Høyer, and Tapp [11] gave a quantum algorithm that finds a pair in a kk-to-one function on NN inputs using O((N/k)1/3)O((N/k)^{1/3}) expected queries. Aaronson and Shi [1] proved matching collision lower bounds by the polynomial method; Ambainis [3] subsequently removed the large-range restriction. Belovs and Rosmanis [9] gave tight general adversary bounds for collision and set equality under a sufficiently large alphabet assumption. In set equality, two injective functions on nn-element domains are promised to have equal or disjoint images. In the equal-image case their disjoint union has type (2n)(2^n), with one preimage in each domain for every value. This explains the connection with the abundant-collision regime; the set-equality promise also specifies how the preimages are distributed between the domains.

Higher-order and multiple collisions. Liu and Zhandry [19] obtained the exponent (2r−1−1)/(2r−1)(2^{r-1}-1)/(2^r-1) for finding one rr-collision. Their upper-bound construction applies to exact rr-to-one functions and, more generally, to sufficiently compressing functions. Their matching lower bound uses the compressed oracle for independently sampled random functions. Hamoudi and Magniez [17] developed strong success-probability bounds for finding many collision pairs and used them to prove quantum time-space tradeoffs. These random-function lower bounds do not directly transfer to exact types: conditioning on the complete type destroys the independence on which the compression relies. Our lower bound treats the uniform distribution on each prescribed type directly. Our earlier work [23] established tight pure-type bounds for collisions in multiple distinct classes. Peng and Wu [24] obtained tight adaptive and non-adaptive bounds for promised kk-to-one finding. The present theorem extends the adaptive single-target characterization from pure types to arbitrary bounded types.

k-distinctness. Ambainis’s quantum walk [4] solves element distinctness in O(N2/3)O(N^{2/3}) queries, matching the polynomial lower bound, and finds rr equal elements in O(Nr/(r+1))O(N^{r/(r+1)}) queries. Belovs [6] improved the latter bound to O(N3/4−1/[4(2r−1)])O(N^{3/4-1/[4(2^r-1)]}) using adaptive learning graphs. On the lower-bound side, Bun, Kothari, and Thaler [12] and Mande, Thaler, and Zhu [21] used dual polynomials to obtain exponents approaching 3/43/4 as rr grows. Belovs [8] recently proved the matching lower bound for every fixed rr, assuming an alphabet of size Ω(N2)\Omega(N^2). His proof uses hard input types with many classes of each smaller size. Our question fixes the exact type: a bound attained on those hard input types need not hold on a specified type with missing class sizes. Theorem 1.1 determines this dependence for bounded types and all feasible alphabets.

Compressed permutation oracles. Rosmanis [25] introduced a representation-theoretic decomposition of the permutation-oracle space into knowledge subspaces, recovering the tight permutation-inversion bound under forward queries. Majenz, Malavolta, and Walter [22] developed a permutation superposition oracle based on strictly monotone factorizations into transpositions. This gives a nonlocal database representation of a random permutation, supports both forward and inverse queries, and yields search bounds for predicates on a single input-output pair.

Unruh [26] proposed a compressed permutation oracle in which inverse queries are implemented by reversing the database; its soundness was left conjectural. Carolan [14] modified this construction to preserve injectivity explicitly and proved its soundness. Carolan and Majenz [15] improved its soundness horizon from the N1/12N^{1/12} scale to the tight N1/2N^{1/2} scale through a representation-theoretic analysis of the compression isometry. We use their completion-frame structure to analyze complete function queries with a harmonic projection after each query. Keeping the function-query interface is essential for types with few target classes, where independent permutation access can reveal additional information. The next subsection explains the filtered comparison and the estimates in terms of tail counts needed for our lower bounds.

Technique overview

Two issues govern the lower bound. First, a useful database representation must remain accurate beyond the square-root query scale. Second, it must distinguish partial collisions that can be extended to a target from those trapped in smaller classes. We address the first issue by filtering complete function queries, and the second by comparing hidden bucket capacities. Moment estimates connect these two parts and identify the hardest intermediate collision order. The upper bound balances the same intermediate populations through sampling and adaptive learning graphs.

Preserving the function-query interface. We represent a function of the prescribed type as f=a∘β∘πf = a \circ\beta\circ\pi, where π\pi is a uniform hidden permutation of slots, β\beta assigns slots to buckets of the prescribed sizes, and aa is an injective table of output labels. This samples the exact type uniformly for every feasible alphabet. The algorithm receives only the function oracle; the permutation, bucket assignment, and label table belong to the representation used in the analysis. In the phase-query picture, a complete compressed function query has the form F′=CxLCxF' = C_x L C_x: decompress at the queried input, apply the bucket-label phase, and recompress. Its temporary response register returns to the blank state. Analyzing this complete block preserves the restriction on oracle access that is needed for sparse target classes.

Filtering the database evolution. Completion vectors associate a partial injection with the superposition of permutations extending it. After removing the contributions already represented at smaller degrees, their adjoints identify the harmonic database subspace. Its coefficients have zero sums along each input- and output-deletion fiber. The associated Gram operator gives two useful encodings: V~\widetilde{V} preserves norms, while WW exactly inverts completion synthesis. These maps differ by O(T/N)O(T/N) on states of degree at most TT in the range we use. We follow the query dynamics through WW and use V~\widetilde{V} at the endpoint to compare probabilities.

An unfiltered complete query can create a component of norm O(N−1/2)O(N^{-1/2}) outside the harmonic subspace. This is a substantive obstruction: Proposition 4.16 gives a distinguishing experiment at T=Θ(N)T = \Theta(\sqrt{N}) using only complete function-query blocks. Our analytical process instead applies the harmonic projector KK after each complete query, without renormalizing:

ξ0=∣∅⟩,ξt+1=KFtUtξt,∥ξT−V~ψT∥=O(T/N).\xi_0 = |\varnothing\rangle,\qquad\xi_{t+1} = K F_t U_t \xi_t,\qquad\lVert\xi_T - \widetilde{V}\psi_T\rVert= O(T/N).

Here Ut\mathcal{U}_t is the algorithm’s free unitary and ψT\psi_T is its real state; the initial vector includes the same algorithm registers. The comparison holds for T≤N/4T \le N/4 and sufficiently large NN (Corollary 4.19). Its key estimate concerns the return to the harmonic subspace: the upward degree component is exact, while conditioning on fresh and recorded inputs bounds the middle and downward corrections by O(1/(N−2t))O(1/(N-2t)). Summing these corrections gives O(T/N)O(T/N), which remains small at all scales needed here.

References

  1. [1]Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 51(4):595–605, 2004. doi:10.1145/1008731.1008735.DOI
  2. [2]Andris Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 636–643, 2000. arXiv:quant-ph/0002066.DOI
  3. [3]Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1(3):37–46, 2005. doi:10.4086/toc.2005.v001a003.DOI
  4. [4]Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. arXiv:quant-ph/0311001.
  5. [5]Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. arXiv:quant-ph/9802049.DOI
  6. [6]Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 207–216, 2012. arXiv:1205.1534v2.arxiv.org/abs/1205.1534
  7. [7]Aleksandrs Belovs. Span programs for functions with constant-sized 1-certificates. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 77–84, 2012. arXiv:1105.4024.arxiv.org/abs/1105.4024
  8. [8]Aleksandrs Belovs. Tight quantum lower bound for k-distinctness. arXiv:2604.05133v2, 2026.arxiv.org/abs/2604.05133
  9. [9]Aleksandrs Belovs and Ansis Rosmanis. Adversary lower bounds for the collision and the set equality problems. Quantum Information and Computation, 18(3–4):198–222, 2018. arXiv:1310.5185.
  10. [10]Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46, 1998. arXiv:quant-ph/9605034.arxiv.org/abs/quant-ph/9605034
  11. [11]Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In LATIN 1998: Theoretical Informatics, volume 1380 of Lecture Notes in Computer Science, pages 163–169, 1998. doi:10.1007/BFb0054319.DOI
  12. [12]Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, pages 297–310, 2018. arXiv:1710.09079.DOI
  13. [13]Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. doi:10.1137/S0097539796300921.
  14. [14]Joseph Carolan. Compressed permutation oracles. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 150–161, 2026. arXiv:2509.18586.arxiv.org/abs/2509.18586
  15. [15]Joseph Carolan and Christian Majenz. Compressed permutation oracles revisited. arXiv:2609.28469v1, 2026.arxiv.org/abs/2609.28469
  16. [16]Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez. A time-efficient quantum walk for 3-distinctness using nested updates. arXiv:1302.7316, 2013.arxiv.org/abs/1302.7316
  17. [17]Yassine Hamoudi and Frédéric Magniez. Quantum time-space tradeoff for finding multiple collision pairs. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, volume 197 of LIPIcs, pages 1:1–1:21, 2021. doi:10.4230/LIPIcs.TQC.2021.1.
  18. [18]Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum query complexity of state conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 344–353, 2011. arXiv:1011.3020.DOI
  19. [19]Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Advances in Cryptology—EUROCRYPT 2019, 2019. arXiv:1811.05385.arxiv.org/abs/1811.05385
  20. [20]Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/090745854.DOI
  21. [21]Nikhil S. Mande, Justin Thaler, and Shuchen Zhu. Improved approximate degree bounds for k-distinctness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, volume 158 of LIPIcs, pages 2:1–2:22, 2020. doi:10.4230/LIPIcs.TQC.2020.2.DOI
  22. [22]Christian Majenz, Giulio Malavolta, and Michael Walter. Permutation superposition oracles for quantum query lower bounds. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1508–1519, 2025. arXiv:2407.09655.DOI
  23. [23]Tianci Peng, Shiqi Hou, and Xiaoyang Dong. Quantum multi-collision lower bounds for arbitrary bounded types. Cryptology ePrint Archive, Paper 2026/2663, 2026. IACR ePrint 2026/2663.
  24. [24]Pan Peng and Jingyu Wu. Quantum lower bounds for collision problems. arXiv:2611.01767, 2026.arxiv.org/abs/2611.01767
  25. [25]Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. arXiv:2103.08975v2, 2022.arxiv.org/abs/2103.08975
  26. [26]Dominique Unruh. Towards compressed permutation oracles. In Advances in Cryptology—ASIACRYPT 2023, Part IV, volume 14441 of Lecture Notes in Computer Science, pages 369–400, 2023. IACR ePrint 2023/770.DOI
  27. [27]Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Advances in Cryptology—CRYPTO 2019, 2019. IACR ePrint 2018/276.DOI

Paper details

vlnc:W_jwv6yffa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents