\(\ell\)-succinct LWE

Propose Edit

Updated:

\(\ell\)-succinct LWE was introduced in 2024 by Wee [1] dual to \(\ell\)-succinct SIS and inspired by BASIS\(_\text{struct}\). So far, the assumption has been utilised to build Distributed Broadcast Encryption and Registered ABE schemes.

Definition

\(\ell\)-succinct LWE\(_{n,m,\hat{m},q,\chi,\sigma}\)

Let matrices \(\mat{A} \in \ZZ_q^{n \times m}\) and \(\mat{W} \in \ZZ_q^{\ell n \times \hat{m}}\) as well as vectors \(\vec{s} \in \ZZ_q^n\) and \(\vec{c} \in \ZZ_q^m\) be chosen uniformly at random. Sample \(\vec{e} \sample D_{\ZZ, \chi}^m\) discrete Gaussian and define \(\mat{B} := \begin{bmatrix} \mat{I}_\ell \otimes \mat{A} &\mat{W} \end{bmatrix}\) to generate a short trapdoor \(\mat{T} \gets \mat{B}_\sigma^{-1}(\mat{I}_\ell \otimes \mat{G}_n)\). An adversary is asked to distinguish between the distributions

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

Intuitively, the assumption states that Decision LWE is hard even if the adversary has access to a trapdoor \(\mat{T}\) for matrix \(\mat{B}\), which is related to the LWE challenge matrix \(\mat{A}\).

Hardness

Wee proved that \(\ell\)-succinct LWE is at least as hard as public-coin evasive LWE in Lemma 3 of [1].

Trivially, LWE implies \(\ell\)-succinct LWE\(_{n, m, \ell m, q, \chi, \poly(\lambda, \ell, m)}\) and 1-succinct LWE by following the trapdoor delegation approach [2] and sampling \(\mat{W}\) along with a trapdoor to derive a trapdoor for \(\mat{B}\).

Constructions built from \(\ell\)-succinct LWE

  • Distributed Broadcast Encryption [3][4]
  • Registered Attribute-Based Encryption [4]

References

  • [1]Hoeteck Wee. 2024. Circuit ABE with poly(depth,\(λ\))-Sized Ciphertexts and Keys 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, 178–209. Retrieved from https://ia.cr/2024/1416
  • [2]David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. 2010. Bonsai Trees, or How to Delegate a Lattice Basis. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings (Lecture Notes in Computer Science), 2010. Springer, 523–552. Retrieved from https://ia.cr/2010/591
  • [3]Jeffrey Champion and David J. Wu. 2024. Distributed Broadcast Encryption from Lattices. In Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part III (Lecture Notes in Computer Science), 2024. Springer, 156–189. Retrieved from https://ia.cr/2024/1417
  • [4]Hoeteck Wee and David J. Wu. 2025. Unbounded Distributed Broadcast Encryption and Registered ABE from Succinct LWE. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part III (Lecture Notes in Computer Science), 2025. Springer, 204–235. Retrieved from https://ia.cr/2025/1039