Masked Differential-linear Distinguishers and Quantum Approaches

1 Introduction

• Classical cryptanalysis sequentially accumulates statistical evidence, while masked auto-correlation creates a quantum-native search problem for powerful mask pairs beyond efficient classical reach.The obstacles are searching an exponential mask space and sampling according to the cross-correlation distribution.Source: §1 · pp. 2–3

1.1 Technical Overview

• A two-oracle quantum algorithm samples mask pairs with probability proportional to C_w(α, β)^2, while MAC Fishing requires Ω(N/log N) classical queries.The lower bound adapts the hardness of Fourier Fishing, yielding a quantum upper bound and classical lower bound for identifying high-correlation approximations.Source: §1.1 · p. 3, §1.2 · p. 4
• Masked differential-linear approximations strictly generalize linear, differential-linear, multidimensional, and DLCT methods, whose capacities follow a conjectured central χ2 law for random permutations.Quantum attacks use MAC Fishing for masks and amplitude estimation for correlations, replacing O(1/τ) verification with O(1/√τ); signed template matching resolves key-recovery sign degeneracy.Source: §1.1 · pp. 3–4, §1.2 · p. 4

1.2 Our Contributions –

• Experiments confirm abundant, key-stable heavy masks and predicted χ2 capacity on 16-bit 3-round Mini-AES, while toy Simon separates the cipher and recovers its last-round subkey only with signed templates.Mini-AES validates distributional claims; toy Simon exercises the end-to-end attack pipeline because its last round encodes the subkey as a masked-output sign.Source: §1.2 · p. 5

2.1 Notation

• The paper works over F_2^n, models block ciphers as permutations, and denotes masked auto-correlation by C_w(α, β), with MACD_w sampling mask pairs.Capacity notation includes a 2^t multiplier for F_2-valued distributions.Source: §2.1 · p. 6

2.2 Correlation, capacity, and approximations

• Capacity measures squared Euclidean imbalance, with distinguishing data complexity O(1/Cap), while a single bias ε yields capacity 2ε^2 and complexity O(1/ε^2).Multiple approximations can reduce data complexity when combined with a suitable capacity notion.Source: §2.2 · p. 6

2.3 Linear cryptanalysis

• Linear cryptanalysis distinguishes ciphers through nonzero linear correlation; for random permutations, correlations are approximately N(0, 2^-n), making deviations beyond ±2^-n/2 detectable.Early combinations of multiple approximations relied on generally invalid independence assumptions [28,10,35].Source: §2.3 · p. 7

2.4 Multidimensional Linear Cryptanalysis

• Multidimensional linear cryptanalysis uses Pearson’s chi-square test on mask spaces, but trivial masks reduce degrees of freedom from 2^ℓ−1 to 2^ℓ−2·2^n+1.Approximations without trivial components recover the full 2^ℓ−1 degrees of freedom, while quantum correlation extraction enables related speed-ups.Source: §2.4 · pp. 7–8

2.5 Differential-linear cryptanalysis

• Differential-linear cryptanalysis combines differential and linear biases, while multidimensional differences and masks aggregate correlated approximations into a capacity and can reduce data complexity by |U⊥|.Bar-On et al. showed that the usual independence assumption can fail and introduced the DLCT to capture boundary dependencies.Source: §2.5 · pp. 8–9

2.6 Fourier Fishing and quantum query lower bounds

• Fourier Fishing separates quantum and classical search: one quantum query finds large squared Fourier coefficients, whereas classical algorithms need Ω(N/log N) queries; this motivates the paper’s analogous mask-search lower bound.The paper identifies large masked cross-correlation as a cross-correlation analogue of Fourier Fishing and adapts the Aaronson–Chen argument in Theorem 1.Source: §2.6 · p. 9

3 Masked Auto-Correlation

• Masked auto-correlation is the masked cross-correlation of a permutation with itself, indexed by output masks α, β and input difference w.The section also defines the corresponding distribution over mask pairs for fixed w.Source: §3 · p. 10

3.1 Few identities

• The MAC distribution never samples pairs with exactly one zero mask: both masks are zero with probability 1/N, otherwise both are non-zero.This follows from the exact identities for masked auto-correlation.Source: §3.1 · p. 11

3.2 Distribution of MAC for a random permutation

• For a random permutation, nonzero equal masks yield C_w(α, α) ∼ N(0, 2), whereas unequal masks yield C_w(α, β) ∼ N(0, 1).The analysis uses a central-limit heuristic for near-independent ±1 terms as N tends to infinity, distinguishing w = 0 and w ≠ 0 cases.Source: §3.2 · pp. 11–12
• For unequal masks, E_B[C_w(α, β)^2] = 1 and Var_B[C_w(α, β)^2] = 2; for equal masks, the corresponding values are 2 and 8.Across masks, E_{α,β,B}[C_w(α, β)^2] = 1 + 1/N and Var_{α,β,B}[C_w(α, β)^2] = 2 + 7/(N − 1)N^2 as stated in the supplied passage.Source: §3.2 · pp. 12–13

4 Masked Auto-Correlation (MAC) Fishing

• MAC Fishing asks for any mask pair (α, β) with large |C_w(α, β)|, collecting such heavy pairs above threshold τ for nonzero w.These heavy pairs are the approximations used by the paper’s distinguishers.Source: §4 · pp. 13–14
• At least 4% of mask pairs are good for nearly 75% of sampled 16-bit mini-AES keys, regardless of w.The experiment used τ = 9/2^16 and sampled four differences across 512 random keys.Source: §4 · p. 13, Figure 1 · p. 14
• Any o(N/log N)-query classical randomized algorithm succeeds with probability at most 0.317 + o(1), establishing hardness even with exponentially more queries.The lower-bound proof adapts the Fourier Fishing approach and uses τ = 1 for the stated separation.Source: §4 · pp. 14–15

4.1 Quantum Algorithm for MAC Fishing

• Algorithm 1 samples mask pairs with probability |C_w(α, β)|^2/N^2 using a constant-query quantum circuit.It prepares paired inputs separated by w, applies the permutation oracle, performs Hadamards, and measures the two mask registers.Source: §4.1 · pp. 15–16
• The filtered algorithm makes at most three oracle queries in expectation and outputs nonzero masks with probability C_w(α, β)^2/[N(N−1)].Without zero-mask filtering, two queries suffice and the output probability is C_w(α, β)^2/N^2; filtering repeats at most 1.5 times in expectation.Source: §4.1 · p. 16

5 Masked Differential-Linear (MDL) Approximation

• MDL approximations measure the correlation between α · f(x) and β · f(x ⊕ w) using output masks α, β and input difference w.They are defined analogously to linear approximations of vectorial functions.Source: §5 · p. 17

5.1 Single Approximation

• O(1/ϵ^2) classical samples, or O(1/ϵ) quantum queries, distinguish a cipher with known correlation magnitude at least ϵ from a random permutation.The test averages masked differential bits over randomly chosen plaintexts and applies Chernoff’s bound classically or quantum counting.Source: §5.1 · pp. 17–18

5.2 Multidimensional Approximation

• A multidimensional MDL stacks t masked differential bits from linearly independent mask pairs, and its capacity equals a sum of squared masked cross-correlations over their non-empty linear combinations.Every linear combination of the coordinates remains a single masked differential approximation, enabling the exact capacity decomposition.Source: §5.2 · p. 18

MDL Capacity

• For random permutations, the expected capacity is zero and follows a central χ2 distribution with at most 2^t − 1 degrees of freedom; experiments support the corresponding 2^t − 1-degree conjecture for random block ciphers.The conjecture applies when mask pairs are non-zero, while zero masks can reduce the degrees of freedom; Figure 3 reports the observed distribution.Source: MDL Capacity · p. 19, Figure 3 · p. 20

5.3 Relationship to Existing Techniques

• MDL strictly generalizes multidimensional linear and differential-linear cryptanalysis by recovering them when w = 0 with one identity side, or when α = β = γ and w = δ, respectively.Arbitrary mask pairs and vector-space organization extend the differential-linear setting to a multidimensional form.Source: §5.3 · pp. 19–20

Differential-Linear Connectivity Table (DLCT)

• The DLCT is a restricted MDL instance with f = g = S, identical masks α = β = λ, and shift w = Δ, making its entries proportional to the corresponding differential-linear correlation.Thus, MDL strictly generalizes both differential-linear cryptanalysis and the DLCT formalism.Source: Differential-Linear Connectivity Table… · pp. 20–21

Capacity Based Distinguisher Algorithm

• Capacity distinguishes structured ciphers from random permutations by estimating masked-correlation capacity, which accumulates nonzero correlations above the near-zero random baseline.Algorithm 2 thresholds an empirical capacity estimate from plaintext pairs under a fixed difference.Source: Capacity Based Distinguisher Algorithm · p. 22
• Nearly all tested keys produced capacity near 1 for random permutations but close to 1.7 for Mini-AES.The experiment used a 16-dimensional approximation and a fresh set of 40 keys; Wilson’s lower bound supported inference across keys.Source: Capacity Based Distinguisher Algorithm · p. 23, Figure 4 · p. 23

Key Recovery on the (r + 1)-Round Cipher

• Signed template matching recovers the correct last-round subkey after energy filtering removes wrong-key guesses at the random baseline.Energy alone leaves a linear equivalence class because magnitudes are shared; signed correlations distinguish the correct key, which ranked first experimentally.Source: Key Recovery on the (r + 1)-Round Cipher · pp. 23–24

Complexity Analysis

• Key recovery costs O(2^κ m/τ) one-round operations with data collected once, while mask count and threshold trade separation, memory, and data requirements.These are expected costs; rigorous estimator-variance and error-probability bounds remain open.Source: Complexity Analysis · p. 26

MAC-Fishing-Based Block Cipher Distinguisher

• MAC-Fishing distinguishing uses constant-query quantum sampling to find candidate masks, then verifies squared correlation at threshold τ.A sample is heavy with probability adv; quantum verification costs O(1/√τ), versus O(1/τ) classical queries, and repetition costs O(1/adv).Source: MAC-Fishing-Based Block Cipher… · pp. 27–28
• For τ = ω(log N/N), random permutations have no heavy mask pair with high probability, yielding negligible false positives after verification.The threshold is sparser than the dense regime Nτ = Θ(1) used for the stated classical hardness theorem.Source: §6 · p. 21, MAC-Fishing-Based Block Cipher… · p. 28
• TemplateKeyRecovery extends MAC Fishing to last-round recovery by collecting verified heavy tuples offline and ranking partially decrypted candidates by signed profile similarity.The correct key restores the reduced-round structure, whereas wrong guesses randomize correlations; the attack remains in the Q2 model because mask finding has no classical analogue.Source: §6.2 · p. 27, MAC-Fishing-Based Block Cipher… · p. 29
• The attack establishes m verified high-correlation tuples offline, then scores every candidate subkey with template correlations, applies an energy pre-filter, and ranks survivors by signed similarity.The energy pre-filter removes non-structured guesses near the 2^-n baseline before signed disambiguation.Source: MAC-Fishing-Based Block Cipher… · pp. 29–30
• When 1/adv ≤ 2^κ, the offline term is dominated and the total becomes O(2^κm/√τ), yielding a quadratic 1/√τ improvement over classical verification while retaining 2^κ enumeration.The comparison concerns verification cost; the candidate-key scan itself is unchanged in this bound.Source: MAC-Fishing-Based Block Cipher… · p. 30
• Grover search can reduce key enumeration from 2^κ to 2^(κ/2) by marking candidates passing the energy test, but sign-blindness and the need for coherent, amplified amplitude estimation leave rigorous composition unresolved.The stated result therefore remains the amplitude-estimation-only bound.Source: MAC-Fishing-Based Block Cipher… · p. 31

Relation to prior work

• Unlike Fourier Fishing, which seeks a high Fourier coefficient, MAC Fishing must identify a mask pair (α, β) whose masked cross-correlation satisfies |Cw(α, β)|^2 ≥ τ.The proof highlights that the adapted claims depend specifically on masked cross-correlation values.Source: A Proof of Theorem 1 · pp. 33, 41

Theorem conclusion

• The theorem follows by contradiction: an algorithm succeeding with SuccR + Ω(1) using o(N/log N) queries would solve the promised instances supplied by Lemma 8, contradicting Lemma 9.Lemma 8 implies that a 1 − o(1) fraction of random permutations satisfy the theorem’s promise.Source: A Proof of Theorem 1 · p. 34

Average-case analysis

• Lemma 8 states that for a random permutation, the expected advantage equals SuccQ(τ) + Δ(τ)/N and lies between SuccQ(τ) and SuccQ(τ) + 2/N.The analysis characterizes Cw(α, β) as behaving like N(0, 1) when α ≠ β and N(0, 2) when α = β.Source: A Proof of Theorem 1 · p. 35

Query lower bound

• Lemma 9 proves that no randomized algorithm using o(N/log N) queries solves MAC Fishing on a random n-bit permutation with probability SuccR + Ω(1).The argument first treats deterministic algorithms and extends to randomized algorithms via Yao’s minimax principle.Source: A Proof of Theorem 1 · p. 41

B Experimental Validation

• Exact enumeration and simulated MACSample and QuantumVerify test whether the pipeline matches predicted statistics, capacity-based distinguishability, and signed-template key recovery.The validation uses a known-key signed reference and simulates MACSample by sampling from the exact squared-correlation distribution, while QuantumVerify adds Gaussian noise with width ε.Source: B Experimental Validation · p. 43

B.1 A toy Simon-like cipher

• The toy cipher is a Simon-style Feistel construction with 6-bit words, 12-bit blocks, and N = 4096.The state is represented as a pair of 6-bit words, with within-word rotation operators S_j.Source: §B.1 · p. 43
• The reduced cipher B has four fixed-key rounds, while the target E_K appends a fifth round with a secret 6-bit subkey and 64 candidates.The last-round subkey space therefore has κ = 6 bits.Source: §B.1 · p. 43
• Its round constants follow the Simon pattern (1, 3, 2) scaled to 6-bit words.Each round key is 6 bits, and the target is formed as E_K = R_k⋆ ◦ B.Source: §B.1 · p. 43
• Correlations use the normalized masked differential-linear quantity Cor(B, w; α, β), defined over input differences w and output masks α, β.The supplied definition places these correlations in the range [−1, 1].Source: §B.1 · p. 43
• For a random permutation, normalized correlations follow a Gaussian baseline: Cor ∼ N(0, 2^-n), equivalently C_w = N Cor ∼ N(0, 1).This baseline is the statistic the experiments aim to verify for the toy construction.Source: §B.1 · p. 43, B Experimental Validation · p. 43

Sampling

• Quantum MACSample uses amplitude amplification to overcome bulk-dominated ∝ Cor^2 sampling and concentrate on V_w = {Cor^2 ≥ τ}.Conditioned on V_w, returned pairs are distributed proportionally to Cor^2, matching the empirical simulated draws.Source: §B.2 · p. 44, Figure 6 · p. 44

Spectrum

• At w = 0x8f, the reduced cipher has heavy masked auto-correlation pairs reaching |C_w| ≈ 24, while random permutations follow N(0, 1) off-diagonal and N(0, 2) diagonal baselines.The heaviest pairs are diagonal, corresponding exactly to differential-linear connectivity-table entries.Source: §B.2 · p. 43, Figure 5 · p. 44

B.3 The capacity distinguisher

• The capacity distinguisher stacks t = 4 linearly independent off-diagonal pairs, ensuring every nonzero combination is off-diagonal and the null is a clean chi-square distribution.Diagonal pairs are avoided because their variance-2 baseline and linear combinations would inflate the null degrees of freedom.Source: §B.3 · p. 44
• Cap(gw) = 0.128 for the cipher, versus the random baseline (2t − 1)/N ≈ 0.0037, with N Cap ≈523.The selected pairs are evaluated at w = 0x8f.Source: §B.3 · p. 44, Figure 7 · p. 45
• The cipher lies beyond the entire random-permutation null, while the statistic N · d Cap(gw) has empirical mean 15.1 versus the predicted chi-square mean 2t − 1 = 15.Figure 7 compares 4000 random permutations with the predicted chi-square density.Source: §B.3 · p. 44, Figure 7 · p. 45
• Reliable distinguishing requires about 31 plaintext pairs, matching the predicted scaling and the N = Ω(√(2t/Cap)) law of Equation (9).Figure 8 plots distinguishing success against data N and marks the predicted complexity with a dashed line.Source: Figure 8 · p. 45, §B.3 · p. 45

B.4 Last-round key recovery

• All 64 key candidates have identical correlation magnitudes and energy, so key information resides entirely in the correlation signs; diagonal pairs are key-blind.The Simon subkey contributes a constant phase determined by the key-mask, preserving magnitudes while changing signs.Source: §B.4 · p. 45
• Six heavy off-diagonal pairs with linearly independent key-masks uniquely recover the true subkey k⋆ = 2, whereas rank deficiency leaves κ − rank {mi} residual ambiguity bits.The signed cosine score peaks on the singleton coset {k⋆}; Figure 9 shows the flat energy profile and peaked signed score, and Table 7 ranks candidates.Source: §B.4 · p. 45

Quantum MAC-fishing pipeline

• The pipeline samples m = 16 heavy mask pairs proportional to squared correlation, verifies each with signed amplitude estimates, and thresholds their averaged energy.MACSample replaces enumeration, while QuantumVerify uses additive precision ε and resolves heavy-pair membership when |Cor| ≥√τ.Source: §B.5 · pp. 45–46

Verification precision

• At τ = 10^-2, resolving heavy-pair membership requires ε ∼√τ, corresponding to approximately 10 verification queries after amplitude amplification.The heavy set is defined by Cor^2 ≥ τ, and the amplification overhead is the inverse of 8.6×10^-6.Source: §B.5 · pp. 45–46

Last-round key recovery

• The signed score uniquely identifies the true subkey k⋆ = 2, whereas key-independent energy magnitudes are identical across all 64 candidates.The signed score singles out the true key when template key-masks span the subkey space; energy screening alone is uninformative.Source: Figure 9 · p. 46, Table 7 · p. 46

Distinguisher results

• Detection reaches 0.88 at a 1% false-positive operating point, while verification is near-certain for ε ≲√τ and degrades when ε^2 exceeds the heavy-pair energy.At ε = √τ, cipher and random-permutation statistic distributions separate cleanly; the observed detection matches Proposition 1’s Gaussian union bound.Source: §B.5 · p. 46

B.6 MAC-fishing key recovery

• The MAC-fishing key-recovery template reuses m = 6 off-diagonal pairs with rank {m_i} = 6 = κ and obtains correlations from QuantumVerify.The Grover-style search returns the recovered coset rather than a unique k⋆ unless the template masks span the subkey space.Source: §B.6 · pp. 46–47
• The signed score uniquely peaks at the true subkey k⋆ = 2, while unsigned energy is exactly key-blind and recovery depends on verified signs.TemplateEstablishment fixes a high-precision same-key reference; each candidate is verified on the peeled cipher and scored by signed cosine.Source: §B.6 · p. 47
• Success is only marginal at 0.68, whereas halving ε, at twice the query cost, makes the distinguisher reliable at approximately 1.Distinguishing tolerates the minimal ε ∼√τ budget, while sign-based key recovery requires finer verification; weaker correlations demand finer amplitude estimation.Source: §B.6 · p. 47

C Classical Verification and Scoring for MAC Fishing

• ClassicalVerify estimates each candidate pair’s squared correlation by averaging N oracle samples of its masked correlation and returning the square of that estimate.This is the classical Phase-2 verification procedure for MAC-Fishing attacks.Source: C Classical Verification and Scoring… · p. 48

D Use of Wilson’s Score

• Wilson intervals apply because threshold outcomes are noise-free i.i.d. binomial trials, while thresholds tied to the random-permutation noise floor keep qualifying fractions at modest tail mass.The interval captures sampling uncertainty; variation across keys or input differences is treated as genuine population variation against the same baseline.Source: D Use of Wilson’s Score · pp. 48–50
• ClassicalKeyScore computes per-mask correlations under each key guess, then returns average energy, template correlation, and normalized signed score.The score is Score(k) = T(k)/(∥v(k)∥∥v⋆∥), where T(k) is the inner product with the reference vector.Source: D Use of Wilson’s Score · p. 49
• Wilson’s one-sided lower bound keeps a candidate only when ρ_LB ≥0.70, using z = Φ^−1(0.95) = 1.6449 for a one-sided 95% claim.The bound remains in [0, 1], improves small-sample coverage over Wald’s interval, and is conservative for high target ρ.Source: D Use of Wilson’s Score · pp. 49–50

Case analysis

• For α ≠ β, C_w(α, β) follows N(0, 1), so its squared correlation has mean 1 and variance 2.These moments use the χ²(1) distribution of the squared normalized Gaussian.Source: E Proof of Lemma 5 · p. 50
• For α = β, C_w(α, β) follows N(0, 2), so its squared correlation has mean 2 and variance 8.The proof again derives the moments from the χ²(1) distribution.Source: E Proof of Lemma 5 · p. 50

Averaging over mask pairs

• Averaging over N equal-mask pairs and N^2 − N unequal-mask pairs gives E_α,β E_B[C_w(α, β)^2] = 1 + 1/N.The mask space contains N^2 ordered pairs, including N diagonal pairs.Source: E Proof of Lemma 5 · p. 50
• The same averaging yields Var_α,β,B[C_w(α, β)^2] = 2 + 7(N − 1)/N^2.The fourth moments needed for this calculation are obtained from each case’s variance and squared mean.Source: E Proof of Lemma 5 · p. 50

• For w ≠ 0_n and threshold τ > 0, the proof considers mask pairs (α, β) belonging to V_τ for a random permutation B.Source: F Proof of Lemma 6 · p. 51
• The proof treats the α = β ≠ 0_n case using C_w(α, α) ∼ N(0, 2), alongside the combined normal-variable representation.The tail probabilities are p_1 = 2Φ(−√τ) and p_2 = 2Φ(−√(τ/2)).Source: F Proof of Lemma 6 · p. 52
• Independence across distinct mask pairs makes the covariance terms vanish, so the variance of |V_τ| is (N^2 − N) · p_1(1 − p_1) + N · p_2(1 − p_2).This uses the variance formula p(1 − p) for Bernoulli indicators.Source: F Proof of Lemma 6 · pp. 51–52