Binary-Matrix LWE implied

Propose Edit

Updated:

In 2013, Galbraith introduced LWE with a binary matrix, which he referred to as Compact LWE and is also known as Galbraith’s LWE [1]. He originally introduced the assumption to suggest a more space-efficient PKE scheme for devices with relatively small storage.

Definition

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

Let binary matrix \(\mat{A} \in \set{0,1}^{m \times n}\) and secret vector \(\vec{s} \in \ZZ_q^n\) be chosen uniformly at random. Let \(\vec{e} \in \ZZ_q^m\) be sampled from the error distribution \(\chi\). Given the matrix \(\mat{A}\) and the vector \(\vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod q\), an adversary is asked to find the secret vector \(\vec{s}\).

Hardness

Binary-Matrix LWE is as hard as LWE [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 [1] and it was further analysed in [2]. The parameters suggested in [1] mostly ignore the logarithmic growth in dimension of \(\mat{A}\), which was suggested in the reduction. The authors of [1] manage to break Binary-Matrix LWE for parameters suggested in [2] and thus show that the factor \(\log q\) has significant impact on the hardness of the assumption.

Constructions built from Binary-Matrix LWE

  • Space-efficient Public-Key Encryption [1]

References

  • [1]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
  • [2]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