Common Notation

Binary-Secret LWE implied

Propose Edit

Updated:

Binary-Secret LWE was introduced in 2010 by Goldwasser, Kalai, Peikert, and Vaikuntanathan [1], and was later proven in [2]. The name of the assumption is descriptive as Binary-Secret LWE literally restricts LWE to choosing its secret as a binary vector.

The definition can naively be extended to both the ring and the module setting but hardness is only provided for the classical LWE and a special regime of MLWE (which leaves the hardness for the ring variant unproven).

Definition

Binary-Secret LWE\(_{n,m,q,\sigma}\)

Let matrix \(\mat{A} \in \ZZ_q^{m \times n}\) and secret vector \(\vec{s} \in \set{-1,1}^n\) be chosen uniformly at random. Sample \(\vec{e} \sample D_{\ZZ, \sigma}^m\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod q) \text{ and } \mathcal{U}\left(\ZZ_q^{m \times n}\right) \times \mathcal{U}\left(\ZZ_q^m\right).\]

Note that we define Binary-Secret LWE w.r.t. a secret in \(\set{-1,1}^n\). This definition is also referred to as Fixed-Norm LWE [3] as the norm of the secret is fixed. Binary-Secret LWE with secret in \(\set{0,1}^n\) is equivalent to Fixed-Norm LWE via the public transform \(\vec{s} \mapsto (2\vec{s} - \vec{1})\). The alternative name was brought up by Gupte, Vafa, and Vaikuntanathan in 2022 [3], where they formalise the statement that Fixed-Norm LWE is at least as hard as Binary-Matrix LWE in Theorem 7.

Hardness

A first version was provided by the original authors but not efficient due to a severe blow-up in the noise rate. The hardness was proven by Brakerski, Langlois, Peikert, Regev and Stéhlé [2] (Theorem 4.1), proving that Binary-Secret LWE is at least as hard as Decision LWE throught a hybrid argument with intermediate problems first-is-errorless LWE and Extended-LWE (both reduced to the standard LWE).

Later in 2018, the proof was shortened and simplified by Micciancio [4] (Corollary 1), with same range of parameters (just a lower growth of the noise than [2]). The gain is due to the definition of the secret over \(\set{-1,1}^n\) instead of \(\set{0,1}^n\).

Furthermore, Boudgoust, Jeudy, Roux-Langlois, and Wen provided a reduction from Module-LWE with intermediate problems first-is-errorless LWE and Extended-LWE to Module LWE with binary secret in Lemma 18 of [5]. This proof has an impact on the choice of dimension, which leaves the question of the difficulty of the ring variant unsolved.

Note that there is a paper claiming a more efficient attack on Binary-Secret LWE using machine learning [6]. However, the evidence presented in [7] shows that there is no benefit of using machine learning over existing approaches.

Constructions built from Binary-Secret LWE

  • Public-Key Encryption [8]
  • LWE can be reduced to Binary-Secret LWE.
  • Continuous LWE is at least as hard as Fixed-Norm LWE.

References

  • [1]Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. 2010. Robustness of the Learning with Errors Assumption. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, 2010. Tsinghua University Press, 230–240. Retrieved from https://web.eecs.umich.edu/ cpeikert/pubs/robustlwe.pdf
  • [2]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
  • [3]Aparna Gupte, Neekon Vafa, and Vinod Vaikuntanathan. 2022. Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, 2022. IEEE, 1162–1173. Retrieved from https://ia.cr/2022/437
  • [4]Daniele Micciancio. 2018. On the Hardness of Learning With Errors with Binary Secrets. Theory Comput. 14, 1 (2018), 1–17. Retrieved from https://ia.cr/2018/988
  • [5]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
  • [6]Cathy Yuanchen Li, Jana Sotáková, Emily Wenger, Mohamed Malhou, Evrard Garcelon, François Charton, and Kristin E. Lauter. 2023. SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, 2023. ACM, 2606–2620. Retrieved from https://ia.cr/2023/340
  • [7]Alexander Karenin, Elena Kirshanova, Julian Nowakowski, Eamonn W. Postlethwaite, Ludo N. Pulles, Fernando Virdia, and Paul Vié. 2026. Cool + Cruel = Dual, and New Benchmarks for Sparse LWE. In Advances in Cryptology - EUROCRYPT 2026 - 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10-14, 2026, Proceedings, Part IV (Lecture Notes in Computer Science), 2026. Springer, 304–333. Retrieved from https://ia.cr/2025/1002
  • [8]Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. 2022. Public-Key Encryption from Continuous LWE. Electron. Colloquium Comput. Complex. TR22, (2022). Retrieved from https://ia.cr/2022/093