Quantum limits on key guessing help improve side-channel attacks evaluation
Quantum-Aware Key Rank for Side-Channel Attacks evaluation
Cryptography and Security
Summary
Side-channel attacks try to find secret keys by analyzing side information but often end up with a list of likely keys instead of a single one. The authors studied how quantum computers can help finish this key search faster, but only up to a certain point due to hardware limits. They defined a way to compare classical and quantum attackers fairly based on computational cost, helping labs evaluate how much quantum power really speeds up key recovery. Their experiments show that quantum advantage depends on factors like guess rank and quantum device depth, giving practical guideposts for security evaluations.
What this means in practice
- •For security testing teams: Evaluate the effectiveness of quantum-assisted key recovery methods for side-channel attack scenarios within fixed quantum hardware limits.
- •For cryptographic hardware designers: Design cryptographic devices with key spaces that maintain security margins against quantum-enhanced side-channel analysis under realistic depth constraints.
Tested on simulated data.
Authors
Yevgen Kotukh
Abstract
Side-channel attacks on block ciphers rarely recover the key outright: they leave a residual key space ordered by subkey posteriors, and evaluation laboratories report the key rank of the true key against thresholds near 2^48 and 2^60. No evaluation framework models an adversary who collects traces classically and finishes the search on a quantum computer, although quantum search with advice provides exactly that. We give such an adversary a cost model and a metric. For a device whose key has rank r, any quantum algorithm with classical access to the posteriors needs Omega(sqrt(r)) cipher evaluations, and block search achieves O(sqrt(r)); the per-instance advantage is exactly quadratic, and the super-quadratic exponents reported for search with advice are averages over the prior that apply to no single device. Under the NIST MAXDEPTH budget D and a Grover iteration of g gates and depth d, the quadratic advantage holds only for ranks up to (4D/(pi d))^2 and collapses to a constant factor beyond; with the best published AES-128 oracle and D = 2^40 the window closes near rank 2^58.6. We define the quantum-aware key rank, the classical rank of equal cost, computable from the rank estimators laboratories already run, and derive the classical rank a device must retain to keep a given threshold against each depth budget. Block search and amplitude amplification from the product-form posterior state are within a factor of two to four of each other on Hamming-weight posteriors, so the cost of coherent indexing decides between them. Experiments on simulated leakage and a toy cipher confirm the predicted window: at SNR 0.125 a depth-limited quantum adversary is worth about 22 traces to a classical one, however large its gate budget.