×

Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. (English) Zbl 1418.94028

Avanzi, Roberto (ed.) et al., Selected areas in cryptography – SAC 2016. 23rd international conference, St. John’s, NL, Canada, August 10–12, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10532, 317-337 (2017).
Summary: 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.
For the entire collection see [Zbl 1378.94001].

MSC:

94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Shor, PW, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509 (1997) · Zbl 1005.11065 · doi:10.1137/S0097539795293172
[2] Boneh, D.; Lipton, RJ; Coppersmith, D., Quantum cryptanalysis of hidden linear functions, Advances in Cryptology — CRYPT0’ 95, 424-437 (1995), Heidelberg: Springer, Heidelberg · Zbl 0876.94023 · doi:10.1007/3-540-44750-4_34
[3] Grover, LK, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett., 79, 325-328 (1997) · doi:10.1103/PhysRevLett.79.325
[4] Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4-5), 493-505 (1998). doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
[5] Gilles, B., Peter, H., Michele, M., Alain, T.: Quantum amplitude amplification and estimation. Quantum Comput. Quantum Inf. 305, 53-74 (2002). e-print arXiv:quant-ph/0005055. Lomonaco Jr., S.J. (ed.) AMS Contemporary Mathematics · Zbl 1063.81024
[6] U.S. National Security Agency: NSA Suite B Cryptography - NSA/CSS. NSA. https://www.nsa.gov/ia/programs/suiteb_cryptography/
[7] Chen, L., Jordan, S., Liu, Y.K., Moody, D., Peralta, R., Perlner, R., Smith-Tone, D.: Report on post-quantum cryptography. National Institute of Standards and Technology Internal Report 8105, February 2016
[8] Lenstra, A.K.: Key lengths. In: Handbook of Information Security. Wiley (2004)
[9] Lenstra, AK; Verheul, ER, Selecting cryptographic key sizes, J. Cryptol., 14, 4, 255-293 (2001) · Zbl 1006.94020 · doi:10.1007/s00145-001-0009-4
[10] Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T., Thompson, E., Weiner, M.: Minimal key lengths for symmetric ciphers to provide adequate commercial security. Technical report, An ad hoc group of cryptographers and computer scientists (1996)
[11] Amy, M.; Maslov, D.; Mosca, M., Polynomial-time t-depth optimization of Clifford+T circuits via matroid partitioning, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 33, 10, 1476-1489 (2014) · doi:10.1109/TCAD.2014.2341953
[12] Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates, e-print arXiv:1512.04965 [quant-ph] · Zbl 1405.81026
[13] Fowler, AG; Mariantoni, M.; Martinis, JM; Cleland, AN, Surface codes: towards practical large-scale quantum computation, Phys. Rev. A, 86, 032324 (2012) · doi:10.1103/PhysRevA.86.032324
[14] Fowler, AG; Whiteside, AC; Hollenberg, LCL, Towards practical classical processing for the surface code: timing analysis, Phys. Rev. A, 86, 4, 042313 (2012) · doi:10.1103/PhysRevA.86.042313
[15] Fowler, AG; Mariantoni, M.; Martinis, JM; Cleland, AN, Surface codes: towards practical large-scale quantum computation, Phys. Rev. A, 86, 3, 032324 (2012) · doi:10.1103/PhysRevA.86.032324
[16] Fowler, AG; Whiteside, AC; Hollenberg, LCL, Towards practical classical processing for the surface code, Phys. Rev. Lett., 108, 18, 180501 (2012) · doi:10.1103/PhysRevLett.108.180501
[17] Fowler, A.G.: Minimum weight perfect matching of fault-tolerant topological quantum error correction in average \(O(1)\) parallel time. arXiv:1307.1740 [quant-ph], July 2013
[18] Mining hardware comparison. Bitcoin Wiki, September 2015. https://en.bitcoin.it/wiki/Mining_hardware_comparison. Accessed 30 Mar 2016
[19] Bernstein, D.J., Lange, T. (eds.): eBACS: ECRYPT Benchmarking of Cryptographic Systems. http://bench.cr.yp.to. Accessed 30 Mar 2016
[20] Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A, 87, 042302 (2013). doi:10.1103/PhysRevA.87.042302
[21] NIST: Federal information processing standards publication 180-2 (2002). See also the Wikipedia entry http://en.wikipedia.org/wiki/SHA-2
[22] Parent, A., Roetteler, M., Svore, K.M.: Reversible circuit compilation with space constraints. arXiv preprint arXiv:1510.00377 (2015) · Zbl 1487.68108
[23] Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv preprint arXiv:quant-ph/0410184 (2004)
[24] Amy, M.; Maslov, D.; Mosca, M.; Roetteler, M., A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 32, 6, 818-830 (2013) · doi:10.1109/TCAD.2013.2244643
[25] NIST: Federal information processing standards publication 202 (2015). See also the Wikipedia entry http://en.wikipedia.org/wiki/SHA-3
[26] Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Sponge functions. In: Ecrypt Hash Workshop 2007, May 2007
[27] Bennett, CH, Logical reversibility of computation, IBM J. Res. Dev., 17, 525-532 (1973) · Zbl 0267.68024 · doi:10.1147/rd.176.0525
[28] Bennett, CH, Time/space trade-offs for reversible computation, SIAM J. Comput., 18, 766-776 (1989) · Zbl 0676.68010 · doi:10.1137/0218053
[29] Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: KeccakTools software, April 2012. http://keccak.noekeon.org/
[30] Amy, M., Parent, A., Roetteler, M.: ReVerC software, September 2016. https://github.com/msr-quarc/ReVerC
[31] Amy, M., Roetteler, M., Svore, K.M.: Verified compilation of space-efficient reversible circuits. arXiv preprint arXiv:1603.01635 (2016) · Zbl 1494.68045
[32] Bravyi, S.; Kitaev, A., Universal quantum computation with ideal Clifford gates and noisy Ancillas, Phys. Rev. A, 71, 022316 (2005) · Zbl 1227.81113 · doi:10.1103/PhysRevA.71.022316
[33] Fowler, A.G., Devitt, S.J., Jones, C.: Surface code implementation of block code state distillation. Scientific Reports 3, 1939 EP - (2013). doi:10.1038/srep.01939
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.