Papers for

quantum cryptographers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Quantum proofs outperform classical hierarchies despite equal classical computing power

Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA

Abstract: Remark: This work is in submission at STOC'27 and thus the full manuscript has been publicly posted on the conference website since November 3rd, 2026. Inspired by the Codeword-Hash Structure problem recently introduced by Cakan (arXiV, 2026) to separate $\mathsf{QMA}$ from $\mathsf{QCIP}$, we introduce a new problem called Codeword-Hash pairs in Noise ($\mathsf{CHN}$) and prove that, in the query complexity model, it is in $\mathsf{QMA}$ but hard for the $\mathsf{QCMA}$ hierarchy $\mathsf{QCMAH} = \bigcup_{d\geq1}\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots^{\mathsf{QCMA}}}}$, the classical-witness quantum-verifier analogue of $\mathsf{PH}=\bigcup_{d\ge1}\mathsf{NP}^{\mathsf{NP}^{\cdots^{\mathsf{NP}}}}$. Using this problem, we show that there exists a classical oracle ${O}$ such that $\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O} =\mathsf{QCMAH}^{O} \subset \mathsf{QMA}^{O} \text{ but } \mathsf{QMA}^{O}\not\subseteq\mathsf{QCMAH}^{O},$ thus showing that quantum state or quantum proof advantage could exist even if classical computers can efficiently solve any problem that can be quantumly verified with a classical proof. Further, using our problem, we show that various quantum cryptographic primitives can exist even when $\mathsf{P} = \mathsf{QCMA}$ and thus neither quantum-computable one-way functions nor (verifiable) quantum computational advantage exist. In particular, relative to a classical oracle ${O}$ with $\mathsf{P}^{O}=\mathsf{BQP}^{O}=\mathsf{QCMA}^{O}=\mathsf{QCMAH}^{O}$, there exist pseudorandom states with classical keys and public-key encryption with copy-protected quantum decryption keys and classical public keys and ciphertexts, among other primitives, answering an open question of Kretschmer, Qian, and Tal (STOC 2025).

Thu 19 NovCryptography and Security
The gist
Some problems can be checked easier if you have a quantum proof rather than a classical one, even when classical computers are just as powerful as quantum ones for many tasks. The authors created a new problem that shows quantum proofs have an advantage over any classical proof system no matter how many layers of classical verification you stack. They also demonstrated that certain quantum cryptography methods can exist even if classical and quantum computers are equally powerful. This challenges previous assumptions about how classical and quantum computing relate to one another.
Open → 2611.26574v1

Quantum complexity of finding collisions in complex functions determined

Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types

Abstract: We determine the bounded-error quantum query complexity of finding one $r$-collision in an $N$-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,\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 $k$-distinctness. In particular, finding the unique $(k+1)$-collision in type $(k^n,k+1)$ has complexity $Θ_k(N^{3/4-1/[4(2^{k+1}-1)]})$, where $N=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)$ comparison error over $T$ 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.

Fri 13 NovComputational Complexity
The gist
This work figures out how hard it is for a quantum computer to find a repeated output value — called a collision — in a function with many inputs, even when the outputs are grouped in complicated ways. The authors find the precise number of queries a quantum algorithm must make to solve this problem depending on how the outputs are distributed, resolving a previously open question. They develop new mathematical tools to prove these limits and also design algorithms that match these limits exactly. Their results connect different known quantum problems, improving understanding of quantum search tasks.
Open → 2611.17804v1

Quantum method improves bounds on repeated two-player game wins

Parallel Repetition for Entangled Games via Conditional Relative Entropy

Abstract: We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value $1-\varepsilon<1$ and answer alphabets $\mathcal A,\mathcal B$, its $n$-fold repeated value is at most \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, \] for every $n\ge1$. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least $1-\varepsilon+δ$ is at most $\exp[-Ω(δ^5n/(\varepsilon^2L))]$ for $0<δ\le\varepsilon$. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.

Thu 15 OctComputational ComplexityInformation Theory
The gist
The paper studies games where two players share quantum entanglement and answers to questions are repeated many times. It shows how the chance to win all or most of these repeated games decreases quickly, based on a new way to measure information using quantum relative entropy. The authors provide precise math bounds that explain how the winning probability drops with the number of repetitions and size of answers. Their results help understand the limits of quantum strategies in repeated interactions.
Open → 2610.21410v1

Cyclotomic coset problem enables quantum sieve for prime power moduli

Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

Abstract: The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.

Mon 28 SeptCryptography and Security
The gist
Understanding certain hard math problems helps protect data from hackers using future quantum computers. This paper introduces a new problem called the Cyclotomic Coset Problem, which has a special hidden structure that lets the authors design a quantum algorithm to solve it more efficiently. Their algorithm works especially well when the numbers involved are powers of a prime number. However, this advance does not immediately translate to solving the main cryptographic problem known as LWE, which secures many post-quantum cryptography systems.
Open → 2609.34996v1