\(\ell\)-Decomposed LWE

Propose Edit

Updated:

Decomposed LWE was proposed by Abram, Malavolta, and Roy in 2025 [1] to secure the execution of RAM programs over encrypted data, based on the following primitives: Key-Homomorphic PKE, ABE, and Succinct Randomised Encodings.

Definition

We recall the definition of a gadget matrix \(\mat{G}_n = \mat{I}_n \otimes \vec{g}^\intercal\), where \(\vec{g}^\intercal = \begin{bmatrix} 1 & 2 & \cdots & b^{\lceil \log q \rceil- 1}\end{bmatrix}\).

\(\ell\)-Decomposed LWE\(_{n,m,\hat{m},q,\sigma_\mat{B},\sigma_{\vec{e}}}\)

Let \(\ell\) matrices \(\mat{W}_i \sample \ZZ_q^{n \times m}, \mat{B}_j \sample D_{\sigma_\mat{B}}^{m \times \hat{m}}\) and construct \(\mat{A}_{i,j} = \mat{W}_i\mat{B}_j + \delta_{i,j} \cdot \mat{G}\). Let \(\vec{s} \in \ZZ_q^n\) be chosen uniformly at random and noise errors \(\vec{e}_{i,j} \sample D_{\sigma_\vec{e}}^{\hat{m}}\). An adversary is asked to distinguish between the distribution \(\{\mat{W}_i,\mat{B}_j,\vec{b}_{i,j} = \vec{s}^\intercal\mat{A}_{i,j} + \vec{e}_{i,j}\}_{i,j \in [\ell]}\) and a tuple sampled from \(\mathcal{U}(\ZZ_q^{n \times m})^\ell \times (D_{\sigma_\mat{B}}^{m \times \hat{m}})^\ell \times \mathcal{U}(\ZZ_q^{m})^{\ell^2}\).

The Decomposed LWE assumption can also be viewed as an instance similar to \(\ell\)-succinct LWE, as presented by Wee [2] where \(\textsf{vec}\) denotes the concatenation of the columns of a matrix. In this setup, let \(\mat{W} \sample \ZZ_q^{n \times \ell m}\) and \(\mat{B} \sample D_{\sigma_\mat{B}}^{m \times \ell\hat{m}}\) and consider \(\mat{A}\) constructed as

\[\mat{A} = \mat{W} \cdot (\mat{I}_\ell \otimes \mat{B}) + \textsf{vec}(\mat{I}_\ell) \otimes \mathbf{G}.\]

Variants

Small-Secret Extended \(\ell\)-Decomposed LWE\(_{n,m,\hat{m},q,\sigma_\mat{B},\sigma_{\vec{s}},\sigma_{\mat{E}},t}\)

Let matrices \(\mat{W} \sample \ZZ_q^{(n\cdot \ell) \times m}\), \(\mat{B} \sample D_{\sigma_\mat{B}}^{m \times (\hat{m}\cdot \ell)}\), \(\mat{Q} \sample \mathsf{GL}_n(\ZZ_q)\), \(\mat{M} \sample \ZZ_q^{n \times t}\) and construct \(\mat{A} = \mat{W}\cdot\mat{B} + \mat{I}_\ell \otimes (\mat{Q} \cdot \mat{G})\). Let \(\vec{s} \sample D_{\sigma_{\vec{s}}}^n\) and errors \(\vec{e} \sample D_{\sigma_{\vec{s}}}^t\), \(\mat{E} \sample D_{\sigma_{\mat{E}}}^{\ell \times (\hat{m} \cdot \ell)}\). An adversary is asked to distinguish the distributions

\[\left\{\mat{W},\mat{B},\mat{Q},\mat{M},\vec{s}^\intercal\cdot \mat{M} + \vec{e}^\intercal,(\mat{I}_\ell \otimes \vec{s}^\intercal)\cdot\mat{A} + \mat{E}\right\},\] \[\mathcal{U}\left(\ZZ_q^{(n\cdot \ell) \times m}\right) \times D_{\sigma_\mat{B}}^{m \times (\hat{m} \cdot \ell)} \times \mathsf{GL}_n(\ZZ_q) \times \mathcal{U}\left(\ZZ_q^{n \times t}\right) \times \mathcal{U}\left(\ZZ_q^{1 \times t}\right) \times \mathcal{U}\left(\ZZ_q^{\ell \times (\hat{m} \cdot \ell)}\right).\]

As the name suggests, this version utilises a short-secret. Additionally, it extends the assumption via an invertible matrix \(\mat{Q}\) and \(t\) additional LWE samples with respect to the matrix \(\mat{M}\). According to Theorem 4.4 in [1], Small-Secret Extended \(\ell\)-Decomposed LWE is at least as hard as \(\ell\)-Decomposed LWE if \(\sigma_{\vec{s}} / (\sigma_{\mat{B}} \cdot \sigma_{\mat{E}}) \in \lambda^{\omega(1)}\) and \(\ell \in \poly{\lambda}\).

Small-Secret Circular \(\ell\)-Decomposed LWE\(_{n,m,\hat{m},q,\sigma_\mat{B},\sigma_{\vec{s}},\sigma_{\mat{E}},\sigma_{\bar{\vec{e}}},t}\)

Let matrices \(\mat{W} \sample \ZZ_q^{(n\cdot \ell) \times m}\), \(\mat{B} \sample D_{\sigma_\mat{B}}^{m \times (\hat{m}\cdot \ell)}\), \(\mat{Q} \sample \mathsf{GL}_n(\ZZ_q)\), \(\mat{M} \sample \ZZ_q^{n \times t}\), \(\mat{K} \sample \ZZ_q^{n \times \hat{m}\cdot(\hat{m} + \log q)}\), and construct \(\mat{A} = \mat{W}\cdot\mat{B} + \mat{I}_\ell \otimes (\mat{Q} \cdot \mat{G})\). Let \(\vec{s} \sample D_{\sigma_{\vec{s}}}^n\) and errors \(\vec{e} \sample D_{\sigma_{\vec{s}}}^t\), \(\bar{\vec{e}} \sample D_{\sigma_{\bar{\vec{e}}}}^{\hat{m}\cdot(\hat{m} + \log q)}\), \(\mat{E} \sample D_{\sigma_{\mat{E}}}^{\ell \times (\hat{m} \cdot \ell)}\). An adversary is asked to distinguish the distributions

\[\left\{\mat{W},\mat{B},\mat{Q},\mat{M},\vec{s}^\intercal\cdot \mat{M} + \vec{e}^\intercal,(\mat{I}_\ell \otimes \vec{s}^\intercal)\cdot\mat{A} + \mat{E}, \begin{bmatrix} \mat{K}\\ \vec{s}^\intercal \mat{K} + \bar{\vec{e}}^\intercal \end{bmatrix} - \mathsf{Bits}(\vec{s})^\intercal \otimes \mat{I}_{n+1} \otimes \vec{g}^\intercal \right\},\] \[\mathcal{U}\left(\ZZ_q^{(n\cdot \ell) \times m}\right) \times D_{\sigma_\mat{B}}^{m \times (\hat{m} \cdot \ell)} \times \mathsf{GL}_n(\ZZ_q) \times \mathcal{U}\left(\ZZ_q^{n \times t}\right) \times \mathcal{U}\left(\ZZ_q^{1 \times t}\right) \times \mathcal{U}\left(\ZZ_q^{\ell \times (\hat{m} \cdot \ell)}\right) \times \mathcal{U}\left(\ZZ_q^{(n+1) \times \hat{m}\cdot (\hat{m} + \log q)}\right).\]

The circular variant is supposed to correspond to Small-Secret Extended \(\ell\)-Decomposed LWE, where the distinguisher is provided an additional GSW encryption [3]. However, this intution is provided in [1] without any formal arguments.

Hardness

Let \(\hat{m} = n \log q\) and \(q\) be prime. For a polynomial \(\ell\), Abram, Malavolta, and Roy reduced the hardness of the assumption \(\ell\)-succinct LWE\(_{n,m,\hat{m},q,\sigma_\mat{B},\sigma_{\vec{e}}}\) to \(\ell\)-Decomposed LWE\(_{n,m,\hat{m},q,\sigma_\mat{B},\sigma_{\vec{e}}}\) where \(m \geq 2 \hat{m}\) and with a polynomial noise ratio \(\frac{\sigma_{\vec{e}}}{\sigma_\mat{B}}\).

The reduction is done by transforming the \(\ell\)-succinct LWE instance \((\mat{A}, \vec{b}, \mat{W}, \mat{T})\). Consider

\[\mat{T} = \begin{bmatrix} \mat{T}_{0,0} & \cdots & \mat{T}_{0,t-1} \\ \vdots & \ddots & \vdots \\ \mat{T}_{t-1,0} & \cdots & \mat{T}_{t-1,t-1} \\ \mat{B}_0 & \cdots & \mat{B}_{t-1} \end{bmatrix}.\]

The trapdoor \(\mat{T}\) is a Gaussian preimage such that \(\mat{AT}_{i,j} = \delta_{i,j} \cdot \mat{G} - \mat{W}_i\mat{B}_j\). The targets of the Decomposed instance are constructed as \(\vec{b}_{i,j}' = \vec{b}\mat{T}_{i,j} + \vec{e}_{i,j}\) where \(\vec{e}_{i,j} \sample D_{\sigma_\vec{e}}^m\). With an appropriate choice of Gaussian parameters, \(\vec{e}_{i,j}\) will flood the noise of \(\vec{b}\) (multiplied by \(\mat{T}_{i,j}\)). Finally, the \(\ell\)-Decomposed LWE instance is defined as \(\{-\mat{W}_i, \mat{B}_j,\vec{b}_{i,j}'\}_{i,j \in [\ell]}\).

Constructions built from Decomposed LWE

  • Succinct Randomised Encodings [1]
  • Attribute-based Encryption (ABE) with additional properties [1][2]
  • Constrained PRF [4]
  • Broadcast Encryption [4][5]
  • Distributed Monotone-Policy Encryption [6]

Further Reading Suggestions

References

  • [1]Damiano Abram, Giulio Malavolta, and Lawrence Roy. 2025. Key-Homomorphic Computations for RAM: Fully Succinct Randomised Encodings and More. 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, 236–268. Retrieved from https://ia.cr/2025/339
  • [2]Hoeteck Wee. 2025. Almost Optimal KP and CP-ABE for Circuits from Succinct LWE. In Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part III (Lecture Notes in Computer Science), 2025. Springer, 34–62. Retrieved from https://eprint.iacr.org/2025/509
  • [3]Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. 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, 75–92. Retrieved from https://ia.cr/2013/340
  • [4]Damiano Abram, Giulio Malavolta, and Lawrence Roy. 2026. How to Authenticate a Non-Deterministic Computation: Shift-Hiding Functions, Compressed LWE Sampling, Broadcast Encryption, and Obfuscation. Retrieved from https://ia.cr/2026/741
  • [5]Rishab Goyal and Saikumar Yadugiri. 2026. Adaptively-Secure Flexible and Identity-Based Broadcast Encryption from Decomposed LWE. Retrieved from https://ia.cr/2026/862
  • [6]Jeffrey Champion and David J. Wu. 2026. Distributed Monotone-Policy Encryption for DNFs from Lattices. In Advances in Cryptology – EUROCRYPT 2026, 2026. . Retrieved from https://ia.cr/2026/318