Quantum-Aware Key Rank for Side-Channel Attacks evaluation

What it is

Kotukh's paper adds a quantum-adversary metric to side-channel evaluation. The adversary collects traces classically (a "Q1" adversary: no quantum access to the device) and then searches the residual key space on a quantum computer. The paper notes that JIL, ISO/IEC 17825 and FIPS 140-3 do not model this adversary. The only public mention it finds is a remark that a classical 2^80 cut-off would fall to 2^40 under Grover.

How it works

• Per-instance bound. For a key of rank r, any quantum algorithm with classical access to the posteriors needs Ω(√r) cipher evaluations, and block search achieves O(√r). The speed-up is exactly quadratic.
• Reconciling the super-quadratic results. The exponents of Bashiri et al. and Schubert et al. (2^H2/3/2 against 2^H1/2) are averages over the prior. They do not describe any single device, so both results hold.
• Depth window. With a Grover iteration of g gates and depth d, and depth budget D:
• The cost is Θ(√r) only for r ≤ (4D/πd)².
• Above that the cost is Θ(r), and the gain over classical enumeration is the constant 16·c_cl·D/(π²·g·d).
• The paper gives closed-form window boundaries and their sensitivity to the published value of d.
• QKR_D. The quantum-aware key rank is the classical rank of equal cost. It is computed from histogram and ESrank estimators, so no new rank estimator is needed.
• Trace discount. For a fixed gate budget, the depth-limited quantum advantage plateaus at log2(γ/μ) extra classical traces, however large the gate budget. This is about 22 traces at SNR 0.125 and D=2^40, measured on simulated Hamming-weight leakage and a toy cipher.
• Block search versus amplitude amplification. Amplitude amplification from the product-form posterior costs about 1/√p_t. Block search costs about √r but needs coherent indexing. The paper proves √r ≤ 1/√p_t always. On 4,000 simulated instances the advice sharpness σ was 2–3 bits, so the two are within a small constant of each other. The cost κ of coherent indexing decides which wins in gates.

Preconditions / Affected

• The analysis is relevant to devices whose leakage lets a rank of roughly 2^50–2^60 be reached. Beyond about 2^58.6 (AES-128, D=2^40, best published oracle) the depth bound removes the quadratic gain.
• Assumption 1: the posterior factors across subkeys. It holds for unprotected first-round S-box leakage and fails for masked implementations that tie bytes together.
• Assumption 2: exactly one key of rank ≤ r matches the known plaintext–ciphertext pair.
• The model charges logical gates only. Error-correction overhead is outside it.

What to do

For an evaluation lab, the page implies the following:

• Keep reporting classical log2(rank), and also compute QKR_D with the rank estimators already in use.
• Use the paper's derivation of the classical rank a device must retain to keep a given threshold against each depth budget (2^40, 2^64, 2^96).
• Treat a roughly 2^80 classical cut-off as not safe post-quantum, since Grover halves the exponent.

Caveats

• The fetched text cuts off partway through the adversary model. The evaluation-practice section (Sect. 8), limitations (Sect. 9), experiments and proofs were not available, so the exact derived thresholds are not verified here.
• The text contains unresolved [VERIFY] markers on the AES oracle figures and on the Liu et al. reference.
• The cost of coherent indexing, new circuit designs and Kalyna are deferred to a companion paper. The window therefore depends on the published (g, d) values.
• The experiments use simulated leakage and a toy cipher, not real device traces.