Search papers, labs, and topics across Lattice.
This paper introduces masked auto-correlation (MAC), a new cryptanalytic primitive that enhances the analysis of symmetric-key primitives through a novel quantum attack pipeline. The authors establish a constant-query quantum algorithm for identifying high-correlation mask pairs, proving its necessity by demonstrating an exponential classical lower bound for the same task. Their findings reveal that MAC can effectively generalize classical techniques and enable capacity-based distinguishers and key-recovery attacks, validated through experiments on mini-AES.
Quantum algorithms are essential for identifying high-correlation cryptanalytic approximations, as classical methods face exponential query limitations.
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 $\alpha,\beta$, and an input difference $w$, masked auto-correlation (MAC) measures the correlation between the masked outputs $\alpha\cdot f(x)$ and $\beta\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 $\Omega(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.
