Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9705002 · Lecture notes in computer science

Quantum cryptanalysis of hash and claw-free functions: Invited paper

Gilles Brassard, Peter Høyer, Alain Tapp

Published Jan 1, 1998• 394 citations
arXivHTMLPDF
DOI
10.1007/bfb0054319

Related papers

Dual universality of hash functions and its applications to quantum cryptography

豊広 鶴丸, 正人 林

IEICE Technical Report; IEICE Tech. Rep.•Feb 24, 2011•4 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.

quant-pharXiv:2609.35633•Sep 29, 2026•0 citations

Quantum cryptanalysis of hash and claw-free functions

Gilles Brassard, Peter Høyer, Alain Tapp

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 News•Jun 1, 1997•144 citations

Security of quantum cryptography and the hash function

Toyohiro Tsurumaru

IEICE Technical Report; IEICE Tech. Rep.•Mar 3, 2016•0 citations

Analysis of Properties of Quantum Hashing

Alexander Vasiliev, A. R. Vasilov, M. A. Latypov

Journal of Mathematical Sciences•Jul 29, 2019•5 citations

Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE

Samuel Jaques, John M. Schanck

Lecture notes in computer science•Jan 1, 2019•96 citations
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.
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.