Adaptive LWE

Propose Edit

Updated:

Adaptive LWE was proposed by Quach, Wee, and Wichs in 2018 [1]. Adaptive LWE enables the adversary to define which LWE samples should provide additional structure by adding a gadget matrix to \(\set{\mat{A}_i + x_i \cdot \mat{G}}_{i \in [k]}\) after seeing \(\set{\mat{A}_i}_{i \in [k]}\).

Definition

Adaptive LWE\(_{n,m',k,q,\chi}\)

Let \(\chi\) be a distribution over \(\ZZ\), \(m = n \ceil{\log q}\), and \(\adv = (\adv_0,\adv_1)\) be a two-stage adversary. Sample \(\mat{A}_i \sample \ZZ_q^{n \times m}\), \(\vec{s} \sample \ZZ_q^n\), and \(\vec{e}_i\sample \chi^m\) for \(i \in [k]\). Further, sample \(\mat{A}_{k+1} \sample \ZZ_q^{n \times m'}\) and \(\vec{e}_{k+1} \sample \chi^{m'}\). Given \((\mat{A}_i)_{i \in [k]}\), the first stage of the adversary picks \(\vec{x} \in \set{0,1}^k\). Then, the adversary is asked to distinguish between the distribution

\[\left( \set{ \left(\mat{A}_i, \vec{s}^T \cdot \left(\mat{A}_i + x_i \cdot \mat{G}\right) + \vec{e}_i^T \right)}_{i \in [k]}, \left(\mat{A}_{k+1}, \vec{s}^T \cdot \mat{A}_{k+1} + \vec{e}_{k+1}^T\right) \right)\]

and the distribution

\[\set{\mathcal{U}\left(\ZZ_q^{n \times m}\right) \times \mathcal{U}\left(\ZZ_q^{1 \times m}\right)}_{i \in [k]} \times \mathcal{U}\left(\ZZ_q^{n \times m'}\right) \times \mathcal{U}\left(\ZZ_q^{1 \times m'}\right).\]

Hardness

Quach et al. [1] note that the hardness of Adaptive LWE would immediately follow from LWE if the adversary would be forced to choose \(\vec{x}\) before seeing \(\set{\mat{A}_i}_{i \in [k]}\). Alternatively, they argue about the hardness of the assumption by providing a reduction with exponential loss-factor \(2^{k}\), where the reduction guesses the choice of \(\vec{x}\) in advance. Then, they present a more optimistic choice of parameters.

In Section 7 of [2], Abram, Malavolta, and Roy provide an attack on the aforementioned optimistic choice of parameters. They exploit the fact that \(\vec{x}\) can be chosen after \(\adv\).

Constructions built from Adaptive LWE

  • Laconic Function Evaluation [1], which has applications in MPC
  • Secret-Sharing for Boolean Formulae [3]
  • Key-Policy and Ciphertext-Policy Attribute-Based Encryption for Boolean Formulae [3]
  • Decomposed LWE also adds structure to LWE by adding a gadget matrix to \(\mat{A}\). However, not adaptively.

References

  • [1]Willy Quach, Hoeteck Wee, and Daniel Wichs. 2018. Laconic Function Evaluation and Applications. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, 2018. IEEE Computer Society, 859–870. Retrieved from https://ia.cr/2018/409
  • [2]Damiano Abram, Giulio Malavolta, and Lawrence Roy. 2025. Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, 2025. ACM, 1875–1886. Retrieved from https://ia.cr/2025/336
  • [3]Hanjun Li, Huijia Lin, and Ji Luo. 2022. ABE for Circuits with Constant-Size Secret Keys and Adaptive Security. In Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I (Lecture Notes in Computer Science), 2022. Springer, 680–710. Retrieved from https://ia.cr/2022/659