Common Notation

Augmented LWE implied

Propose Edit

Updated:

Augmented LWE was introduced by Bansarkhani, Dagdelen, and Buchmann in 2015 [1]. It augments the error-term of LWE with information about a message \(\vec{m}\) given as input.

Definition

Augmented LWE\(_{n,m_1,m_2,q,s}\)

Let \(k=\log q\), \(m = m_1 + m_2\) where \(k | m_2\) and \(H: \ZZ_q^n \times \ZZ_q^{m_1} \rightarrow \set{0,1}^{m_2}\) be a function. On input \(\vec{m} \in \set{0,1}^{m_2}\), sample \(\mat{A} \sample \ZZ_q^{n \times m}\), \(\vec{s} \sample \ZZ_q^n\), and \(\vec{e}_1 \sample D_{\ZZ^m, s}\). Define \(\vec{v} = \mathsf{encode}(H(\vec{s}, \vec{e}_1) \oplus \vec{m}) \in \ZZ_q^{m_2/k}\) and sample \(\vec{e}_2 \sample D_{\Lambda_q^{\vec{v}}(\mat{G}), s}\). Define \(\vec{e} = (\vec{e}_1, \vec{e}_2)\). An adversary is asked to distinguish between samples from the distribution

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

We provide the decisional definition of Augmented LWE. Due to the introduction of a message \(\vec{m}\), the authors [1] provide a decisional, a search-secret, and a search-message version, where \(\vec{m} \sample \set{0,1}^{m_2}\).

Hardness

Theorem 1 and Theorem 2 of [1] state that Augmented LWE\(_{n,m_1,m_2,q,s}\) is at least as hard as LWE\(_{n,m,q,D_{\ZZ,s}}\) if \(H\) is a random oracle and \(s \geq \eta_\epsilon(\Lambda_q^\perp(\mat{G}))\) for \(\epsilon = \negl{\lambda}\).

Constructions built from Augmented LWE

  • Public-Key Encryption [1][2]
  • Private Stream Aggregation [3][4]
  • Private Weighted Sum Aggregation [5]

References

  • [1]Rachid El Bansarkhani, Özgür Dagdelen, and Johannes Buchmann. 2015. Augmented Learning with Errors: The Untapped Potential of the Error Term. In Financial Cryptography and Data Security - 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected Papers (Lecture Notes in Computer Science), 2015. Springer, 333–352. Retrieved from https://ia.cr/2014/733
  • [2]Rachid El Bansarkhani. 2019. LARA: A Design Concept for Lattice-Based Encryption. In Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Frigate Bay, St. Kitts and Nevis, February 18-22, 2019, Revised Selected Papers (Lecture Notes in Computer Science), 2019. Springer, 377–395. Retrieved from https://ia.cr/2017/049
  • [3]Daniela Becker, Jorge Guajardo, and Karl-Heinz Zimmermann. 2018. Revisiting Private Stream Aggregation: Lattice-Based PSA. In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018, 2018. The Internet Society. Retrieved from https://www.ndss-symposium.org/wp-content/uploads/2018/02/ndss2018_02B-3_Becker_paper.pdf
  • [4]Johannes Ottenhues and Alexander Koch. 2024. LaPSuS - A Lattice-Based Private Stream Aggregation Scheme Under Scrutiny. In Security and Cryptography for Networks - 14th International Conference, SCN 2024, Amalfi, Italy, September 11-13, 2024, Proceedings, Part II (Lecture Notes in Computer Science), 2024. Springer, 228–248. Retrieved from https://ia.cr/2024/1159
  • [5]Andreea B. Alexandru and George J. Pappas. 2022. Private Weighted Sum Aggregation. IEEE Trans. Control. Netw. Syst. 9, 1 (2022), 219–230. Retrieved from https://arxiv.org/abs/2010.10640