publication . Article . Book . Part of book or chapter of book . Other literature type . 1998

Quantum cryptanalysis of hash and claw-free functions

Invited paper
Brassard, G.; Peter Høyer; Tapp, A.;
Open Access
  • Published: 01 Jan 1998 Journal: ACM SIGACT News, volume 28, pages 14-19 (issn: 0163-5700, Copyright policy)
  • Publisher: Association for Computing Machinery (ACM)
In this note, we give a quantum algorithm that finds collisions in arbitrary t-to-one functions after only O(3rN/t) 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.
Download fromView all 4 versions
Part of book or chapter of book
Provider: UnpayWall
Other literature type . 1998
Provider: Datacite
Part of book or chapter of book . 2006
Provider: Crossref
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue