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

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?\nA 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.\nThis 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.