PaperlayerView exact revision on arXiv

Source-linked AI summary

Masked Differential-linear Distinguishers and Quantum Approaches

Shobhit Pandey, Sarbani Sen, Debajyoti Bera, Ravi Anand

arXiv:2608.24799v1quant-phcs.CR

TL;DR

The paper addresses how to identify high-correlation approximations for symmetric-key cryptanalysis when mask pairs form an exponential search space. It introduces masked auto-correlation and a quantum sampling-and-attack pipeline, proving a classical lower bound for mask finding and applying the framework to distinguishers and key recovery. The framework is supported by reduced-round Mini-AES and toy Simon-cipher experiments, with stated complexity boundaries for the lower-bound regime and expected attack costs.

  • Problem

    Finding mask pairs with large cross-correlation is an exponential-space search, while classical approaches lack an efficient analogue for this step.

  • Method

    The paper defines masked auto-correlation and MDL approximations, samples mask pairs by squared correlation with a constant-query quantum algorithm, and uses amplitude estimation in attack pipelines.

  • Results

    MAC Fishing requires Ω(N/log N) classical queries, while the framework yields capacity-based distinguishers and last-round key recovery with quantum quadratic query advantages.

  • Takeaways & Limitations

    MDL provides one statistical framework for several classical distinguishers and supports quantum procedures for finding and verifying exploitable approximations.

  • Takeaways & Limitations

    The rigorous Ω(N/log N) MAC-Fishing lower bound is proved only in the dense regime Nτ = Θ(1), whereas the distinguisher uses the sparser regime Nτ = ω(log N).

Abstract

from arXiv · show

We introduce masked auto-correlation, a new primitive for the cryptanalysis of symmetric-key primitives, together with a quantum attack pipeline built on it. For a permutation $f$, output masks $α,β$, and an input difference $w$, masked auto-correlation (MAC) measures the correlation between the masked outputs $α\cdot f(x)$ and $β\cdot f(x\oplus w)$. The associated masked differential-linear (MDL) approximations strictly generalize several classical techniques; ordinary linear cryptanalysis, differential-linear cryptanalysis, and the differential-linear connectivity table all arise as special cases. Our central object of study is the problem of finding mask pairs with large masked cross-correlation -- those that yield powerful distinguishers -- which we call MAC Fishing. We give a constant-query quantum algorithm that samples such pairs according to their squared correlation, and we prove an exponential classical lower bound of $Ω(N/\log N)$ queries, by adapting the hardness of Fourier Fishing. To our knowledge this is the first result pairing a quantum upper bound with a classical lower bound for the core task of identifying high-correlation approximations, making quantum algorithms an absolute necessity. Building on this, we analyse the distribution of masked auto-correlation for random permutations, and then construct capacity-based distinguishers and key-recovery attacks, both classically and with a quadratic quantum speed-up using amplitude estimation. We validate our claims with experiments on reduced-round mini-AES.

1 Introduction

The paper introduces masked auto-correlation and MDL approximations as a unified framework for classical symmetric-key distinguishers. It develops quantum mask-finding and attack procedures, proves a classical query lower bound, and validates the framework experimentally.

  • Masked Auto-Correlation: Masked auto-correlation measures cross-correlation between masked outputs α · f(x) and β · f(x ⊕ w), enabling MDL approximations for permutations.The framework studies output-mask pairs across input differences and formalizes their correlation structure.
  • MAC Fishing: MAC Fishing finds mask pairs with large |Cw(α, β)|, which are the heavy pairs used by the paper’s distinguishers.The search ranges over exponentially many mask pairs, making naive enumeration infeasible.
  • Quantum Approach: A constant-query quantum sampler outputs mask pairs with probability proportional to Cw(α, β)^2, directly favoring high-correlation approximations.The sampler uses 3n qubits and two oracle calls to f for a fixed key.
  • Quantum Approach: MAC Fishing requires Ω(N/log N) classical queries, establishing a provably exponential quantum speedup for identifying high-correlation approximations.The lower bound adapts the Aaronson–Chen hardness proof for Fourier Fishing.
  • Unifying Framework: MDL approximations strictly generalize linear cryptanalysis, differential-linear cryptanalysis, multidimensional variants, and the DLCT.Ordinary linear cryptanalysis is recovered with the identity map and zero difference, while mask constraints recover differential-linear cases and DLCT entries.
  • Applications and Validation: Capacity-based distinguishers and signed-template key recovery extend the framework classically and quantumly, with amplitude estimation providing a quadratic query advantage.The quantum procedures replace classical O(1/τ) verification with O(1/√τ). Experiments confirm distributional predictions on Mini-AES and end-to-end attack behavior on a toy Simon cipher.

2 Background and Related Works

This section reviews classical cryptanalysis, capacity-based distinguishers, multidimensional approximations, and quantum extensions, motivating the paper’s masked framework and query-separation results.

  • Capacity: Capacity-based distinguishers use squared Euclidean imbalance, with data complexity proportional to O(1/Cap).
  • Classical cryptanalysis: Classical linear and differential cryptanalysis remain foundational paradigms for evaluating symmetric-key primitives.
  • Multidimensional cryptanalysis: Multidimensional linear cryptanalysis aggregates a basis of approximations through capacity, avoiding early statistical-independence assumptions.
  • Multidimensional cryptanalysis: Trivial mask pairs reduce the effective chi-square degrees of freedom from 2^l−1 to 2^l−2·2^n+1, while non-trivial approximations recover 2^l−1.
  • Quantum cryptanalysis: Quantum counting reduces one-dimensional distinguishing time from O(1/Cor^2) to O(1/|Cor|), while related work extends quantum correlation extraction to multidimensional attacks.
  • Quantum query lower bounds: Fourier Fishing establishes a canonical quantum–classical query gap that the paper adapts to finding mask pairs with large masked cross-correlation.

3 Masked Auto-Correlation

Masked auto-correlation extends cross-correlation to two masked outputs of a shifted permutation, with exact identities and random-permutation distributions guiding later algorithms.

  • Definition: Masked auto-correlation measures cross-correlation between α·f(x) and β·f(x⊕w) for output masks α, β and shift w.
  • Distribution: MACD_w defines a distribution over mask pairs using squared masked auto-correlation, and its support excludes pairs with exactly one zero mask.
  • Random-permutation behavior: The random-permutation analysis uses a central-limit heuristic treating masked outputs as many near-independent ±1 variables as N→∞.
  • Random-permutation behavior: For a random permutation and α≠β, C_w(α,β) follows N(0,1), with expected squared correlation 1 and variance 2.
  • Random-permutation behavior: For a random permutation and equal non-zero masks, C_w(α,α) follows N(0,2), with expected squared correlation 2 and variance 8.
  • Scope: The paper restricts its algorithms and experiments to non-zero shifts w, despite also analyzing the w=0 case.

4 Masked Auto-Correlation (MAC) Fishing

MAC Fishing seeks high-correlation mask pairs among exponentially many candidates; the paper gives a constant-query quantum sampler, proves classical hardness, and validates abundance of good pairs experimentally.

  • Problem definition: MAC Fishing asks for a mask pair with |C_w(α,β)| above a threshold τ among exponentially many mask pairs.
  • Experiments: In 16-bit mini-AES, at least 4% of mask pairs are good for nearly 75% of sampled keys, supporting the abundance of exploitable pairs.
  • Classical hardness: Ω(N/log N) classical queries are required for MAC Fishing, and any o(N/log N) randomized algorithm succeeds with probability at most 0.317+o(1).
  • Quantum algorithm: A constant-query quantum algorithm samples mask pairs with probability proportional to their squared cross-correlation, favoring heavy pairs.
  • Quantum algorithm: At most three oracle queries in expectation suffice to output non-zero masks with probability C_w(α,β)^2/[N(N−1)].
  • Quantum algorithm: Removing zero-mask filtering yields two oracle queries and sampling probability C_w(α,β)^2/N^2.

5 Masked Differential-Linear (MDL) Approximation

Masked Differential-Linear approximations stack masked differential bits across shifted evaluations, with capacity summarizing their value distribution and decomposing into masked cross-correlations. This framework strictly generalizes linear, differential-linear, multidimensional variants, and the DLCT, while random-permutation capacities follow predicted chi-square behavior.

  • Definition and construction: MDL approximations stack t masked differential bits, one for each linearly independent mask pair, into a t-bit function.Each coordinate is α_i · f(x) ⊕ β_i · f(x ⊕ w), equivalently a linear projection determined by the mask pair.
  • Capacity: Capacity decomposes exactly into the masked cross-correlations of all non-empty linear combinations of the approximation coordinates.The mask pairs used for capacity are precisely the non-empty linear combinations of the original linearly independent pairs.
  • Random permutations: For random permutations, capacity has expectation zero and follows a central χ2 distribution with at most 2^t − 1 degrees of freedom.The corresponding value distribution is uniform, p_z = 1/2^t, under the stated assumptions.
  • Random block ciphers: The paper conjectures that random block-cipher capacity approximately follows a central χ2 distribution with 2^t − 1 degrees of freedom.The conjecture is reported to hold when all mask pairs are non-zero, including masks returned by MACSample, and is observed experimentally in Figure 3.
  • Relationship to existing techniques: The framework preserves the statistical structure of several classical linear attacks while extending their approximation form.The paper explicitly characterizes the generalization as capturing both the structures and the corresponding statistical properties of these attacks.
  • Relationship to existing techniques: MDL strictly generalizes ordinary linear cryptanalysis, differential-linear cryptanalysis, their multidimensional variants, and the DLCT through restrictions on masks or input differences.Setting one function to the identity and w = 0 recovers linear cryptanalysis; setting α = β recovers differential-linear cryptanalysis and the DLCT special case.

6 Distinguishers and Key-Recovery Attacks

The paper develops capacity-based distinguishers and last-round key-recovery attacks from masked auto-correlation, with quantum variants using MAC Fishing and amplitude estimation. Experiments and complexity analyses characterize their classical and quantum costs, while signed template matching resolves key ambiguity left by unsigned energy.

  • Capacity-Based Distinguisher: CapacityDistinguisher estimates the capacity of masked output differences and thresholds it to distinguish a structured cipher from a random permutation.The capacity is interpreted as accumulated squared masked auto-correlations over carefully constructed mask pairs.
  • Capacity-Based Distinguisher: Almost all tested keys produced capacity near 1 for a random permutation and close to 1.7 for Mini-AES.The experiment used a fresh set of 40 keys and a 16-dimensional approximation selected from other keys.
  • Last-Round Key Recovery: TemplateKeyRecovery filters subkeys by correlation energy and then uses signed template matching to distinguish the correct key from an energy-equivalent class.In experiments, signed re-ranking recovered the correct subkey at the top, while energy screening alone returned an equivalence class.
  • Last-Round Key Recovery: The classical last-round attack recovers a κ-bit subkey with O(2^κ m/τ) one-round operations, while memory is O(2^κ + m).The mask budget m sharpens separation but increases time and memory linearly; the stated bounds are expected costs and leave estimator-variance analysis for future work.
  • Quantum MAC-Fishing Attacks: Quantum MAC-Fishing attacks use O(1) queries for sampling and O(1/√τ) for verification, with repetition cost O(1/adv).For key recovery, the online quantum cost is O(2^κm/√τ), giving a quadratic 1/√τ improvement over classical verification when the offline term is dominated.

A Proof of Theorem 1

The proof establishes that MAC Fishing remains classically hard: randomized algorithms using o(N/log N) queries cannot achieve the required success probability on random permutations. It adapts Fourier Fishing through distributional and concentration arguments for masked cross-correlations.

  • Problem setup: MAC Fishing asks for a mask pair whose masked cross-correlation satisfies |C_w(α, β)|^2 ≥ τ.The proof contrasts this objective with Fourier Fishing, where one seeks a high-valued Fourier coefficient.
  • Query lower bound: No randomized algorithm making o(N/log N) queries solves MAC Fishing with probability SuccR+Ω(1) for large n.The randomized statement follows from the deterministic contradiction argument via Yao’s minimax principle.
  • Distributional analysis: For random permutations, masked cross-correlations are modeled as N(0, 1) off the diagonal and N(0, 2) on the diagonal.The diagonal and off-diagonal cases require separate variance calculations throughout the proof.
  • Query lower bound: With high probability, all mask pairs observed through fewer than N queries have low masked cross-correlation for a random permutation.The proof separates seen and unseen contributions and applies Gaussian tail bounds and a union bound.

B Experimental Validation

The experiments use a four-round, 12-bit Feistel cipher and compute the relevant correlation quantities exactly, while simulating the quantum primitives on the reduced construction.

  • Validation procedure: The capacity-family quantities are computed exactly by enumeration, while the quantum MAC-fishing stages simulate their two required primitives.The stated aim is to test whether the pipeline follows the theoretical correlation baseline.
  • Experimental setup: The experimental cipher uses 6-bit words, giving a 12-bit block and N=4096.The state is represented as two 6-bit halves.
  • Experimental setup: The reduced cipher has four rounds, and the target five-round cipher appends a secret last-round subkey with 64 candidates.The last-round subkey space has κ=6 bits.
  • Experimental setup: Correlations are normalized so that random-permutation values follow N(0,2^-n), equivalently C_w=N Cor follows N(0,1).This normalization provides the baseline used for the spectrum experiments.

B.2 Masked auto-correlation spectrum and sampling

The reduced cipher’s masked auto-correlation spectrum is compared with the random-permutation baseline, and quantum sampling is tested on the heavy correlation set.

  • Spectrum: At w=0x8f, the random-permutation spectrum follows N(0,1) off diagonal and N(0,2) on diagonal.The reduced cipher instead concentrates correlation in a handful of heavy pairs.
  • Spectrum: The full spectrum for a fixed difference is obtained by a Walsh–Hadamard transform of the paired-output distribution.This permits exact computation of all 2^2n mask-pair values for that difference.
  • Sampling: Conditioned on V_w={Cor^2≥τ}, quantum MACSample returns mask pairs with probability proportional to Cor^2.Amplitude amplification concentrates sampling on the heavy set because the heavy pairs are a vanishing fraction of total squared-correlation mass.

B.3 The capacity distinguisher

The capacity distinguisher selects independent off-diagonal mask pairs to obtain a clean χ2 null distribution, and the toy cipher separates sharply from that baseline.

  • Capacity distinguisher: Four linearly independent off-diagonal mask pairs are stacked so every nonzero combination remains off diagonal.This avoids the variance-2 diagonal baseline and preserves a χ2^(2t−1) null with t=4.
  • Capacity distinguisher: Cap(g_w)=0.128 for the cipher, versus a random baseline of approximately 0.0037.The corresponding cipher statistic is N Cap≈523.
  • Capacity distinguisher: Across 4000 random permutations, N·d Cap(g_w) has empirical mean 15.1 versus the predicted value 15.The histogram follows the χ2^(2t−1) density, while the cipher lies beyond the null distribution.
  • Data complexity: Reliable distinguishing sets require approximately 31 plaintext pairs, consistent with the Ω(√(2^t/Cap)) scaling law.The empirical success curve is compared with the predicted complexity line.
  • Key recovery: All 64 last-round subkey candidates have identical unsigned energy, so key recovery uses signed template matching from six independent off-diagonal pairs.The signed cosine score is maximized on the single target coset.

B.5 The MAC-fishing distinguisher

The MAC-fishing distinguisher samples heavy mask pairs, verifies their correlations, and aggregates their squared correlations into an energy statistic. On the cipher, this separates cleanly from random permutations, but verification precision controls detection.

  • MACSample returns mask pairs with probability proportional to Cor^2, favoring the heavy pairs that drive the distinguisher.The sampling stage replaces exhaustive spectrum enumeration with quantum sampling.
  • At threshold τ = 10^-2, heavy-pair membership requires verification precision ε ∼√τ, costing approximately 10 queries here.QuantumVerify uses O(1/ε) queries for additive precision ε.
  • The distinguisher verifies m = 16 sampled pairs and thresholds their averaged energy.
  • At ε = √τ, the cipher and random-permutation energy distributions separate cleanly, yielding detection probability 0.88 at a 1% false-positive operating point.The random-permutation correlations include a noise floor from verification.
  • Detection is near-certain for ε ≲√τ and degrades when the verification noise floor ε^2 overtakes the heavy-pair energy.

B.6 MAC-fishing key recovery

MAC-fishing key recovery verifies sampled correlations against a signed template rather than relying on unsigned energy. The true subkey is isolated when the template spans the subkey space, but recovery requires finer precision than distinguishing.

  • The key-recovery pipeline uses QuantumVerify to obtain template correlations and scores each candidate by signed cosine similarity to a fixed reference vector.TemplateEstablishment fixes the same-key signed reference offline at high precision.
  • The unsigned energy is exactly key-blind, so recovery rests entirely on verified correlation signs.The measured energy spread across candidates is 0.
  • At an adequate verification budget, the true subkey k⋆ = 2 is the unique maximum of the signed score.
  • Recovery requires ε below the template magnitude |Cor| ≈0.15 because it must resolve signs rather than aggregate energy.
  • At ε = √τ, recovery succeeds only marginally at 0.68, whereas halving ε makes it reliable at approximately 1.Halving ε doubles the query cost under QuantumVerify's O(1/ε) scaling.
  • The heaviest correlations span only a rank-2 subspace, leaving four of six key directions dependent on weaker correlations and finer estimation.The Grover-style search returns a coset rather than a unique subkey unless the template masks span.
  • Experiments reproduce the precision hierarchy: distinguishing tolerates ε ∼√τ, while sign-based key recovery requires finer verification.

E Proof of Lemma 5

For random permutations, masked auto-correlation follows different Gaussian laws for equal and unequal masks, determining the corresponding squared-correlation moments.

  • For α ≠ β, Cw(α, β) ∼ N(0, 1), with expected squared correlation 1 and variance 2.
  • For α = β, Cw(α, α) ∼ N(0, 2), with expected squared correlation 2 and variance 8.
  • Averaging over all mask pairs gives expected squared correlation 1 + 1/N and variance 2 + 7(N − 1)/N^2.The average combines N equal-mask pairs with N^2 − N unequal-mask pairs.
  • The proof uses the χ^2(1) moments of squared Gaussian variables and averages the equal- and unequal-mask cases.

F Proof of Lemma 6

For a random permutation, the number of mask pairs exceeding a correlation threshold has variance obtained by separating equal-mask and unequal-mask cases.

  • The proof considers a nonzero difference w and the thresholded mask-pair set Vw^τ for a random permutation.
  • Unequal and equal masks have distinct exceedance probabilities, p1 = 2Φ(−√τ) and p2 = 2Φ(−√(τ/2)).
  • Independence across distinct mask pairs makes the covariance terms vanish, leaving the sum of Bernoulli variances.
  • The variance of |Vw^τ| is (N^2 − N)p1(1 − p1) + Np2(1 − p2).There are N^2 − N unequal-mask pairs and N equal-mask pairs.
Loading 2608.24799v1…