Open Collections

Description

We investigate the cost of Grover's quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms. We exhibit a T-optimized circuit for a pre-image attack on SHA-256 that is approximately $2^{149}$ surface code cycles deep and requires approximately $2^{13}$ logical qubits. This yields an overall cost of $2^{162}$ logical-qubit-cycles. Likewise, we exhibit a T-optimized SHA3-256 circuit that is approximately $2^{146}$ surface code cycles deep and requires approximately $2^{16}$ logical qubits for a total cost of, again, $2^{162}$ logical-qubit-cycles. Both attacks require on the order of $2^{128}$ queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as $17$ billion times more expensive than one would expect from the simple query analysis. http://arxiv.org/abs/1603.09383