Welcome to the resource topic for 2016/992
Title:
Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
Authors: Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, John Schanck
Abstract: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 circuit for a pre-image attack on SHA-256 that is approximately 2^{153.8} surface code cycles deep and requires approximately 2^{12.6} logical qubits. This yields an overall cost of 2^{166.4} logical-qubit-cycles. Likewise we exhibit a SHA3-256 circuit that is approximately 2^{146.5} surface code cycles deep and requires approximately 2^{20} logical qubits for a total cost of, again, 2^{166.5} 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 275 billion times more expensive than one would expect from the simple query analysis.
ePrint: https://eprint.iacr.org/2016/992
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .