Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?

D.J. Bernstein

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Downloads (Pure)


    Current proposals for special-purpose factorization hardware will become obsolete if large quantum computers are built: the number-field sieve scales much more poorly than Shor's quantum algorithm for factorization. Will all special-purpose cryptanalytic hardware become obsolete in a post-quantum world? A quantum algorithm by Brassard, HØyer, and Tapp has frequently been claimed to reduce the cost of b-bit hash collisions from 2^b/2 to 2^b/3. This paper analyzes the Brassard-HØyer-Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot-Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.
    Original languageEnglish
    Title of host publicationSHARCS'09 Workshop Record (Proceedings 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, Switserland, September 9-10, 2009)
    Publication statusPublished - 2009


    Dive into the research topics of 'Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?'. Together they form a unique fingerprint.

    Cite this