In this note, we give a quantum algorithm that finds collisions in arbitrary τ-to-one functions after only O ( 3 √ N /τ) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.In this note, we give a quantum algorithm that finds collisions in arbitrary τ-to-one functions after only O ( 3 √ N /τ) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.

ACM SIGACT NewsJun 1, 1997132 citations

Security of quantum cryptography and the hash function

Toyohiro Tsurumaru

IEICE Technical Report; IEICE Tech. Rep.Mar 3, 20160 citations

Succinct Arguments for QMA from Collapsing Hash Functions

James Bartusek, Giulio Malavolta

We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state generation} protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicrypt'' assumptions, which are not known to imply public-key encryption. Our main technical contribution is a quantum-succinct \emph{claw-state generation} protocol that allows us to bootstrap a small number of quantum correlations into an arbitrarily large number of claw-state correlations, using classical communication only. This improves upon the work of [Zhang, STOC 2021], having better round complexity, a proof in the standard model, and being overall much simpler. This yields a quantum-succinct blind delegation of quantum computation protocol from one-way functions, which we plug into the communication-compression compiler of [Bartusek, Liu, and Malavolta, EUROCRYPT 2026] to obtain succinct arguments for QMA.

quant-pharXiv:2609.35633Sep 29, 20260 citations

Post-Quantum $κ$ -to-1 Trapdoor Claw-free Functions from Extrapolated Dihedral Cosets

Xingyu Yan, Licheng Wang, Lize Gu +2 more

\emph{Noisy trapdoor claw-free function} (NTCF) as a powerful post-quantum cryptographic tool can efficiently constrain actions of untrusted quantum devices. However, the original NTCF is essentially \emph{2-to-1} one-way function (NTCF $^1_2$ ). In this work, we attempt to further extend the NTCF $^1_2$ to achieve \emph{many-to-one} trapdoor claw-free functions with polynomial bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF $^1_2$ by drawing on extrapolated dihedral cosets, thereby giving a model of NTCF $^1_κ$ where $κ$ is a polynomial integer. Then, we present an efficient construction of NTCF $^1_κ$ assuming \emph{quantum hardness of the learning with errors (LWE)} problem. We point out that NTCF can be used to bridge the LWE and the dihedral coset problem (DCP). By leveraging NTCF $^1_2$ (resp. NTCF $^1_κ$ ), our work reveals a new quantum reduction path from the LWE problem to the DCP (resp. extrapolated DCP). Finally, we demonstrate the NTCF $^1_κ$ can naturally be reduced to the NTCF $^1_2$ , thereby achieving the same application for proving the quantumness.\emph{Noisy trapdoor claw-free function} (NTCF) as a powerful post-quantum cryptographic tool can efficiently constrain actions of untrusted quantum devices. However, the original NTCF is essentially \emph{2-to-1} one-way function (NTCF$^1_2$). In this work, we attempt to further extend the NTCF$^1_2$ to achieve \emph{many-to-one} trapdoor claw-free functions with polynomial bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF$^1_2$ by drawing on extrapolated dihedral cosets, thereby giving a model of NTCF$^1_κ$ where $κ$ is a polynomial integer. Then, we present an efficient construction of NTCF$^1_κ$ assuming \emph{quantum hardness of the learning with errors (LWE)} problem. We point out that NTCF can be used to bridge the LWE and the dihedral coset problem (DCP). By leveraging NTCF$^1_2$ (resp. NTCF$^1_κ$), our work reveals a new quantum reduction path from the LWE problem to the DCP (resp. extrapolated DCP). Finally, we demonstrate the NTCF$^1_κ$ can naturally be reduced to the NTCF$^1_2$, thereby achieving the same application for proving the quantumness.

arXiv:2211.16993Nov 30, 20220 citations

Quantum cryptanalysis

Kahrobaei, Delaram, Flores, Ramón, Marialaura Noce +2 more

Mathematical surveys and monographsJan 1, 20240 citations

^1_2

). In this work, we attempt to further extend the NTCF

^1_2

to achieve \emph{many-to-one} trapdoor claw-free functions with polynomial bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF

^1_2

by drawing on extrapolated dihedral cosets, thereby giving a model of NTCF

^1_κ

where

κ

is a polynomial integer. Then, we present an efficient construction of NTCF

^1_κ

assuming \emph{quantum hardness of the learning with errors (LWE)} problem. We point out that NTCF can be used to bridge the LWE and the dihedral coset problem (DCP). By leveraging NTCF

^1_2

(resp. NTCF

^1_κ

), our work reveals a new quantum reduction path from the LWE problem to the DCP (resp. extrapolated DCP). Finally, we demonstrate the NTCF

^1_κ

can naturally be reduced to the NTCF

^1_2

, thereby achieving the same application for proving the quantumness.