Tensor LWE

Propose Edit

Updated:

Tensor LWE was introduced in 2022 by Wee [1] to build broadcast encryption and ciphertext-policy attribute-based encryption schemes based on the hardness of Tensor LWE and Evasive LWE.

Definition

Tensor LWE\(_{n,m,q,\ell,Q,s_e,s_r}\)

Let \(\vec{x}_i \in \set{0,1}^\ell\) denote binary vectors and sample \(\mat{A} \sample \ZZ_q^{n \times \ell m}\), \(\vec{s} \sample \ZZ_q^{nm}\), \(\vec{e}_i \sample D_{\ZZ,s_e}^{\ell m}\), \(\vec{r}_i \sample D_{\ZZ,s_r}^m\), and \(\vec{c}_i \sample \ZZ_q^{\ell m}\) for \(i \in [Q]\). An adversary is asked to distinguish between the distributions

\[\left( \mat{A}, \set{\vec{s}^T \cdot \left( \mat{I}_n \otimes \vec{r}_i \right) \cdot \left( \mat{A} - \vec{x}_i^T \otimes \mat{G} \right) + \vec{e}_i^T, \vec{r}_i}_{i \in [Q]} \right) \text{ and } \left( \mat{A}, \set{\vec{c}_i^T, \vec{r}_i}_{i \in [Q]} \right).\]

Variants

Strong Tensor LWE\(_{n,m,q,\ell,k,Q,s_e,s_r}\)

Let \(\vec{x}_{j_1,\dots,j_k} \in \set{0,1}^\ell\) denote binary vectors indexed by \(j_1,\dots,j_k \in [Q]\). Sample \(\mat{A} \sample \ZZ_q^{n \times \ell m}\), \(\vec{s} \sample \ZZ_q^{nm^k}\), \(\vec{e}_{j_1,\dots,j_k} \sample D_{\ZZ,s_e}^{\ell m}\), \(\vec{r}_{i,j_i} \sample D_{\ZZ,s_r}^m\), and \(\vec{c}_{i, j_i} \sample \ZZ_q^{\ell m}\) for \(i \in [k], j_1,\dots,j_k \in [Q]\). An adversary is asked to distinguish between the Strong Tensor LWE distribution

\[\left( \mat{A}, \set{\vec{s}^T \cdot \left( \mat{I}_n \otimes \vec{r}_{1,j_1} \otimes \dots \otimes \vec{r}_{k,j_k} \right) \cdot \left( \mat{A} - \vec{x}_{j_1,\dots,j_k}^T \otimes \mat{G} \right) + \vec{e}_{j_1,\dots,j_k}^T, \vec{r}_{i,j_i}}_{i \in [k], j_1,\dots,j_k\in [Q]} \right)\]

and the distribution

\[\left( \mat{A}, \set{\vec{c}_{i,j_i}^T, \vec{r}_{i,j_i}}_{i \in [k], j_1,\dots,j_k \in [Q]} \right).\]

Agrawal, Rossi, Yadav, and Yamada [2] propose this generalised and stronger (some may say extended) version of Tensor LWE to provide a construction of constant-input attribute-based encryption. The reductions given for Tensor LWE have not been generalised to Strong Tensor LWE. Thus, the only known reductions exist for the special case \(k=1\), where Strong Tensor LWE is equivalent to Tensor LWE.

Circular Tensor LWE

In Section 4.2 of [3], Agrawal, Kumari, and Yamada introduce a circular version of Tensor LWE to provide an attribute-based encryption scheme for Turing machines. As the name suggests, this assumption combines the ideas of Circular LWE and Tensor LWE.

Hardness

Wee [1] shows that a modified version of Tensor LWE is at least as hard LWE, where the matrix \(\mat{A}\) is chosen discrete Gaussian and the gadget matrix \(\mat{G}\) is replaced by the identity matrix \(\mat{I}_n\). This statement is formalised in Lemma 3.6 of [2] and Agrawal et al. provide another Lemma (3.7) proving that the hardness of LWE implies the hardness of Tensor LWE if \(\vec{x}_i = \vec{0}\) for all \(i \in [Q]\) or all \(\vec{x}_i\) are equal (Corollary 3.8).

For further details, we refer to Section 3.2 and 3.3 in [2].

Constructions built from Tensor LWE

  • Broadcast Encryption [1]
  • Ciphertext-Policy Attribute-Based Encryption [1]
  • Multi-Party Attribute-Based Encryption [4]
  • Attribute-Based Encryption for Turing Machines [3]
  • Decomposed LWE also adds some structure to LWE but does not utilise tensor products.

References

  • [1]Hoeteck Wee. 2022. Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions. In Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 217–241. Retrieved from https://ia.cr/2023/906
  • [2]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
  • [3]Shweta Agrawal, Simran Kumari, and Shota Yamada. 2024. Attribute Based Encryption for Turing Machines from Lattices. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part III (Lecture Notes in Computer Science), 2024. Springer, 352–386. Retrieved from https://ia.cr/2025/001
  • [4]Valerio Cini, Russell W. F. Lai, and Ivy K. Y. Woo. 2024. Lattice-based Multi-Authority/Client Attribute-based Encryption for Circuits. IACR Commun. Cryptol. 1, 4 (2024), 1. https://doi.org/10.62056/AHMPGY4E-