PaperlayerView exact revision on arXiv

Source-linked AI summary

Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes

Vlad Gheorghiu, Michele Mosca

arXiv:1902.02332v2quant-ph

TL;DR

The paper addresses the need for realistic resource estimates for quantum attacks on symmetric, hash-based, and public-key cryptography. It combines optimized attack circuits with fault-tolerant resource modeling and reports benchmark estimates spanning algorithmic, circuit, and hardware assumptions. The results provide security estimates for symmetric and hash schemes and space-time comparisons for RSA and ECC, while highlighting remaining alternative attack models and future fault-tolerance improvements.

  • Problem

    Real-world quantum-cryptanalysis impact depends on estimating attack resources in addition to tracking fault-tolerant quantum-computer development.

    Source: §IX · pp. 17–18

  • Method

    The paper models optimized attacks through logical circuits and surface-code fault tolerance, including parallelized Grover search, lattice surgery, and physical-error assumptions.

    Source: §I · p. 2, A. Symmetric cryptography and hash… · p. 3, §IX · p. 18

  • Results

    The study computes security parameters, wall times, and physical footprints for symmetric and hash primitives, and space-time resource estimates for RSA and ECC.

    Source: §IX · pp. 17–18

  • Takeaways & Limitations

    The estimates provide benchmarks for gauging cryptographic vulnerability and for measuring the impact of future advances in quantum algorithms, circuit optimization, and fault tolerance.

    Source: §IX · p. 18

    Some superposition-based attacks on symmetric schemes are not practical in most realistic instances, and their results can depend heavily on the nonlinear system’s condition number.

    Source: §IX · p. 17

Abstract

from arXiv · show

Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.

I. INTRODUCTION

The paper frames quantum attacks across cryptographic layers, contrasting Grover-based weakening of symmetric and hash schemes with Shor-based breaks of RSA and ECC. It develops resource estimates that incorporate fault-tolerant implementation costs, parallel search, and recent error-correction techniques.

I. INTRODUCTION

  • Grover’s algorithm gives quadratic speedup for symmetric and hash-function search, whereas Shor’s algorithm completely breaks factoring- and discrete-log-based asymmetric schemes.Grover uses O(sqrt(N)) evaluations versus order N for comparable classical black-box search.Source: §I · p. 2
  • Fault-tolerant execution maps logical circuits to surface-code measurement cycles, with T gates dominating resource costs compared with Clifford gates.Magic-state distillation is required for non-Clifford gates and introduces substantial overhead.Source: §I · p. 2
  • Lattice-surgery techniques reduce the spatial overhead of implementing T gates by approximately a factor of 5 while modestly improving runtime.The comparison is with surface-code defects and braiding techniques.Source: §I · p. 2
  • The analysis estimates symmetric and hash-function security under parallelized Grover attacks, including time-space trade-offs down to the fault-tolerant layer.Parallel processors reduce search depth less ideally than classical processors, motivating explicit resource accounting.Source: §I · p. 2
  • The paper evaluates AES, SHA, Bitcoin’s proof of work, RSA, and ECC, then summarizes findings and compares public-key schemes using resource estimates.The study also considers Grover search with a trivial-cost oracle to bound the effect of further function-circuit optimization.Source: §I · p. 2

II. METHODOLOGY

The methodology propagates assumptions from quantum algorithms through circuit and fault-tolerance layers to physical resource estimates. It evaluates parallel Grover search using surface-code architectures, varying physical error rates and separating logical, fault-tolerant, and oracle costs.

II. METHODOLOGY

  • The resource-estimation methodology is modular across layers from high-level algorithms to physical hardware, allowing layer-specific assumptions and improvements to be evaluated.The approach follows the earlier methodology described in.Source: Figure 1 · p. 3, A. Symmetric cryptography and hash… · p. 3
  • The analysis assumes surface-code fault tolerance with Reed–Muller distillation and varies physical gate error rates from 10^-4 to 10^-7.Defect-and-braiding methods are used for symmetric and hash-based schemes because lattice surgery mainly reduces spatial overhead.Source: A. Symmetric cryptography and hash… · p. 3
  • Parallel Grover analysis counts approximately ⌊π2^(N/2)/(2K)⌋ Grover iterations across K processors, with each oracle call using two reversible-function evaluations and a comparison circuit.The search space is partitioned into independent parts for parallel quantum searches.Source: A. Symmetric cryptography and hash… · p. 3
  • The plots compare surface-code cycles against theoretical lower bounds for black-box and ideal-gate oracles, isolating logical and fault-tolerant overheads.Additional plots track wall time, per-processor footprint, and total footprint as processor count changes.Source: A. Symmetric cryptography and hash… · pp. 3–4
  • The methodology covers AES, SHA-256, SHA3-256, Bitcoin’s hash function, and trivial-oracle Grover searches.Source: A. Symmetric cryptography and hash… · p. 4
  • Total physical footprint can increase slightly with more processors because lower code distances and parallel magic-state factories offset parallelization benefits.Total time per CPU remains monotonically decreasing as processors increase.Source: A. Symmetric cryptography and hash… · p. 4

B. Public-key cryptography

For RSA and ECC, the paper combines optimized logical attack circuits with lattice-surgery resource estimation to characterize space-time trade-offs. It fits these trade-offs analytically under alternative physical error rates and cycle-time assumptions.

B. Public-key cryptography

  • The public-key analysis uses optimized logical circuits for RSA and ECC and estimates their physical footprints with lattice-surgery techniques.The analysis includes memory required for magic-state distillation in the total footprint.Source: B. Public-key cryptography · p. 4
  • RSA and ECC resource estimates are plotted as space-time trade-offs and fitted with third-degree polynomials that achieve R^2 greater than 0.997.The fits provide a closed-form relation between attack time and required qubits.Source: B. Public-key cryptography · p. 4
  • The fitted relation uses y as log2 qubits and x as log2 attack time in seconds, enabling estimates of qubits required for a target attack duration.Source: B. Public-key cryptography · p. 4
  • The resource model assumes a 200ns surface-code cycle and compares physical gate error rates of 10^-3 and 10^-5.Changing the cycle time scales computation time linearly; the lower error rate is more conservative for cybersecurity.Source: B. Public-key cryptography · p. 4

III. SYMMETRIC CIPHERS

The paper analyzes AES-128 against parallel Grover attacks using optimized logical circuits and compares idealized query costs with fault-tolerant overhead. The figures report surface cycles, time, and physical-qubit footprint as processor counts vary.

A. AES-128

  • The AES-128 analysis reports required surface clock cycles, time per processor, and physical-qubit footprint as functions of processor count.Source: Figure 3 · p. 5, Figure 4 · p. 5, Figure 5 · p. 5
  • At 2^50 parallel processors, the optimized AES-128 circuit requires about 2^63 gate calls without physical errors, versus about 2^38 oracle calls for a trivial-cost implementation.Source: A. AES-128 · p. 5
  • With physical error rate 10^-7 and fault-tolerant error correction, the optimized implementation requires around 2^76 surface code cycles per processor.Source: A. AES-128 · p. 5
  • Over 280 parallel quantum searches would be needed to break AES-128 in one year under the stated assumptions.Source: Figure 4 · p. 5

B. AES-192

The AES-192 subsection presents resource estimates across processor counts, while the supplied hash-function passage identifies optimized logical circuits as the basis for the SHA-256 and SHA3-256 analyses.

B. AES-192

IV. HASH FUNCTIONS

  • The supplied hash-function passage states that SHA-256 and SHA3-256 analyses use highly optimized logical circuits produced in.Source: §IV · p. 7

A. SHA-256

The supplied material presents SHA-256 and Bitcoin resource plots across processor counts, including time and physical footprint, and describes Bitcoin’s proof-of-work as repeated SHA-256 hashing.

A. SHA-256

V. BITCOIN

  • Bitcoin’s proof-of-work seeks a hash pre-image beginning with a dynamically adjusted number of zeros, with the network targeting an average solution time of 10 minutes.Source: §V · p. 8
  • Bitcoin uses H(x) := SHA-256(SHA-256(x)) as its cryptographic hash function.Source: §V · p. 8
  • Bitcoin resource plots measure surface clock cycles, time per processor, per-processor physical footprint, and total physical footprint across processor counts.Source: Figure 23 · p. 9, Figure 24 · p. 9, Figure 25 · p. 9
  • Trivial-cost oracle analyses bound how much further optimized AES and SHA implementations could improve quantum cryptanalysis estimates.Source: §V · p. 9
  • Additional Grover plots evaluate a trivial oracle for a search space of size 256, showing resource requirements as functions of processor count.Source: Figure 27 · p. 9, Figure 28 · p. 10, Figure 29 · p. 10

B. Searching space of size 264

The supplied figures characterize Grover search over a space of size 2^64 as processor parallelism changes, reporting computational time and physical-resource requirements.

B. Searching space of size 2^64

  • For a search space of size 2^64, the figures report required surface clock cycles per processor as a function of processor count.Source: Figure 31 · p. 10
  • For a search space of size 2^64, the figures report required time per processor as a function of processor count.Source: Figure 32 · p. 10
  • For a search space of size 2^64, the figures report per-processor and total physical-qubit footprints as processor count varies.Source: Figure 33 · p. 10, Figure 34 · p. 11

D. Searching space of size 2256

This section presents resource tradeoffs for Grover search over a space of size 2^256 and RSA-1024 under fault-tolerant assumptions. RSA-1024 can be evaluated through space/time tradeoffs, including a one-day attack estimate at physical error rate 10^-5.

D. Searching space of size 2^256

  • Grover-search costs are characterized by surface-clock cycles, time, per-processor footprint, and total physical footprint as processor count varies.The figures use logarithmic processor-count scales; total qubits are not correlated across processors.Source: Figure 39 · p. 12, Figure 40 · p. 12, Figure 41 · p. 12

VII. RSA SCHEMES

A. RSA-1024

  • 2.14 × 10^6 physical qubits are required to break RSA-1024 in one day at physical error rate 10^-5.The estimate uses 3.01 × 10^11 T gates, 2050 logical qubits, and 2.93 × 10^13 surface-code cycles; the classical security parameter is approximately 80 bits.Source: Figure 44 · p. 13

B. RSA-2048

The RSA sections report one-day space/time tradeoffs for RSA-2048 through RSA-15360 at physical error rates 10^-3 and 10^-5. The estimates include physical-qubit, T-gate, logical-qubit, surface-code-cycle, and classical-security parameters.

B. RSA-2048

  • 9.78 × 10^6 physical qubits are required to break RSA-2048 in one day at physical error rate 10^-5.The estimate uses 2.41 × 10^12 T gates, 4098 logical qubits, 2.35 × 10^14 surface-code cycles, and approximately 112 classical security bits.Source: Figure 46

C. RSA-3072

  • 2.55 × 10^7 physical qubits are required to break RSA-3072 in one day at physical error rate 10^-5.The estimate uses 8.12 × 10^12 T gates, 6146 logical qubits, 7.91 × 10^14 surface-code cycles, and approximately 128 classical security bits.Source: Figure 48 · p. 13

D. RSA-4096

  • 5.70 × 10^7 physical qubits are required to break RSA-4096 in one day at physical error rate 10^-5.The estimate uses 1.92 × 10^13 T gates, 8194 logical qubits, 1.88 × 10^15 surface-code cycles, and approximately 156 classical security bits.Source: Figure 50 · p. 14

E. RSA-7680

  • 7.41 × 10^9 physical qubits are required to break RSA-7680 in one day at physical error rate 10^-5.The estimate uses 1.27 × 10^14 T gates, 15362 logical qubits, 2.47 × 10^16 surface-code cycles, and approximately 192 classical security bits.Source: Figure 52 · p. 14

F. RSA-15360

  • 7.64 × 10^10 physical qubits are required to break RSA-15360 in one day at physical error rate 10^-5.The estimate uses 1.01 × 10^15 T gates, 30722 logical qubits, 1.98 × 10^17 surface-code cycles, and approximately 256 classical security bits.Source: Figure 54 · p. 15

VIII. ELLIPTIC CURVE SCHEMES

The elliptic-curve analysis estimates space/time tradeoffs for NIST curves using logical circuits from [14], with separate results for physical error rates 10^-3 and 10^-5. The covered curves span P-160 through P-224 and report one-day attack resources.

VIII. ELLIPTIC CURVE SCHEMES

  • The analysis computes elliptic-curve attack tradeoffs by plotting points and fitting third-degree polynomials for physical error rates 10^-3 and 10^-5.The schemes include NIST P-160, P-192, P-224, P-256, P-384, and P-521, using logical circuits from [14].Source: §VIII · p. 15

A. NIST P-160

  • 1.81 × 10^7 physical qubits are reported for a one-day NIST P-160 attack at physical error rate 10^-3.The estimate uses 2.08 × 10^11 T gates, 1466 logical qubits, 4.05 × 10^13 surface-code cycles, and 80 classical security bits.Source: Figure 55 · p. 15, A. NIST P-160 · p. 15

B. NIST P-192

  • 2.18 × 10^6 physical qubits are required to break NIST P-192 in one day at physical error rate 10^-5.The estimate uses 3.71 × 10^11 T gates, 1754 logical qubits, 3.62 × 10^13 surface-code cycles, and 96 classical security bits.Source: Figure 58

C. NIST P-224

  • 3.24 × 10^6 physical qubits are reported for a one-day NIST P-224 attack at physical error rate 10^-5.The estimate uses 5.90 × 10^11 T gates, 2042 logical qubits, 5.75 × 10^13 surface-code cycles, and 112 classical security bits.Source: Figure 60 · p. 16, C. NIST P-224 · p. 16

D. NIST P-256

The higher-security elliptic-curve sections estimate one-day attack resources for NIST P-256, P-384, and P-521 at physical error rates 10^-3 and 10^-5. Each estimate reports physical-qubit, T-gate, logical-qubit, and surface-code-cycle requirements.

D. NIST P-256

  • 4.64 × 10^6 physical qubits are reported for a one-day NIST P-256 attack at physical error rate 10^-5.The estimate uses 8.82 × 10^11 T gates, 2330 logical qubits, 8.60 × 10^13 surface-code cycles, and 128 classical security bits.Source: Figure 62 · p. 16, D. NIST P-256 · p. 16

E. NIST P-384

  • 1.28 × 10^7 physical qubits are reported for a one-day NIST P-384 attack at physical error rate 10^-5.The estimate uses 3.16 × 10^12 T gates, 3484 logical qubits, 3.08 × 10^14 surface-code cycles, and 192 classical security bits.Source: Figure 64 · p. 17, E. NIST P-384 · p. 17

F. NIST P-521

  • 2.30 × 10^7 physical qubits are reported for a one-day NIST P-521 attack at physical error rate 10^-5.The estimate uses 7.98 × 10^12 T gates, 4719 logical qubits, 7.78 × 10^14 surface-code cycles, and 256 classical security bits.Source: Figure 66 · p. 17, F. NIST P-521 · p. 17

IX. SUMMARY AND CONCLUSIONS

The paper benchmarks quantum attack resources for symmetric, hash-based, and public-key cryptography using parallelized Grover attacks and fault-tolerant resource estimates. It reports security parameters and physical costs while highlighting assumptions about attack optimality and future fault-tolerance advances.

Symmetric and hash-based cryptography

  • The analysis computes quantum security parameters for widely used symmetric ciphers and hash functions under parallelized Grover search and surface-code fault tolerance.The security parameter is summarized in Table I under a conservative physical error rate of pg = 10−4.Source: §IX · pp. 17–18, Table I · p. 18

Assumptions and limitations

  • The symmetric and hash-function estimates assume black-box brute-force search is essentially optimal, although superposition attacks could provide advantages when their nonlinear-system condition numbers are sufficiently small.The practicality of such attacks remains unclear because the relevant condition numbers are generally unknown and large-scale quantum experiments are unavailable.Source: §IX · p. 17

Public-key cryptography

  • RSA and ECC analyses estimate quantum attack resources using surface-code lattice surgery, with RSA requiring more resources than ECC at the same classical security level.The RSA and ECC estimates include physical footprint, T gates, surface-code cycles, and classical security parameters for 24-hour attacks.Source: §IX · p. 18, Table II · p. 18, Table III · p. 18

Implications

  • The benchmark provides state-of-the-art snapshots of realistic quantum attack costs and a reference point for measuring improvements in algorithms, circuit synthesis, fault tolerance, and physical error rates.The estimates assume surface-code methods and span potential physical error rates, reflecting the resource intensity of the fault-tolerant layer.Source: §IX · p. 18

Related papers

Loading 1902.02332v2…