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

New Generation Computing

A new quantum claw-finding algorithm for three functions

Kazuo Iwama, Akinori Kawachi

Published Dec 1, 2003• 1 citation
Publisher
DOI
10.1007/bf03037306

Related papers

An Improved Claw Finding Algorithm Using Quantum Walk

Seiichiro Tani

Lecture notes in computer science•Aug 14, 2007•16 citations

Claw finding algorithms using quantum walk

Seiichiro Tani

arXiv:0708.2584•Theoretical Computer Science•Sep 5, 2009•79 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

An Efficient Quantum Multi-Collision Search Algorithm

Jian Xiao Zou, Yongyang Liu, Le Dong

In this article, we propose an efficient quantum k-collision search algorithm with low quantum memory O(n). The previous quantum k-collision algorithms can not be converted into a low quantum memory k-collision algorithm directly, because the time complexity of the converted algorithm is larger than the basic k-collision algorithm. To solve this problem, we shall not only divide our low memory quantum k-collision algorithm into several subroutines, but also need to achieve some balances between these subrou tines. The time complexity of our k-collision search algorithm is O(2(2k-2)n/2k+1-3 ), and the classical memory and quantum memory complexities are O(2(2k-2)n/2k+1-3 ) and O(n) respectively. In addition, we propose an efficient k-claw search algorithm, which can output a k-claw with O(n) qubits. Given 2squantum processors, we can construct our quantum k-collision and k-claw parallel algorithm with the time of O(2(2k-2)n-(2k+1-2k-1-3)s/2k+1-3 )while the classical memory and quantum memory complexities are O(2(2k-1-1)n+s-2k-2/2k+1-3 ) and O(n), respectively.

IEEE Access•Jan 1, 2020•3 citations

Parallelism strategies for the tuneable golden-claw finding problem

Reza Azarderakhsh, Jean‐François Biasse, Rami El Khatib +2 more

In this paper we study a strategy for adapting the “Tiny Claw” Grover-based attack of Biasse and Pring (A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE, J. Math. Cryptol. 15 (2019), pp. 143–156) for attacking SIKE and abstract it under a realistic model of classical memory-access costs. Our results allow us to retain the almost quadratic reduction in the overheads involved with the implementing the quantum oracle in this cost model and demonstrate how the cost of the parallel version of this attack scales in a manner superior to that of a naive use of Grover’s algorithm. In order to investigate the utility of the Tiny Claw approach, we perform a quantum resource estimation of the classical and quantum resources required to attack various SIKE instances with Tiny Claw when when we are limited to ≤296 hardware, finding interesting price-points.

International Journal of Computer Mathematics Computer Systems Theory•Feb 4, 2021•0 citations

A Modified Quantum Search Algorithm

Hossein Mehri‐Dehnavi, Hasan Dashtianeh, Hossein Yahyavi Kuchaksaraei +3 more

International Journal of Theoretical Physics•Sep 7, 2018•6 citations
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 article, we propose an efficient quantum k-collision search algorithm with low quantum memory O(n). The previous quantum k-collision algorithms can not be converted into a low quantum memory k-collision algorithm directly, because the time complexity of the converted algorithm is larger than the basic k-collision algorithm. To solve this problem, we shall not only divide our low memory quantum k-collision algorithm into several subroutines, but also need to achieve some balances between these subrou tines. The time complexity of our k-collision search algorithm is O(2(2k-2)n/2k+1-3 ), and the classical memory and quantum memory complexities are O(2(2k-2)n/2k+1-3 ) and O(n) respectively. In addition, we propose an efficient k-claw search algorithm, which can output a k-claw with O(n) qubits. Given 2squantum processors, we can construct our quantum k-collision and k-claw parallel algorithm with the time of O(2(2k-2)n-(2k+1-2k-1-3)s/2k+1-3 )while the classical memory and quantum memory complexities are O(2(2k-1-1)n+s-2k-2/2k+1-3 ) and O(n), respectively.
In this paper we study a strategy for adapting the “Tiny Claw” Grover-based attack of Biasse and Pring (A framework for reducing the overhead of the quantum oracle for use with Grover's algorithm with applications to cryptanalysis of SIKE, J. Math. Cryptol. 15 (2019), pp. 143–156) for attacking SIKE and abstract it under a realistic model of classical memory-access costs. Our results allow us to retain the almost quadratic reduction in the overheads involved with the implementing the quantum oracle in this cost model and demonstrate how the cost of the parallel version of this attack scales in a manner superior to that of a naive use of Grover’s algorithm. In order to investigate the utility of the Tiny Claw approach, we perform a quantum resource estimation of the classical and quantum resources required to attack various SIKE instances with Tiny Claw when when we are limited to ≤296 hardware, finding interesting price-points.