CoChat
Sign Up
Cited by 128Quantum Computing Algorithms and ArchitectureCryptographic Implementations and SecurityQuantum Information and Cryptography

Estimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3

Open access
Amy, Matthew, Di Matteo, Olivia, Gheorghiu, Vlad, Mosca, Michele, Parent, Alex, Schanck, John·2017·Lecture Notes in Computer Science
DOI 10.1007/978-3-319-69453-5_18
Open this paper in CoChat — free accountOpen PDF

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/978-3-319-69453-5_18

Cites

7 of 7 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Amy et al.'s SHA-2 and SHA-3 pre-image search resource estimate did not consider random-like behavior of the SHA function and assumed that a unique pre-image of a given hash exists.

    “One point we would like to address in the work is that random-like behavior of SHA function was not considered.It is assumed in the paper that the unique pre-image of a given hash exists.”

    From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [5]

    Section 2 (p. 3) models the search using a one-way permutation, which has a unique pre-image for each output. But its footnote explicitly considers that a length-restricted hash may fail to be injective and says this should not significantly affect Grover's success probability. The claim therefore overstates the extent to which non-unique pre-images were ignored. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • In Amy et al.'s design, Ch and Maj require one and two Toffoli gates, respectively.

    “Ch and Maj are bit-wise operations that do require Toffoli gates.We adopt Amy et al.'s design where Ch and Maj require one and two Toffoli gates, respectively.See Figs. 4 and 5 in [5].”

    From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [5]

  • The ratio of physical execution time in all Clifford gates to all T gates is about 0.0001 in breaking SHA-256.

    “Similar analysis that T gates are much more expansive than all the other gates can be found in [5], where the ratio of physical execution time in all Clifford gates to all T gates is about 0.0001 in breaking SHA-256.”

    From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [5]

  • The quantum cost of attacking SHA-3 is more expansive than that of SHA-2, based on [5] and further improvement made in the SHA-2 circuit in Sect. 6.

    “We concluded that quantum cost of attacking SHA-3 is more expansive than that of SHA-2, based on[5] and further improvement we have made in SHA-2 circuit in Sect.6.”

    From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [5]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 17

  1. [2]2. Boneh, D., Lipton, R.J.: Quantum Cryptanalysis of Hidden Linear Functions. In: Coppersmith, D. (ed.) Advances in Cryptology - CRYPTO'95, pp. 424-437. No. 963 in Lecture Notes in Computer Science, Springer Berlin Heidelberg (Aug 1995)
  2. [4]4. Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4-5), 493-505 (1998), http://dx.doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P · DOI
  3. [5]5. Gilles, B., Peter, H., Michele, M., Alain, T.: Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics (305), 53-74 (2002), e-print arXiv:quant-ph/0005055 · arXiv
  4. [8]8. Lenstra, A.K.: Handbook of Information Security, chap. Key Lengths. Wiley (2004)
  5. [9]9. Lenstra, A.K., Verheul, E.R.: Selecting cryptographic key sizes. Journal of Cryptology 14(4), 255-293 (Aug 2001)
  6. [11]11. Amy, M., Maslov, D., Mosca, M.: Polynomial-time t-depth optimization of Clifford+T circuits via matroid partitioning. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 33(10), 1476-1489 (Oct 2014)
  7. [14]14. Fowler, A.G., Whiteside, A.C., Hollenberg, L.C.L.: Towards practical classical processing for the surface code: Timing analysis. Physical Review A 86(4), 042313 (Oct 2012), http://link.aps.org/doi/10.1103/PhysRevA.86.042313 · DOI
  8. [15]15. Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N.: Surface codes: Towards practical large-scale quantum computation. Physical Review A 86(3), 032324 (Sep 2012), http://link.aps.org/doi/10.1103/PhysRevA.86.032324 · DOI · Paper page
  9. [16]16. Fowler, A.G., Whiteside, A.C., Hollenberg, L.C.L.: Towards Practical Classical Processing for the Surface Code. Physical Review Letters 108(18), 180501 (May 2012), http://link.aps.org/doi/10.1103/PhysRevLett.108.180501 · DOI
  10. [17]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] (Jul 2013), http://arxiv.org/abs/1307.1740 , arXiv: 1307.1740 · arXiv
  11. [20]20. Selinger, P.: Quantum circuits of T -depth one. Phys. Rev. A 87, 042302 (Apr 2013), http://link.aps.org/doi/10.1103/PhysRevA.87.042302 · DOI
  12. [22]22. Parent, A., Roetteler, M., Svore, K.M.: Reversible circuit compilation with space constraints. arXiv preprint arXiv:1510.00377 (2015), http://arxiv.org/abs/1510.00377 · arXiv
  13. [23]23. Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/0410184 (2004), http://arxiv.org/abs/quant-ph/0410184 · arXiv
  14. [26]26. Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Sponge functions. Ecrypt Hash Workshop 2007 (May 2007)
  15. [27]27. Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development 17, 525-532 (1973)
  16. [31]31. Amy, M., Roetteler, M., Svore, K.M.: Verified compilation of spaceefficient reversible circuits. arXiv preprint arXiv:1603.01635 (2016), http://arxiv.org/abs/1603.01635 · arXiv
  17. [33]33. Fowler, A.G., Devitt, S.J., Jones, C.: Surface code implementation of block code state distillation. Scientific Reports 3, 1939 EP -(06 2013), http://dx.doi.org/10.1038/srep01939 · DOI · Paper page

Cited by

Sorted by citations

Authors
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., & Schanck, J.
Affiliations
  • University of Waterloo (CA)
  • Canadian Institute for Advanced Research (CA)
Corresponding author
Gheorghiu, Vlad
ORCID
Venue
Lecture Notes in Computer Science
Publisher
Springer International Publishing
Published
2017
Pages
317-337
ISSN
  • 0302-9743 (ISSN-L)
  • 1611-3349
DOI
10.1007/978-3-319-69453-5_18
OpenAlex
W2335111715
Cited by
128
References
7
Citations by year
2026: 11 · 2025: 12 · 2024: 10 · 2023: 6 · 2022: 24 · 2021: 5 · 2020: 38 · 2019: 7 · 2018: 10 · 2017: 4 · 2016: 1
FWCI
7.22
Type
conference paper
Language
en
Open access
Licence
Locations
  • Lecture notes in computer science (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Canadian Institute for Advanced Research
  • Government of Canada
  • Natural Sciences and Engineering Research Council of Canada
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
Grover's algorithm, SHA-2, SHA-3, hash functions, surface code, fault-tolerant quantum computing, cost model, logical qubits, circuit depth, quantum advantage, SHA-256, SHA3-256

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review