Gilles Brassard
Abstract
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.
Index Terms
- Quantum cryptanalysis of hash and claw-free functions
Recommendations
Cryptanalysis of Hash Functions with Structures
Selected Areas in CryptographyHash function cryptanalysis has acquired many methods, tools and tricks from other areas, mostly block ciphers. In this paper another trick from block cipher cryptanalysis, the structures, is used for speeding up the collision search. We investigate the ...
Cryptanalysis of hash functions based on blockciphers suitable for IoT service platform security
It is well-known that blockcipher-based hash functions may be attacked when adopting blockciphers having related-key differential properties. However, all forms of related-key differentials are not always effective to attack them. In this paper we ...
Cryptanalysis of the ESSENCE family of hash functions
Inscrypt'09: Proceedings of the 5th international conference on Information security and cryptologyESSENCE is a family of cryptographic hash functions, accepted to the first round of NIST's SHA-3 competition. This paper presents the first known attacks on ESSENCE. We present a semi-free-start collision attack on 31 out of 32 rounds of ESSENCE-512, ...
Comments