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.
|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)|
|Publication status||Published - 2009|