Common Notation

First-Are-Errorless LWE (FAE-LWE) implied

Propose Edit

Updated:

The first-is-errorless LWE problem was introduced by Brakerski, Langlois, Peikert, Regev, and Stehlé in 2013 [1]. They utilise the problem as an intermediate reduction step towards Extended LWE and Binary-Secret LWE. In subsequent work, the assumption was generalised to first-are-errorless LWE and its module version [2][3].

Definition

FAE-LWE\(_{n,m,k,q,\chi,\mathcal{R}}\)

Let \(\chi\) be a distribution over \(\mathcal{R}\). Sample matrix \(\mat{A} \sample \mathcal{R}_q^{m \times n}\), \(\vec{s} \sample \mathcal{R}_q^n\), and \(\vec{e}' \sample \chi^{m-k}\). Define \(\vec{e} := (0^k, \vec{e}')\). An adversary is asked to distinguish between the distribution

\[\left( \mat{A}, \mat{A} \cdot \vec{s} + \vec{e} \right) \text{ and } \mathcal{U}\left(\mathcal{R}_q^{n \times m}\right) \times \mathcal{U}\left(\ZZ_q^{1 \times m}\right).\]

We provide the module-version of FAE-LWE as defined in [2] to also cover the module-version of the assumption given in [3]. The classical version can be recovered by defining \(\mathcal{R} := \ZZ\). Further, this assumption is utilised and referred to as First-is-errorless LWE in [1][4][3], i.e. \(k = 1\). Finally, the same assumption is called Some-are-errorless LWE in in [5].

Hardness

The first reduction from LWE to first-is-errorless LWE is provided in Lemma 4.3 of [1]. This reduction was generalised by Agrawal et al. [2] to the case, where a constant number of LWE samples is provided without a hint. Reductions for the module version adapt the first proof strategy in Lemma 3.6 of [4] and Lemma 14 of [3].

Constructions built from FAE-LWE

  • (Fully) Homomorphic Encryption [6][5]
  • Extended LWE provides a hint in the form of an inner product on the LWE error.

References

  • [1]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
  • [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]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
  • [4]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
  • [5]Zong-Wu Zhu and Ru-Wei Huang. 2021. Efficient SMC protocol based on multi-bit fully homomorphic encryption. Applied Sciences 11, 21 (2021), 10332.
  • [6]Zengpeng Li, Chunguang Ma, Gang Du, and Weiping Ouyang. 2016. Dual LWE-Based Fully Homomorphic Encryption with Errorless Key Switching. In 22nd IEEE International Conference on Parallel and Distributed Systems, ICPADS 2016, Wuhan, China, December 13-16, 2016, 2016. IEEE Computer Society, 1169–1174. https://doi.org/10.1109/ICPADS.2016.0154