Masked Differential-linear Distinguishers and Quantum Approaches

• URL: http://arxiv.org/abs/2608.24799v1
• Date: Tue, 25 Aug 2026 16:43:31 GMT
• Title: Masked Differential-linear Distinguishers and Quantum Approaches
• Abstract summary: Masked auto-correlation is a new primitive for the cryptanalysis of symmetric-key primitives.<n>We find mask pairs with large masked cross-correlation, which we call MAC Fishing.<n>We construct capacity-based distinguishers and key-recovery attacks, both classically and with a quadratic quantum speed-up.
• Score: 0.667049805558253
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Certifying Quantum Optimization and Circuit Cutting by Using Quantum-Classical Moment Duality [0.0]
  We establish a direct quantum-classical duality based on the degree-$2$ Sum-of-Squares semidefinite programming cone.<n>We show that the same moment matrix reveals the tensor-product structure of the underlying unitary circuit.<n>The framework is validated on Max-Cut instances for variational quantum algorithms and on random states for circuit cutting.
  arXiv  Detail & Related papers  (2026-06-19T12:48:36Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• High-Rate Quantized Matrix Multiplication: Theory and Practice [29.75700570685703]
  This work investigates the problem of quantized matrix multiplication (MatMul)<n>We consider two settings: 1) Generic MatMul, where both matrices must be quantized (weight+ quantization); and 2) weight-only quantization, where the second matrix is only known through covariance matrix $_X$ of its columns.
  arXiv  Detail & Related papers  (2026-01-23T21:32:44Z)
• On the Complexity Theory of Masked Discrete Diffusion: From $\mathrm{poly}(1/ε)$ to Nearly $ε$-Free [49.34727933066799]
  Masked discrete diffusion is a flexible paradigm for text generation in which tokens are corrupted by special mask symbols before being denoised.<n>We show that Euler samplers can achieve $epsilon$-accuracy in total variation (TV) with $tildeO(d2epsilon-3/2)$ discrete score evaluations.<n>We then propose a Mask-Aware Truncated Uniformization (MATU) approach that both removes bounded-score assumptions and preserves unbiased discrete score approximation.
  arXiv  Detail & Related papers  (2025-09-26T03:50:17Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum Augmented Dual Attack [8.134961550216618]
  We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM) Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM.
  arXiv  Detail & Related papers  (2022-05-27T13:54:31Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Discriminating Quantum States with Quantum Machine Learning [0.0]
  We propose, implement and analyze a quantum k-means (qk-means) algorithm with a low time complexity. Discriminating quantum states allows the identification of quantum states from low-level in-phase and quadrature signal (IQ) data. In order to reduce dependency on a classical computer, we use the qk-means to perform state discrimination on the IBMQ Bogota device.
  arXiv  Detail & Related papers  (2021-12-01T07:09:14Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.