Leaky LWE standard

Propose Edit

Updated:

Following new works on relaxed versions of LWE, Lai, Swarnakar, and Woo introduced the Leaky LWE assumption in 2025 [1]. This assumption follows the idea of generalising the classical LWE assumption with additional linear information over the secret and/or the error with fewer restrictions than the standard Hint-MLWE and the Error-Leakage LWE assumptions. This Leaky LWE definition encompasses both the previous assumptions.

The key points of Leaky LWE compared to the previous assumptions is that it only requires the leaked variables to follow discrete Gaussian distributions rather than both, together with giving the ability to the adversary to choose the hint-matrices.

Definition

Leaky MLWE\(_{n,m,q,\chi_{\mathbf{s}},\chi_\mathbf{e},\mathcal{R}}^{\ell,\chi_{\mathbf{y}}, \Gamma}\)

Consider \(\ell > 0\) hints each with an associated distribution \(\chi_\mathbf{y}\) over \(\mathcal{R}^{m+n}\) and a set of hint-matrices \(\Gamma := \{ \mat{H} = (\mat{H}_\mathbf{s},\mat{H}_\mathbf{e}) \in \mathcal{R}^{\ell \times n} \times \mathcal{R}^{\ell \times m}: \|\mat{H}^\top \mat{H}\| \leq \beta\}\).

Consider the original M-LWE construction for a random matrix \(\mat{A} \leftarrow \mathcal{U}(\mathcal{R}_q^{m\times n})\) and \(\mathbf{r} := \begin{bmatrix}\mathbf{s} \\ \mathbf{e}\end{bmatrix}\) where \(\mathbf{s} \leftarrow \chi_\mathbf{s}\) and \(\mathbf{e} \leftarrow \chi_\mathbf{e}\). An adversary can select \(\ell\) hint-matrices \(\mat{H}_i\) knowing \( \mat{A}\), in order to generate \(\ell\) hints as \(\mathbf{z}_i = \mat{H}_i \mathbf{r} + \mathbf{y}_i\), where \(\mathbf{y}_i\leftarrow \chi_\mathbf{y}\).

Finally, the adversary is asked to distinguish between the LWE distribution \((\mat{A}, \vec{b} = \mat{A}\vec{s} + \vec{e} \bmod q)\) and a uniformly random distribution over \(\mathcal{R}_q^{m \times n} \times \mathcal{R}_q^m\) given \(\ell\) honest hints \(\mat{z}_i\) and the involved hint-matrices \(\mat{H}_i\).

Hardness

The hardness of Leaky MLWE was proven by Lai, Swarnakar, and Woo [1] for two parameter regimes encompassing both Hint-MLWE and Error-Leakage LWE. Their proofs are more permissive and enable the choice of better parameters.

More concretely, there is a reduction from MLWE\(_{n,m,q,\chi_\mathbf{s'},\chi_\mathbf{e'},\mathcal{R}}\) to Leaky MLWE\(^{\ell,\chi_\mathbf{y}, \Gamma}_{n,m,q,\chi_\mathbf{s},\chi_\mathbf{e},\mathcal{R}}\) if the parameters satisfy any of the conditions below.

Condition 1: Leakage over the secret and the error

This condition encompasses linear leakages over both the LWE secret \(\vec{s}\) and the LWE error \(\vec{e}\). In this setup, any distribution has to be discrete Gaussian but they can be distinct and non-spherical.

Condition 2: Leakage over the error

If the leakage is only revealing information over the LWE error \(\vec{e}\), then the reduction requires the secret distributions to be discrete Gaussian and spherical. The distributions \(\chi_\mathbf{e},\chi_\mathbf{e'}\), and the noise \(\chi_\mathbf{y}\) can follow (distinct) non-spherical discrete Gaussians.

The value of the bound \(\beta\) depends on the chosen standard deviations. Please find further details in Section 4.1 of [1].

The idea of the proofs follows the original proof from Hint-MLWE with an additional analysis of the statistical closeness of the constructed hints. The proof also differs in that it is a direct reduction from M-LWE rather than short secret M-LWE.

Constructions built from Leaky MLWE

  • Threshold PKE [2]
  • Registration-Based Encryption [3]
  • Hint-MLWE is a specialised instance of Leaky LWE, i.e. \(\textsf{Hint-MLWE}^{\ell,(\chi_\mathbf{y})_{i \in [\ell]}, \mathcal{U}(\mathcal{\Gamma})}_{n,m,q,\chi^{n+m}} := \textsf{Leaky-MLWE}^{\ell,\chi_\mathbf{y}, \mathcal{\Gamma}}_{n,m,q,\chi^n,\chi^m}\) according to Condition 1.
  • Error-Leakage LWE is a specialised instance Leaky LWE (in the Condition 2 regime), which only allow error leakages.

References

  • [1]Russell W. F. Lai, Monisha Swarnakar, and Ivy K. Y. Woo. 2025. Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage. IACR Commun. Cryptol. 2, 3 (2025), 21. https://doi.org/10.62056/AH89KSUC2
  • [2]Valerio Cini, Russell W. F. Lai, and Ivy K. Y. Woo. 2025. Pilvi: Lattice Threshold PKE with Small Decryption Shares and Improved Security. In Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings, Part VI (Lecture Notes in Computer Science), 2025. Springer, 539–569. Retrieved from https://ia.cr/2025/1691
  • [3]Michael Klooß, Russell W. F. Lai, Jan Niklas Siemer, and Monisha Swarnakar. 2026. Scalable Registration-Based Encryption from Lattices. Retrieved from https://eprint.iacr.org/2026/717