\(k\)-LWE standard

Propose Edit

Updated:

The \(k\)-LWE assumption was in 2014 by Ling, Phan, Stehlé, and Steinfeld [1] as the LWE version of \(k\)-SIS. Its utilisation in constructions is currently limited to traitor tracing schemes [1].

Definition

\(k\)-LWE\(_{n,m,q,\mat{S},\mat{C},\alpha}\)

Let \(k\leq m\), \(\mat{S} \in \RR^{m \times m}\) invertible, and \(\mat{C}=\begin{bmatrix} \vec{c}_1 &\dots &\vec{c}_k \end{bmatrix} \in \RR^{m \times k}\). Let matrix \(\mat{A} \in \ZZ_q^{m \times n}\) and vector \(\vec{u} \in \ZZ_q^n\) be chosen uniformly at random and hint vectors \(\vec{x}_i \sample D_{\Lambda^{-\vec{u}}(\mat{A}), \mat{S},\vec{c}_i}\) for \(i \leq k\). Given \(\mat{A}, \vec{u},\) and \((\vec{x}_i)_{i \leq k}\), an adversary is asked to distinguish between the two distributions

\[U\left( \text{im}\left( \begin{bmatrix} \vec{u}^T \\ \mat{A} \end{bmatrix} \right) \right) + D_{\ZZ, \alpha}^{m+1} \text{ and } U\left( \text{span}_{i\leq k}\left( \begin{bmatrix} 1 \\ \vec{x}_i \end{bmatrix}^\bot \right) \right) + D_{\ZZ, \alpha}^{m+1}.\]

The classical LWE problem consists in distinguishing the left distribution from uniform (without hint vectors). The introduction of the hint vectors \(\vec{x}_i \in \Lambda^{-\vec{u}}\) disallows the naive utilisation of the uniform distribution due to the following dependency. Let \(\vec{y} \in \ZZ^{m+1}\) be a challenge sample from the left distribution, then

\[\exists \vec{z} \in \ZZ^n: \begin{bmatrix} \vec{u}^T \\ \mat{A} \end{bmatrix} \cdot \vec{z} \approx \vec{y} \Rightarrow \vec{x}_i^T \cdot \vec{y} \approx \vec{x}_i^T \cdot \begin{bmatrix} \vec{u}^T \\ \mat{A} \end{bmatrix} \cdot \vec{z} = \vec{0} \bmod q.\]

In other words, the short values \(\langle \vec{x}_i, \vec{y} \rangle\) from the left distribution would be easily distinguishable from uniform values. \(k\)-LWE handles this issue by replacing \(U(\ZZ_q^{m+1})\) by \(U\left( \text{span}_{i\leq k}\left( \begin{bmatrix} 1 \\ \vec{x}_i \end{bmatrix}^\bot \right) \right)\).

Please find the module version of \(k\)-LWE in Definition 2.22 of [2].

Hardness

Ling et al. [1] proved that \(k\)-LWE is at least as hard as LWE for \(k \in \bigO{m}\). This result was extended to the module-version of \(k\)-LWE in Section 7 of [2].

Constructions built from \(k\)-LWE

  • Bounded-collusion public-key traitor tracing [1]
  • k-SIS can be seen as the dual or rather SIS version of \(k\)-LWE.

References

  • [1]San Ling, Duong Hieu Phan, Damien Stehlé, and Ron Steinfeld. 2014. Hardness of k-LWE and Applications in Traitor Tracing. In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I (Lecture Notes in Computer Science), 2014. Springer, 315–334. Retrieved from https://ia.cr/2014/494
  • [2]Martin R. Albrecht, Joël Felderhoff, Russell W. F. Lai, Oleksandra Lapiha, and Ivy K. Y. Woo. 2025. A Gaussian Leftover Hash Lemma for Modules over Number Fields. Retrieved from https://ia.cr/2025/1852