Extended LWE implied

Propose Edit

Updated:

Extended LWE was proposed by O’Neill, Peikert, and Waters in 2011 [1]. Since then, the assumption has been given in several flavours with the same core idea of providing a hint on the LWE error. This idea and assumption has since been generalised by Error-Leakage LWE, Hint-MLWE, and Leaky LWE. However, the assumption itself was utilised to provide optimised zero-knowledge proofs, advanced public-key encryption and functional encryption.

Definition

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

Let \(\chi,\chi'\) be distributions over \(\ZZ\) and \(\adv = (\adv_0, \adv_1)\) be a two-stage adversary. Sample \(\mat{A} \sample \ZZ_q^{m \times n}\), \(\vec{s}_i \sample \ZZ_q^n\), \(\vec{e}_i \sample \chi^m\), \(e'_i \sample \chi'\), \(\vec{z} \leftarrow \adv_0(1^m)\) and \(\vec{u}_i \sample \ZZ_q^m\) for \(i \in [k]\). The adversary \(\adv_1\) is then asked distinguish between the distributions

\[\left( \mat{A}, (\mat{A} \cdot \vec{s}_i + \vec{e}_i)_{i \in [k]}, \vec{z}, (\langle \vec{z}, \vec{e}_i \rangle + e'_i)_{i \in [k]} \right) \text{ and } \left( \mat{A}, \vec{u}_i, \vec{z}, (\langle \vec{z}, \vec{e}_i \rangle + e'_i)_{i \in [k]} \right).\]

Extended LWE provides a single hint on the LWE error. Please note that almost every paper introduces a slightly different definition of Extended LWE and the above captures most of them. We abuse notation by setting \(\adv_0\) to some distribution to define sampling \(\vec{z}\) from the specified distribution.

For example, the paper that originally introduced Extended LWE [1] sets \(k:=1\), \(\adv_0 := D_{\ZZ^m, r}\), \(\chi := D_{\ZZ,s}\) and \(\chi' := D_{\ZZ,s'}\). Other papers such as [2] only defines \(k=1\), \(\chi := D_{\ZZ,s}\) and removes the error term \(e'\) in the hint, which we’ll formalise as \(\chi' := \set{0}\). Furthermore, several papers [3][4][5][6] utilise and analyse the module-version of (Multi-Hint) Extended-LWE. Finally, the papers [5][6] introduce one or multiple scalars in the hint-term and only output the sign of each entry.

Variants

Multi-Hint Extended-LWE\(_{n,m,q,\chi,\chi',t}\)

Let \(\chi,\chi'\) be distributions over \(\ZZ\) and \(\adv = (\adv_0, \adv_1)\) be a two-stage adversary. Sample \(\mat{A} \sample \ZZ_q^{m \times n}\), \(\vec{s} \sample \ZZ_q^n\), \(\vec{e} \sample \chi^m\), \(\vec{e}' \sample \chi'\), \(\mat{Z} \leftarrow \adv_0(1^t, 1^m)\) and \(\vec{u} \sample \ZZ_q^m\). The adversary \(\adv_1\) is then asked distinguish between the distributions

\[\left( \mat{A}, \mat{A} \cdot \vec{s} + \vec{e}, \vec{z}, \mat{Z} \cdot \vec{e} + \vec{e}' \right) \text{ and } \left( \mat{A}, \vec{u}, \vec{z}, \mat{Z} \cdot \vec{e} + \vec{e}' \right).\]

The Multi-Hint Extended-LWE assumption is introduced in [2] with \(\chi := D_{\ZZ,s}\), no error term on the hint \(\chi' := \set{0}\), and arbitrary distribution \(\adv_0 := \tau\). They provide a reduction from LWE to Multi-Hint Extended LWE in Theorem 4.

Hardness

Due to the varying definitions of Extended LWE, we group the results by definition.

  • \(\chi' = \set{0}\): Lemma 4.7 and 4.8 of [7] provide reductions from a First-is-errorless variant of LWE to Extended LWE. First-is-errorless LWE is previously shown as at least as hard as LWE in Lemma 4.3.
  • \(k=1\), \(\chi' = D_{\ZZ,s'}\) and \(\adv_0 = \tau\): Section 3 of [8] provides a brief description of an efficient attack on Extended LWE if too many-hints are given out and \(\tau\) is Subgaussian. Further, they provide a reduction from LWE to Extended LWE in Theorem 3.1.
  • \(k=1\), \(\chi = D_{\ZZ,s}\) and \(\chi' = D_{\ZZ, s'}\): In Section 6.2.4 of [1], the authors hint at a straightforward reduction from LWE to Extended LWE.
  • Lyubashevsky, Nguyen and Seiler’s module-definition [5] includes additional scalars and they give a reduction from non-algebraic LWE to non-algebraic Extended LWE in Appendix D.
  • Extended Module-LWE with \(\adv_0 = \tau\) and \(\chi' = \set{0}\): The authors of [4] utilises First-t-are-errorless variant of LWE as an intermediate step in the reduction from M-LWE to Extended LWE, which itself is an intermediate result to reduce to Binary-Secret Module-LWE.
  • Extended Multi-Hint Module-LWE with \(k=1\), \(\chi = D_{\ZZ,s}\) and it only hands out the trace of each hint: Lemma 3.8 of [3] formalises a reduction from M-LWE to Extended M-LWE, which also uses the First-t-are-errorless LWE as an intermediate step and yields an intermediate step in a reduction from M-LWE to M-LWR itself.

Constructions built from Extended LWE

  • Zero-Knowledge Proofs [5][6]
  • Public-Key Encryption [1]
  • Functional Encryption for inner products [8][2]
  • LWE with Error-Leakage is a direct generalisation of Extended LWE and closely related to Multi-Hint Extended LWE.
  • Hint-MLWE can accomodate for some leakage of the LWE error.
  • Leaky LWE generalises (Multi-Hint) Extended LWE and additionally allows for some leakage of the LWE secret.

References

  • [1]Adam O’Neill, Chris Peikert, and Brent Waters. 2011. Bi-Deniable Public-Key Encryption. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings (Lecture Notes in Computer Science), 2011. Springer, 525–542. Retrieved from https://ia.cr/2011/352
  • [2]Shweta Agrawal, Libert Benoı̂t, and Damien Stehlé. 2016. Fully Secure Functional Encryption for Inner Products, from Standard Assumptions. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III (Lecture Notes in Computer Science), 2016. Springer, 333–362. Retrieved from https://ia.cr/2015/608
  • [3]Jacob Alperin-Sheriff and Daniel Apon. 2016. Dimension-Preserving Reductions from LWE to LWR. IACR Cryptol. ePrint Arch. 2016, (2016), 589. Retrieved from https://ia.cr/2016/589
  • [4]Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen. 2021. On the Hardness of Module-LWE with Binary Secret. In Topics in Cryptology - CT-RSA 2021 - Cryptographers’ Track at the RSA Conference 2021, Virtual Event, May 17-20, 2021, Proceedings (Lecture Notes in Computer Science), 2021. Springer, 503–526. Retrieved from https://ia.cr/2021/265
  • [5]Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler. 2021. Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments. In Public-Key Cryptography - PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10-13, 2021, Proceedings, Part I (Lecture Notes in Computer Science), 2021. Springer, 215–241. Retrieved from https://ia.cr/2020/1448
  • [6]Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Maxime Plançon. 2022. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. In Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 71–101. Retrieved from https://ia.cr/2022/284
  • [7]Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. 2013. Classical hardness of learning with errors. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, 2013. ACM, 575–584. https://doi.org/10.1145/2488608.2488680
  • [8]Jacob Alperin-Sheriff and Chris Peikert. 2012. Circular and KDM Security for Identity-Based Encryption. In Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings (Lecture Notes in Computer Science), 2012. Springer, 334–352. https://doi.org/10.1007/978-3-642-30057-8_20