Abstract
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 language | English |
|---|---|
| Title of host publication | SHARCS'09 Workshop Record (Proceedings 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, Switserland, September 9-10, 2009) |
| Pages | 105-116 |
| Publication status | Published - 2009 |