Open Collections

Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3

Banff International Research Station for Mathematical Innovation and Discovery

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

Mathematics; Quantum theory; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: Institute for Quantum Computing

2016-10-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/59540

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/