Common Notation

Non-Uniform LWE implied

Propose Edit

Updated:

Non-Uniform Learning with Errors was introduced by Boneh, Lewi, Montgomery, and Raghunathan in 2013 [1]. The problem diverges from LWE in the distribution of the challenge matrix, which can be distributed according to some distribution \(\eta\). As such, the problem generalises Binary-Matrix LWE (also known as Galbraith’s LWE) and Subspace LWE.

Definition

Non-Uniform LWE\(_{n,m,q,\chi,\eta}\)

Let \(\chi\) be a distribution over \(\ZZ_q\) and \(\eta\) be a distribution over \(\ZZ_q^n\). Sample \(\mat{A} \sample \eta^m \in \ZZ_q^{n \times m}\), \(\vec{s} \sample \ZZ_q^n\), \(\vec{e} \sample \chi^m\), and \(\vec{u} \sample \ZZ_q^m\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A}^{T} \cdot \vec{s} + \vec{e}) \text{ and } (\mat{A}, \vec{u}).\]

Variants

Binary-Matrix LWE\(_{n,m,q,\chi}\)

Sample binary matrix \(\mat{A} \sample \set{0,1}^{n \times m}\), secret vector \(\vec{s} \sample \ZZ_q^n\), and \(\vec{u} \sample \ZZ^m\). Let \(\vec{e} \in \ZZ_q^m\) be sampled from the error distribution \(\chi\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A}^{T} \cdot \vec{s} + \vec{e}) \text{ and } (\mat{A}, \vec{u}).\]

Simultaneously to the introduction of Non-Uniform LWE, Galbraith introduced LWE with a binary matrix [2]. He referred to this problem as Compact LWE and today, it is also referred to as Galbraith’s LWE. Galbraith originally used the assumption to build a space-efficient PKE scheme for devices with relatively small storage.

Binary-Matrix LWE is as hard as LWE [2][1]. For simplicity, let \(q\) be a power of 2 and \(\mat{G} = \mat{I}_n \otimes \begin{bmatrix} 1 &2 &\dots &2^{\log q - 1} \end{bmatrix}\) be a gadget matrix. Then, the LWE-challenge matrix \(\mat{A} \in \ZZ_q^{m \times n}\) can be transformed to a binary challenge matrix by performing the elementwise binary decomposition \(\mat{G}^{-1}(\mat{A})\). The reduction implies that the dimension of the binary matrix \(\mat{G}^{-1}(\mat{A})\) grows multiplicatively by \(\log q\).

Some cryptanalysis of Binary-Matrix LWE was given in [2] and it was further analysed in [3]. The parameters suggested in [2] mostly ignore the logarithmic growth in dimension of \(\mat{A}\), which was suggested in the reduction. The authors of [2] manage to break Binary-Matrix LWE for parameters suggested in [3] and thus show that the factor \(\log q\) has significant impact on the hardness of the assumption.

LWE with Low Norm\(_{n,m,q,\chi,s}\)

Sample matrix \(\mat{A} \sample D_{\ZZ,s}^{n \times m}\) from a discrete Gaussian, secret vector \(\vec{s} \sample \ZZ_q^n\), and \(\vec{u} \sample \ZZ_q^m\). Let \(\vec{e} \in \ZZ^m\) be sampled from the error distribution \(\chi\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A}^{T} \cdot \vec{s} + \vec{e}) \text{ and } (\mat{A}, \vec{u}).\]

This variant of Non-Uniform LWE with \(\eta = D_{\ZZ^n,s}\) is often referred to LWE with Low Norm. It is at least as hard as LWE according to Corollary 4.6 of [1].

Subspace LWE\(_{n,m,q,\chi,V}\)

Sample matrix \(\mat{A} \sample \mathcal{U}(V)\) from a linear subspace \(V \subset \ZZ_q^n\), secret vector \(\vec{s} \sample \ZZ_q^n\), and \(\vec{u} \sample \ZZ_q^m\). Let \(\vec{e} \in \ZZ^m\) be sampled from the error distribution \(\chi\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A}^{T} \cdot \vec{s} + \vec{e}) \text{ and } (\mat{A}, \vec{u}).\]

Subspace LWE (or Non-Uniform LWE with \(\eta = \mathcal{U}(V)\)) was introduced by Pietrzak in 2012 [4]. Similar to Corollary 4.7 in [1], he shows that Subspace LWE is at least as hard as LWE.

Hardness

Boneh et al. discuss the hardness of Non-Uniform LWE in Section 4 of [1]. They provide a generic reduction from LWE to Non-Uniform LWE if \(\eta\) follows a Coset Sampleable Distribution in Theorem 4.3 and then they provide three examples for Coset Sampleable Distributions, namely the three ones described above. The notion of a Coset Sampleable Distribution is closely related to Preimage Sampleable Functions. Additionally, they discuss how the given reductions can adapted to the small-secret LWE case. Further details can be found in Section 4 of [1]. The proofs are only given for LWE over \(\mathbb{Z}_q\).

Attacks on Ring-LWE with Binary Matrix

In Section 7.6 of [2] an attack against Ring-LWE with binary matrix is sketched. Intuitively, it uses the following observation. Given two samples \((a,b)\) and \((a',b')\) of Ring-LWE with binary matrix, where \(a,a'\) are both polynomials of the ring \(R_q\) (where typically \(R_q = \mathbb{Z}[X]/\langle X^n+1 \rangle\) and \(n\) a power-of-two degree) with binary coefficients. Then, one computes \(a \cdot b' - a' \cdot b\). If \(b,b'\) are Ring-LWE samples, then \(a \cdot b' - a' \cdot b = a(a's+e') - a'(as+e)= a \cdot e' - a' \cdot e\), which is small with respect to the modulus \(q\). If \(b,b'\) are uniform samples, this is not the case. Given many samples, one can recover \(e\) through statistical analysis (and thus recover \(s\)).

Constructions built from Non-Uniform LWE

  • Key-Homomorphic Preimage Sampleable Function [1]
  • Space-efficient Public-Key Encryption [2]
  • Attribute-Based Encryption [5]

References

  • [1]Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. 2013. Key Homomorphic PRFs and Their Applications. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I (Lecture Notes in Computer Science), 2013. Springer, 410–428. Retrieved from https://ia.cr/2015/220
  • [2]Steven D Galbraith. 2013. Space-efficient variants of cryptosystems based on learning with errors. (2013). Retrieved from https://www.math.auckland.ac.nz/~sgal018/compact-LWE.pdf
  • [3]Gottfried Herold and Alexander May. 2017. LP Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith’s Binary Matrix LWE. In Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I (Lecture Notes in Computer Science), 2017. Springer, 3–15. Retrieved from https://ia.cr/2018/741
  • [4]Krzysztof Pietrzak. 2012. Subspace LWE. In Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings (Lecture Notes in Computer Science), 2012. Springer, 548–563. https://doi.org/10.1007/978-3-642-28914-9_31
  • [5]Shweta Agrawal, Mélissa Rossi, Anshu Yadav, and Shota Yamada. 2023. Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part IV (Lecture Notes in Computer Science), 2023. Springer, 532–564. Retrieved from https://ia.cr/2023/941