Circular LWE

Propose Edit

Updated:

Although circular security has been utilised in e.g. fully-homomorphic encryption to enable bootstrapping [1][2], the first paper to formalise a concrete circular security notion for LWE, namely Circular LWE, was published by Hsieh, Lin, and Luo in 2023 [3]. They utilise this assumption to construct Attribute-Based Encryption for circuits of unbounded depth.

Definition

Circular LWE\(_{n,m,m',q,s,s'}\)

Sample \(\mat{A} \sample \ZZ_q^{n \times m}\), \(\mat{A}' \sample \ZZ_q^{n\times m'}\), \(\vec{r} \sample D_{\ZZ,s}^n\), \(\vec{e} \sample D_{\ZZ,s}^m\), \(\vec{e}' \sample D_{\ZZ,s'}^{m'}\), \(\mat{R} \sample \set{0,1}^{m \times (n+1)\ceil{\log q}m}\), \(\delta \sample \ZZ_q^m\), \(\delta' \sample \ZZ_q^{m'}\), and \(\Delta \sample \ZZ_q^{(n+1) \times (n+1)\ceil{\log q}m}\). Define \(\vec{s} = (\vec{r}, -1)\). An adversary is asked to distinguish the circular LWE distribution

\[\set{ 1^\lambda, \begin{bmatrix} \mat{A} \\ \vec{r}^T \mat{A} + \vec{e}^T \end{bmatrix}, \begin{bmatrix} \mat{A} \\ \vec{r}^T \mat{A} + \vec{e}^T \end{bmatrix} \cdot \mat{R} - \mathsf{bits}(\vec{s}) \otimes \mat{G}, \mat{A}', \vec{r}^T \mat{A}' + (\vec{e}')^T }_{\lambda \in \NN}\]

and the distribution

\[\set{ 1^\lambda, \begin{bmatrix} \mat{A} \\ \delta^T \end{bmatrix}, \Delta, \mat{A}', (\delta')^T }_{\lambda \in \NN}.\]

The second and third elements contain the circular terms.

Hardness

In Lemma 3 of [3], they state several (trivial) reductions between Circular LWE, short-secret LWE, and LWE. However, these reductions only provide uppper bounds on the hardness of Circular LWE.

Constructions built from Circular LWE

To avoid confusion, we only list constructions built from the formalised Circular LWE assumption.

  • Attribute-Based Encryption for Circuits of Unbounded Depth [3]
  • Attribute-Based Encryption for Turing Machines [4]
  • Tensor LWE: There is an assumption combining the ideas from Circular LWE and Tensor LWE to enable ABE for Turing machines.
  • Evasive LWE: Similarly, Hsieh et al. [3] propose a circular version of Evasive LWE. Agrawal et al. [5] provided an attack against Circular Evasive LWE (including the sampler used in the original work).

References

  • [1]Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009. ACM, 169–178. https://doi.org/10.1145/1536414.1536440
  • [2]Zvika Brakerski and Vinod Vaikuntanathan. 2011. Efficient Fully Homomorphic Encryption from (Standard) LWE. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, 2011. IEEE Computer Society, 97–106. Retrieved from https://ia.cr/2011/344
  • [3]Yao-Ching Hsieh, Huijia Lin, and Ji Luo. 2023. Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, 2023. IEEE, 415–434. Retrieved from https://ia.cr/2023/1716
  • [4]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
  • [5]Shweta Agrawal, Anuja Modi, Anshu Yadav, and Shota Yamada. 2025. Evasive LWE: Attacks, Variants & Obfustopia. IACR Cryptol. ePrint Arch. 2025, (2025), 375. Retrieved from https://ia.cr/2025/375