PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, John Schanck

arXiv:1603.09383v3quant-ph

TL;DR

The paper asks how much realistic fault-tolerant execution changes the cost of quantum pre-image attacks beyond query counts. It estimates SHA-2 and SHA-3 attack costs using optimized reversible circuits in a surface-code model. Both attacks are estimated at approximately 2^166 basic operations when classical processing is included.

  • Problem

    Query-based comparisons assume quantum and classical hash invocations have equal cost, an assumption that realistic quantum-computer designs call into question.

    Source: §1 · p. 2

  • Method

    The authors optimize reversible SHA-256 and SHA3-256 circuits and estimate their resources on a fault-tolerant surface-code architecture.

    Source: §8 · p. 18

  • Results

    For both SHA-256 and SHA3-256, total cost including classical processing is approximately 2^166 basic operations.

    Source: §8 · p. 18

  • Takeaways & Limitations

    The proposed cost model includes classical processing for quantum error correction to support direct, though architecture-dependent, classical–quantum comparisons.

    Source: §1 · p. 2, §8 · p. 18

    The estimates are not lower bounds and depend on assumptions including individually optimized oracle components, surface-code fault tolerance, and a per-gate error rate of about 10^-5.

    Source: §8 · pp. 18–19

Abstract

from arXiv · show

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.

1 Introduction

The introduction motivates assessing quantum pre-image attacks beyond query counts, since realistic fault-tolerant execution adds overhead. The paper estimates SHA-2 and SHA-3 attack costs using reversible circuits and a surface-code model.

1 Introduction

  • Grover’s algorithm reduces the query complexity of black-box search quadratically, while Shor’s algorithm threatens cryptosystems based on the abelian hidden subgroup problem.The introduction notes that Grover’s search requires a square-root number of queries [5].Source: §1 · pp. 1–2
  • Query counts alone assume quantum and classical hash invocations cost the same, an assumption realistic quantum-computer designs call into question.The paper argues that a useful comparison should account for classical processing required for quantum error correction.Source: §1 · p. 2
  • The study estimates pre-image attack costs for SHA-2 and SHA-3 on a surface-code fault-tolerant architecture, using reversible Clifford+T circuits optimized for T-count and T-depth.It estimates the additional fault-tolerant resources needed to produce ancillary states consumed by T gates.Source: §1 · pp. 2–3
  • The cost model focuses on logical-qubit count and circuit depth in surface-code cycles, with analysis divided into layers so architectural assumptions can be evaluated separately.The paper combines elements of prior analyses of Grover-based AES recovery [12] and surface-code implementation of Shor’s algorithm [13].Source: §1 · p. 3

2 Pre-image search via Grover’s algorithm

This section frames pre-image search as finding an input that maps to a target output, and describes Grover’s algorithm as a way to reduce query needs. Its iteration combines an oracle with a diffusion operator.

2 Pre-image search via Grover’s algorithm

  • A pre-image of y is an input x satisfying f(x) = y; in the worst case, finding one requires systematically searching the input space.A function requiring such a search is called one-way; a bijective one-way function is a one-way permutation.Source: §2 · p. 3
  • Classical search needs on the order of 2^k queries, whereas Grover’s algorithm can find a pre-image with 2^(k/2) queries [3].Counting queries alone omits potentially significant overhead from executing the function on a quantum computer.Source: §2 · p. 3
  • Each Grover iteration applies an oracle that calls reversible f twice and checks whether f(x) = y, followed by a diffusion operator that amplifies solutions.The diffusion operator uses single-qubit gates and one k-fold controlled-NOT, and is expected to cost less than the oracle.Source: §2 · p. 4

3 A cost metric for quantum computation

The section proposes a logical-qubit-cycle cost to compare classical and quantum computation, motivated by the classical processing needed for surface-code error correction. Its estimates rely on architectural assumptions.

3 A cost metric for quantum computation

  • Surface-code error detection and correction requires classical processing each cycle, and error-correction overhead is identified as the majority of quantum-computation overhead under realistic architectural assumptions.The paper uses this processing as a partial basis for comparing classical and quantum costs.Source: §3 · pp. 4–5
  • The cost comparison assumes large quantum computations can be approximated by surface-code implementations and that an L × L logical-qubit grid has a corresponding mesh of classical processors.The processor mesh uses one ASIC per block of Ca × Ca physical qubits; the model assumes Ca = n, where n is the physical-qubit grid width per logical qubit.Source: §3 · pp. 5–6
  • The model assumes each ASIC performs a constant number of operations per cycle and equates a cycle’s temporal cost with a hash invocation; the paper notes classical processing may limit quantum-computer speed.The assumed processor operation cost draws on an estimate of O(Ca^2) operations per error-correction round and a heuristic that communication overhead is independent of L.Source: §3 · pp. 4, 6
  • The cost of a quantum computation using ℓ logical qubits for σ surface-code cycles is ℓ·σ hash-function invocations in the paper’s comparison metric.The model equates the temporal cost of one surface-code cycle with one hash-function invocation.Source: §3 · p. 6

4 Intrinsic cost of Grover search

The section characterizes finite-cost Grover search through circuit overhead and advantage, rather than relying only on its asymptotic quadratic query improvement. It gives a lower-bound overhead and an AES circuit example.

4 Intrinsic cost of Grover search

  • The circuit’s advantage is k/C, where k is the searched space’s bit size and 2^C is the adversary’s allowed cost; overhead is denoted v.For fixed v, the ratio k/C tends to 2 as C grows, but the analysis focuses on non-asymptotic advantages.Source: §4 · p. 7
  • For k ≤ 256, the paper gives v ≥ 1.375 as a strict upper-bound basis for Grover advantage in its cost model, before some magic-state-distillation spatial overhead.The lower bound accounts for input representation and at least log2(k) Clifford+T depth, even when a k-fold controlled-NOT dominates.Source: §4 · p. 7
  • The AES-256 circuit from [12] has depth 130929 and 1336 logical qubits, yielding reversible-layer overhead v ≈ 3.423.The paper presents this as a practical overhead example beyond the lower bound.Source: §4 · p. 7

5 Reversible implementation of a SHA-256 oracle

The SHA-256 oracle is built as a reversible implementation of the 512-bit, one-block SHA-256 function, then optimized as a Clifford+T circuit. The optimized circuit has depth 830720 and 2402 logical qubits, with reversible-layer overhead v ≈3.862.

5 Reversible implementation of a SHA-256 oracle

  • The implementation targets SHA-256 on a 512-bit, one-block message, stretching the message before running the round function 64 times.The stretch function runs 48 iterations and can be parallelized with the rounds without adding overall depth.Source: §5 · p. 7, Table 1 · p. 10

5.1 Reversible implementation

  • Each SHA-256 round is made reversible using in-place adders and CNOT-only Σ blocks, avoiding additional space accumulation across rounds.The in-place adders map (a, b, 0) to (a, a+b, 0), using one ancilla bit.Source: §5.1 · p. 9

5.2 Quantum implementation

  • The round circuit is selected from space–gate trade-offs, then converted to Clifford+T and optimized with T-par, which removes many T-gates.The adder construction makes every Toffoli share two controls with another Toffoli, enabling the reported T-gate removal.Source: §5.1 · p. 9, §5.2 · p. 9
  • Depth 830720 and 2402 logical qubits give the optimized SHA-256 circuit a reversible-layer overhead of v ≈3.862.The depth and qubit count are each approximately 2^ values as reported in the passage.Source: §5.2 · p. 9

6 Reversible implementation of a SHA3-256 oracle

The SHA-3 algorithms use the Keccak-p[1600, 24] permutation within a sponge construction. Under the stated pre-image-length assumption, the SHA3-256 oracle needs one permutation application.

6 Reversible implementation of a SHA3-256 oracle

  • SHA-3 pads and chunks the message, absorbs each chunk into the state with a Keccak-p[1600, 24] permutation, then truncates the hash output.The standard includes SHA-3 variants with different output lengths and SHAKE variants with different padding.Source: §6 · p. 10
  • SHAKE uses a different padding form from SHA-3 but otherwise follows the same procedure.Source: §6 · p. 10
  • For a pre-image of length k, the padded message has length 1600 − 2k, so the algorithm applies Keccak-p[1600, 24] once.Source: §6 · p. 11

The Keccak permutation

Keccak-p is an invertible, multi-round permutation on a 5-by-5 array of lanes, built from five component functions. The implementation performs rounds in place, and its optimized SHA3-256 reversible circuit has 3200 logical qubits and depth 11040.

The Keccak permutation

  • Keccak-p[b, r] composes r invertible rounds on a 5-by-5 array of lanes, with b = 25w; SHA-3 uses Keccak-p[1600, 24] with 64-bit lanes.Source: The Keccak permutation · p. 11

6.1 Reversible implementation

  • The in-place implementation uses one temporary input-sized register instead of adding 1600 bits per round, and returns that register to zero after each round.The component functions are invertible; ρ and π are implemented by re-indexing rather than physical swaps.Source: §6.1 · p. 12
  • Per lane width w, θ uses 275w CNOTs and θ⁻¹ uses 125w·j CNOTs; χ uses 50w CNOTs and 25w Toffolis, while χ⁻¹ uses 85w CNOTs and 30w Toffolis.For b = 1600, j is 170; χ and χ⁻¹ are arranged in 5 and 6 parallel stages, respectively.Source: §6.1 · p. 12
  • The final reversible circuit uses 3200 qubits, 33269760 CNOT gates, and 84480 Toffoli gates arranged in 264 parallel stages.Source: §6.1 · p. 12

6.2 Quantum implementation

  • The Clifford+T implementation optimizes χ and χ⁻¹, the only nonlinear operations, and the reported resources are identical across SHA-3 output sizes.Table 2 reports component counts and the full SHA3-256 oracle resource counts.Source: §6.2 · p. 13, Table 2 · p. 13
  • The SHA3-256 reversible circuit has depth 11040, 3200 logical qubits, and reversible-layer overhead v ≈3.134.Source: §6.2 · p. 13

7 Fault-tolerant cost

The section estimates fault-tolerant Grover costs by accounting for magic-state distillation and surface-code resources. It gives SHA-256 and SHA3-256 resource estimates, including their distinct distillation demands.

7 Fault-tolerant cost

  • The estimates use Reed-Muller 15-to-1 distillation and assume pin = 10^-4, pg = 10^-5, and ε = 1; both circuits require three rounds.For SHA-256, the round distances are d1 = 33, d2 = 13, and d3 = 7.Source: §7 · p. 14, §7.1 · p. 15, §7.2 · p. 17

7.1 SHA-256

  • For a quantum attack against SHA-256, total cost is the product of the total logical-qubit count, including magic-state distillation qubits, and the number of code cycles.Source: §7.1 · pp. 16–17

7 Fault-tolerant cost

  • The cost model accounts for logical qubits, including distillation resources, and total depth in surface-code cycles.The analysis treats magic-state production as the limiting step for both hash circuits.Source: §7.1 · pp. 16–17, §7.2 · p. 17

7.2 SHA3-256

  • For SHA3-256, roughly 294 parallel distillation factories compute 1,175 magic states in 530 code cycles, increasing required state-distillation resources to 1.63 × 10^8 physical qubits.Embedding the entire algorithm in a surface code requires distance 44 and 1.94 × 10^7 physical qubits.Source: §7.2 · p. 17

8 Conclusions and open questions

The paper estimates Grover-based pre-image attacks on SHA-256 and SHA3-256 using a fault-tolerant surface-code architecture. Its estimates depend on assumptions and are not lower bounds.

8 Conclusions and open questions

  • SHA-256 requires approximately 2153.8 surface code cycles, while SHA3-256 requires approximately 2146.5; both attacks cost approximately 2166 basic operations when classical processing is included.The authors estimate the cost of quantum pre-image attacks using Grover’s algorithm and a fault-tolerant surface-code architecture.Source: §8 · p. 18
  • The estimates are not lower bounds because the SHA oracle components were optimized individually, surface code was assumed, and the per-gate error rate was optimistic.The authors note that dedicated optimization or other error-correction schemes may yield better estimates.Source: §8 · p. 18
  • Improving the listed assumptions would lower estimated operations, while the decrease in security bits would likely be limited.The considered per-gate error rate was about 10^-5, described as the limit of current quantum hardware.Source: §8 · p. 19

A Tables

The appendix tables describe quantum-search advantage and the crossover between classical and quantum search costs after overhead is included.

A Tables

  • Table 4 reports the advantage k/C for quantum pre-image search at cost 2^C = k a 2^(k/2); entries below 1 indicate quantum search is worse than classical search.The table caption defines the reported advantage and the cost regime it covers.Source: Table 4 · p. 21
  • The displayed sequence 5, 16, 30, 44, 59 has no stated row or column interpretation in the supplied table text.Source: A Tables · p. 21
  • Table 5 gives the k value at which classical and quantum search costs are equal after accounting for quantum-search overhead ka.Source: Table 5 · p. 21

B Parallel quantum search

The appendix compares classical and quantum parallel search through their time-area costs. Parallel quantum search reduces time per processor but increases area, and its total cost is greater than sequential quantum search.

B Parallel quantum search

  • Classical search costs 2^k invocations of g for any of 2^t processors, while its time-area pair can be reported as (2^(k-t), 2^t).Each processor fixes t input bits and searches the remaining k−t bits.Source: B Parallel quantum search · p. 21
  • Parallel quantum search across 2^t processors reduces temporal cost per processor by 2^(t/2) and increases area by 2^t, yielding cost (k a 2^((k−t)/2), k b 2^t).Fixing t input bits does not change Grover-iteration overhead.Source: B Parallel quantum search · p. 21
  • Parallel quantum strategies have strictly greater cost than sequential quantum search.Source: B Parallel quantum search · p. 21
Loading 1603.09383v3…