Asymmetric LWE implied

Propose Edit

Updated:

Asymmetric LWE was introduced in 2020 by Zhang, Yu, Fan, Zhang, and Yang [1] to describe an optimised Key Encapsulation Mechanism (KEM) by purposefully allowing for some asymmetry between secret and error distribution.

Definition

Asymmetric LWE\(_{n,m,q,\chi,\alpha_s,\alpha_e}\)

Let matrix \(\mat{A} \in \ZZ_q^{m \times n}\) be chosen uniformly at random. Sample secret vector \(\vec{s} \sample \chi_{\alpha_s}^n\) and error vector \(\vec{e} \sample \chi_{\alpha_e}^m\). An adversary is asked to distinguish between the following distributions

\[(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e}) \text{ and } \mathcal{U}\left(\ZZ_q^{m \times n} \times \ZZ_q^m\right).\]

Asymmetric LWE allows the secret vector and error vector to be drawn from differently parameterised distributions. In [1], they rely on the module-version of Asymmetric LWE.

Hardness

In [1], they claim that Asymmetric LWE\(_{n,m,q,\chi,\alpha_s,\alpha_e}\) is at least as hard as LWE\(_{n,m,q,\chi_{\min(\alpha_s,\alpha_e)}}\) and at most as hard as LWE\(_{n,m,q,\chi_{\max(\alpha_s,\alpha_e)}}\) w.r.t. “all known solving algorithms despite the absence of a general proof”.

The reduction from Short Secret LWE\(_{n,m,q,\chi_{\min(\alpha_s,\alpha_e)}}\) to Asymmetric LWE\(_{n,m,q,\chi,\alpha_s,\alpha_e}\) holds for discrete Gaussian and (centered) binomial distributions. These hold due to the fact that

  • \(D_{\Lambda_0, s_0} + D_{\Lambda_1, s_1}\) is statistically close to \(D_{\Lambda_0 + \Lambda_1, \sqrt{s_0^2 + s_1^2}}\) according to Lemma 4.12 in [2]
  • \(\mathsf{Bin}(x, p) + \mathsf{Bin}(y, p) = \mathsf{Bin}(x+y, p)\), which is a well-known fact.

However, a reduction from LWE would introduce a loss in LWE samples \(m\) and for several distributions, it is unclear whether a reduction exists. Therefore, the authors of [1] describe further cryptanalytic approaches against Asymmetric LWE in Section 5.

Constructions built from Asymmetric LWE

  • Optimised signature [1][3]
  • Optimised Key Encapsulation Mechanism [1]

References

  • [1]Jiang Zhang, Yu Yu, Shuqin Fan, Zhenfeng Zhang, and Kang Yang. 2020. Tweaking the Asymmetry of Asymmetric-Key Cryptography on Lattices: KEMs and Signatures of Smaller Sizes. In Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II (Lecture Notes in Computer Science), 2020. Springer, 37–65. Retrieved from https://ia.cr/2019/510
  • [2]Dan Boneh and David Mandell Freeman. 2011. Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures. In Public Key Cryptography - PKC 2011 - 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings (Lecture Notes in Computer Science), 2011. Springer, 1–16. Retrieved from https://ia.cr/2010/453
  • [3]Renjie Jin, Shuoqu Jian, and Longjiang Qu. 2026. Optimized G+G Signature. In Public-Key Cryptography - PKC 2026 - 29th IACR International Conference on Practice and Theory of Public-Key Cryptography, West Palm Beach, FL, USA, May 25-28, 2026, Proceedings, Part I (Lecture Notes in Computer Science), 2026. Springer, 364–392. Retrieved from https://ia.cr/2026/943