Common Notation

Pint-LWR

Propose Edit

Updated:

The paper of Belaid, Benadjila, Devevey, Guerreau, Legavre, Martinelli, Ricosset, Rivain, and Rossi introduces the Permuted Hint Module Learning with Rounding assumption, written \(\pi\mathrm{nt}\text{-}\mathrm{MLWR}\), to argue security of the SUCRE countermeasure for masked ML-DSA rejection sampling [1].

Informally, the assumption starts from a standard rounded module-LWE sample and additionally reveals permutation information on rejected values produced during signing. The claim is that this extra leakage should still not help distinguish the rounded sample from uniform.

Definition

\(\pi\mathrm{nt}\text{-}\mathrm{MLWR}_{n,q,p,k,\ell,\gamma,\mathcal{S},\tau}\)

Let \(\mathcal{S}\) be a distribution over \(\mathcal{R}_q = \ZZ_q[X]/(X^n + 1)\). Recall the standard MLWR setting over \(\mathcal{R}_q\) with a random matrix \(\mat{A} \sample \mathcal{U}(\mathcal{R}_q^{k \times \ell})\) and a short vector \(\vec{y} \sample \mathcal{S}^\ell\).

Let \(\vec{s}_1 \sample \mathcal{S}^\ell, \vec{s}_2 \sample \mathcal{S}^k\) be short secrets, let \(c\) be a challenge, and let \(e(\cdot)\) denote the rounding error.

An adversary is asked to distinguish between the distribution

\[\left(\mat{A}, \lfloor \mat{A}\vec{y} \rceil_p, \pi(\vec{y}+c\vec{s}_1 \bmod 2\gamma), \pi(e(\mat{A}\vec{y}-c\vec{s}_2)), (\vec{s}_1,\vec{s}_2), c\right)\]

and

\[\left(\mat{A}, \lfloor \vec{u} \rceil_p, \pi(\vec{y}+c\vec{s}_1 \bmod 2\gamma), \pi(e(\mat{A}\vec{y}-c\vec{s}_2)), (\vec{s}_1,\vec{s}_2), c\right),\]

where \(\vec{u}\) is uniform. Here \(\pi\) forgets the original order of coefficients; equivalently, it captures a randomly permuted view of the leaked vectors.

Thus, an adversary is asked to distinguish the rounded sample \(\lfloor \mat{A}\vec{y} \rceil_p\) from uniform, while also receiving leakage on the rejected values.

Hardness

The paper does not give a reduction from standard MLWR to \(\pi\mathrm{nt}\text{-}\mathrm{MLWR}\). Instead, Section 4.2 of [1] performs an exploratory cryptanalysis of the search variant.

Two attack routes are discussed. The first tries to recover the hidden permutation through algorithms for the Permuted Kernel Problem. The second treats the leaked multisets of coefficients as side information in a lattice attack, in the spirit of LWE with hints. For the ML-DSA parameter sets considered in the paper, both approaches appear to incur only a very small loss compared with the underlying MLWR instance, heuristically around one bit of security.

At present, Pint-LWR should therefore be viewed as a conjectural leakage-augmented MLWR assumption motivated by the SUCRE security proof.

Constructions built from Pint-LWR

  • SUCRE rejection-sampling countermeasure for masked ML-DSA [1]
  • Learning with Rounding is the underlying rounded problem; Pint-LWR augments it with permutation-invariant leakage on rejected values.
  • Hint-LWE and Leaky LWE also add side information to LWE-type samples, but there the leakage is linear rather than a permuted view of the coefficients.

References

  • [1]Belaı̈d Sonia, Ryad Benadjila, Julien Devevey, Morgane Guerreau, Thomas Legavre, Ange Martinelli, Thomas Ricosset, Matthieu Rivain, and Mélissa Rossi. 2026. ML-DSA masking sweetened with SUCRE: Shuffle-and-Unmask Countermeasure for REjection sampling. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2026, (2026), 618–659. https://doi.org/10.46586/TCHES.V2026.I1.618-659