PaperlayerView exact revision on arXiv

Source-linked AI summary

Implementing Grover oracles for quantum key search on AES and LowMC

Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia

arXiv:1910.01700v1quant-phcs.ET

TL;DR

The paper studies concrete quantum key-search costs for block ciphers when Grover-oracle depth is bounded, addressing limitations of qubit-minimizing AES analyses. It implements and optimizes full AES and LowMC Grover oracles, finding lower costs in gate count and depth-times-width and reducing AES estimates for NIST security categories by 11–13 bits.

  • Problem

    Concrete Grover-oracle evaluation costs are often ignored, although NIST security categories use AES key-search gate costs under a MAXDEPTH constraint.

  • Method

    The authors implement full AES and LowMC Grover oracles in Q# and optimize them for gate count and depth-times-width under a depth constraint rather than minimum qubit count.

  • Results

    11–13 bits of consistent G-cost reduction are obtained for quantum AES key search relative to NIST’s estimates.

  • Takeaways & Limitations

    The results provide lower AES cost estimates for NIST security categories and more precise resource estimates for AES and LowMC attacks.

  • Takeaways & Limitations

    The LowMC study uses the original design, yielding a sub-optimal circuit that could be improved by porting a more recent version.

Abstract

from arXiv · show

Grover's search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses $O(\sqrt{N})$ calls to the cipher to search a key space of size $N$. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits. In contrast, we study the cost of quantum key search attacks under a depth restriction and introduce techniques that reduce the oracle depth, even if it requires more qubits. As cases in point, we design quantum circuits for the block ciphers AES and LowMC. Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models. In NIST's post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography. As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates. To the best of our knowledge, these are the first two such full implementations and automatic resource estimations.

1 Introduction

The paper addresses the concrete cost of quantum key search under depth constraints by implementing and optimizing full Grover oracles for AES and LowMC. These designs prioritize lower gate count and depth-times-width cost over minimum qubit count, yielding shallower circuits and lower AES estimates relevant to NIST security categories.

  • Motivation: Grover key search costs are often approximated asymptotically, while the concrete cost of evaluating the oracle is frequently ignored.This limits the precision of security estimates for symmetric primitives.
  • Motivation: NIST defines post-quantum security categories using gate costs for AES key search under a total circuit-depth bound called MAXDEPTH.Categories 1, 3, and 5 correspond to AES-128, AES-192, and AES-256, respectively.
  • Contributions: The authors implement full Grover oracles for AES and LowMC in Q#, including the block ciphers, unit tests, and automatic resource estimation.The implementations support more precise and flexible cost estimates than prior circuit analyses and enable correctness testing.
  • Optimization approach: The circuit designs minimize gate count and depth-times-width under a depth constraint rather than minimizing qubit count.The authors argue that lower depth is crucial because Grover’s algorithm does not parallelize well.
  • Results: The work reports the most shallow quantum implementation of AES proposed at the time and the first quantum implementation of LowMC.LowMC is included because it is used in the Picnic signature scheme and its implementation supports more precise security estimates.
  • Results: 11–13 bits of consistent G-cost reduction are obtained for quantum AES key search relative to NIST’s estimates.The paper presents these as new, lower estimates for defining NIST security strength categories.

2 Finding a block cipher key with Grover’s algorithm

Grover key search marks keys consistent with known plaintext-ciphertext pairs and amplifies their amplitudes through repeated oracle iterations. The section also analyzes spurious keys and shows how parallelization affects success probability and the required number of message blocks.

  • Grover’s algorithm: Grover’s algorithm searches a key space by repeatedly applying an oracle that marks solution keys and an inversion-about-the-mean operator.The oracle flips the target qubit for matching keys, which becomes a phase shift when the auxiliary qubit is prepared in the required state.
  • Key search for a block cipher: For a block cipher, the oracle marks a key exactly when it encrypts every known plaintext to its corresponding ciphertext.The Boolean predicate takes the candidate key as input and tests all r plaintext-ciphertext pairs.
  • Spurious keys: Under pseudo-randomness assumptions, a competing key matches all r ciphertexts with probability 2^-rn, and the expected number of spurious keys is (2^k − 1)2^-rn.These estimates motivate choosing enough message blocks to make the correct key unique with high probability.
  • Key search for a block cipher: A unique key is obtained with high probability when the total known plaintext length slightly exceeds the key length.Taking rn = k + 10 gives approximately 0.999 probability of uniqueness; if k is a multiple of n, r = k/n + 1 gives probability at least 1 − 2^-n.
  • Parallelization: For S = 1, 2, and 3 parallel machines, the corresponding success probabilities are approximately 1, 0.961, and 0.945.These values describe the small-S behavior of the parallelized search under the stated iteration choices.
  • Parallelization: Inner parallelization places the correct key in exactly one machine’s subset, giving near certainty of finding it while other machines cannot return it.Dividing the search space also separates spurious keys across subsets, allowing fewer message blocks when the spurious-key probability remains below the desired bound.

3 Quantum circuit design

The paper designs and evaluates reversible quantum circuits under full parallelism, depth constraints, and multiple cost models. It uses Q# implementations, automated resource estimation, and unit testing to compare circuit constructions and resource trade-offs.

  • Circuit model: Quantum circuits are modeled with Clifford+T gates under full parallelism, allowing disjoint gates to execute simultaneously.Circuit depth is assigned automatically by the Q# compiler, including possible overlap across consecutive circuits.
  • Reversible circuits for linear maps: Linear maps are implemented with CNOT networks or in-place PLU decompositions, and alternative circuits can trade width and gate count for shallower depth.Figure 1 compares circuits implementing the same linear transformation; one construction is wider and has a larger gate count but is shallower than another.
  • Circuit model: The resource analysis assumes fixed total resources and a maximum depth Dmax to make attack costs meaningful.Without such constraints, the same search could be framed using enormous parallelism or extremely long runtimes.
  • Cost metrics: Under fixed depth, width, and gate limits, minimizing parallel machines minimizes both G-cost and DW-cost, while width and gate limits become feasibility conditions.If a resource limit is loose, the oracle can use it to reduce depth and lower total cost.
  • Cost metrics: 240.2cs, 256.2cs, and 272.3cs are the minimum depths for AES-128, AES-192, and AES-256, respectively.The corresponding LowMC-128, LowMC-192, and LowMC-256 minimum depths are 241.1cs, 259.8cs, and 276.4cs.

4 A quantum circuit for AES

The AES quantum circuit is implemented in Q# with depth prioritized over width, combining optimized S-box, MixColumn, and in-place key-expansion designs. The resulting circuit estimates compare alternative components and reveal lower depth-times-width costs under depth restrictions.

  • Q# implements all three AES variants while prioritizing circuit depth over minimizing qubit width.The implementation defines gate, depth, and width costs for the AES components.
  • 4.1 S-box, ByteSub and SubByte: The BP12 S-box is ported to Q# and used for ByteSub and SubByte, with ByteSub applied state-wide and SubByte word-wide.The BP12 design is compared with reconstructed GLRS16 and BP10/LPS19 circuits.
  • 4.3 MixColumn: MixColumn is implemented either in place through PLU decomposition or out of place using Maximov’s shallower design.The in-place and out-of-place alternatives support different cost trade-offs.
  • 4.5 KeyExpansion: The key expansion works in place without ancilla qubits and reduces depth compared with storing all expanded key bits in ancillas.The circuit derives successive round-key word sets from the preceding set.
  • 4.3 MixColumn: For depth-restricted optimization, Maximov’s MixColumn gives the lower depth-times-width cost, whereas the in-place design is preferable without depth restrictions.The choice follows from the squared depth term in the depth-times-width metric.
  • 4.7 T depth.: Q# compilation exposes non-trivial parallelization, making AES-256 T-depth 25% less than the naive expectation.The effect is observed with both AND and standard-library CCNOT implementations and is supported by unit tests.

5 A quantum circuit for LowMC

The paper implements LowMC circuits for Picnic’s three parameter sets, constructing rounds from S-box, affine, key-expansion, and key-addition operations. The original LowMC design is sub-optimal, but its Grover-oracle overhead is small, especially under T-depth.

  • LowMC is a block-cipher family adopted as a core component of the Picnic signature scheme in post-quantum standardization.
  • The study uses the original LowMC design, yielding a sub-optimal circuit, but reports very small Grover-oracle overhead, particularly under T-depth.
  • The implementation targets Picnic parameter sets with key and block sizes of 128, 192, and 256 bits.
  • The LowMC S-box has an in-place depth-5 design with T-depth 3 and an out-of-place design with T-depth 1.
  • LinearLayer and key-scheduling use invertible matrices implemented through PLU decompositions, while in-place key expansion derives each round key from the preceding one.
  • Each LowMC round applies S-boxLayer, AffineLayer, and KeyAddition, with KeyExpansion also performed before AffineLayer in this implementation.

6 Grover oracles and key search resource estimates

The authors construct full AES and LowMC Grover oracles and estimate key-search costs with and without depth limits. Fewer plaintext-ciphertext pairs than earlier estimates suffice, and the resulting AES costs are generally below NIST’s estimates.

  • The full Grover oracle encrypts multiple known plaintext blocks under one candidate key and checks whether all outputs match the supplied ciphertexts.
  • AES key uniqueness with overwhelming probability requires r = 2 for AES-128, r = 2 for AES-192, and r = 3 for AES-256.
  • With lower success probability accepted, r = 1, 2, and 2 suffice for AES-128, AES-192, and AES-256, respectively.
  • For all three considered LowMC parameter sets, r = 2 gives a key-uniqueness probability negligibly close to 1, while r = 1 suffices under high parallelization.
  • The authors’ G-cost is always lower than prior work for the same AES instance and plaintext-ciphertext-pair count; DW-cost also improves when width grows by less than fourfold.
  • LowMC has higher overall G-cost and DW-cost than AES despite lower multiplicative complexity, because its large CNOT count dominates when all gates are counted.
  • For AES-128, MAXDEPTH = 240 raises the attack cost to 1.07 · 2^117 gates and 1.76 · 2^120 qubit-cycles, roughly 2^34 above the unrestricted setting.

7 Future work

The paper identifies several directions beyond its main depth-limited, single-target analysis. Future work includes alternative cost regimes, quantum multi-target attacks, and concrete circuit implementations for other cryptanalytic algorithms.

  • The study focuses on attacks constrained by a total quantum-circuit depth bound, leaving optimization under other hardware and cost constraints for future research.
  • The authors study single-target key search and leave quantum multi-target attacks under MAXDEPTH or alternative regimes for future work.
  • Concrete Q# or quantum-language implementations for cryptanalytic algorithms such as quantum lattice sieving and enumeration are identified as worthwhile exercises.

A AES encryption algorithm

The AES encryption algorithm takes a message and a key as inputs. The supplied algorithm description identifies these inputs without further detailing the encryption steps in the cited passages.

  • AES encryption receives a message m and a key k as its two stated inputs.

B Comparison of in-place AES KeyExpansion vs. naive unrolling

The in-place AES KeyExpansion design is both shallower and narrower than naive unrolling because independent expansion and round gates can run in parallel.

  • The in-place KeyExpansion design is shallower than the naive design while also using fewer qubits.Table 15 compares circuits differing only in their KeyExpansion design.
  • Parallel execution of KeyExpansion gates with independent round gates explains the in-place design’s lower depth.S-box computations for key expansion can run alongside state S-box computations in ByteSub.
  • The width difference between equivalent designs is 4 · 32 · (Nr + 1) − 32 · Nk qubits.Nr denotes the number of AES rounds and Nk the number of words in the AES key.

C AND gate

The AES implementation uses a T-depth 1 AND-gate circuit, whose measurement returns a classical bit while preserving the original qubit as the corresponding computational-basis state.

  • The AES implementation uses a T-depth 1 AND-gate circuit combining designs by Selinger and Gidney.The circuit was designed by Mathias Soeken and is shown in Figure 7.
  • In the measured AND-gate design, the measurement returns a classical bit b and leaves the original qubit in state |b⟩.
  • Figure 7 presents the AND-gate design used in the circuit.

D Placeholder S-box

A dummy S-box design is used to prevent neighboring S-box T gates from executing partially in parallel, enabling a sanity check of the estimated T-depth.

  • The dummy S-box forces wires to synchronize so neighboring S-box T gates cannot be partially computed in parallel.
  • Replacing the AES S-box with the dummy design provides a sanity check for the Q# resource estimator.
  • The resulting dummy AES operation has T depth 2 × # of rounds × d, where d is the dummy S-box depth.
Loading 1910.01700v1…