Common Notation

Learning with Rounding (LWR) implied

Propose Edit

Updated:

The Learning with Rounding (LWR) problem was introduced by Banerjee, Peikert, and Rosen [1] as a derandomized alternative to Learning with Errors. Instead of hiding the linear structure of the underlying lattice by adding random noise, LWR obfuscates it by deterministically rounding the product from a larger modulus \(q\) to a smaller modulus \(p\).

By avoiding the requirement to sample discrete Gaussian noise (which is hard to implement in a side-channel secure way), LWR yields a solid foundation to build efficient cryptographic primitives such as PRFs or PKE.

Definition

First, we need to define a rounding function \(\lfloor \cdot \rceil_p: \ZZ_p \rightarrow \ZZ_q\) for \(q \geq p \geq 2\) in the following way.

\[\lfloor x \rceil_p = \left\lfloor \frac{p}{q} \cdot (x \bmod q) \right\rceil \bmod p\]

Applying this function to a vector or matrix denotes the component-wise application of the function. Furthermore, the function naturally adapts to other rounding methods like \(\lfloor \cdot \rfloor\) or \(\lceil \cdot \rceil\). Notice that \(\lfloor \cdot \rfloor_p\) is equivalent to dropping the least-significant digits in base \(b\) if \(q\) and \(p\) are both powers of the same base \(b\).

Search LWR\(_{n,m,q,p}\)

Let matrix \(\mat{A} \in \ZZ_q^{m \times n}\) and secret vector \(\vec{s} \in \ZZ_q^n\) be chosen uniformly at random. Given the matrix \(\mat{A}\) and the vector \(\lfloor \vec{b} \rceil_p = \lfloor \mat{A} \cdot \vec{s} \rceil_p \in \ZZ_p^m\), an adversary is asked to find the secret vector \(\vec{s}\).

By rounding to the nearest integer modulo \(p\), the challenger implicitly introduces a noise vector whose norm depends on \(q\) and \(p\).

Decision LWR\(_{n,m,q,p}\)

Let matrix \(\mat{A} \in \ZZ_q^{m \times n}\) and secret vector \(\vec{s} \in \ZZ_q^n\) be chosen uniformly at random. An adversary is asked to distinguish between the LWR distribution \((\mat{A}, \lfloor \vec{b} \rceil_p = \lfloor \mat{A} \cdot \vec{s} \rceil_p)\) and a uniformly random distribution over \(\ZZ_q^{m \times n} \times \ZZ_p^m\).

In [1], they define a ring-version of LWR and build a PSF from it. Similarly, there exists a module-version defined in [2]. LWR can also be formulated where the secret does follow another secret distribution than the uniform distribution.

Hardness

There are several papers providing a reduction from LWE to LWR. The first one required the modulus \(q\) and the modulus-to-error ratio to grow super-polynomial [1]. These requirement could be improved in [3] to polynomially sized moduli and modulus-to-error ratios. Further follow-up works have since improved on the provable security of LWR [4] [5] [6] [7].

Note that not all of the reductions presented above were generalised to the ring- or module-setting. The original reduction from [1] works for Ring-LWR as well. The reduction proven in [4] works for Module-LWR, but not for Ring-LWR. An attempt to prove Ring-LWR secure was made in [8] by giving a reduction from Ring-LWE to a modified version of Ring-LWR. For specific rounding functions it was improved in [9].

Constructions built from LWR

  • Pseudorandom Functions [1]
  • Key Exchange Mechanism [2]
  • Public-Key Encryption [2]

References

  • [1]Abhishek Banerjee, Chris Peikert, and Alon Rosen. 2012. Pseudorandom Functions and Lattices. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings (Lecture Notes in Computer Science), 2012. Springer, 719–737. Retrieved from https://ia.cr/2011/401
  • [2]Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren. 2018. Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM. In Progress in Cryptology - AFRICACRYPT 2018 - 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7-9, 2018, Proceedings (Lecture Notes in Computer Science), 2018. Springer, 282–305. Retrieved from https://ia.cr/2018/230
  • [3]Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. 2013. Learning with Rounding, Revisited - New Reduction, Properties and Applications. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I (Lecture Notes in Computer Science), 2013. Springer, 57–74. Retrieved from https://ia.cr/2013/098
  • [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]Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen. 2016. On the Hardness of Learning with Rounding over Small Modulus. In Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I (Lecture Notes in Computer Science), 2016. Springer, 209–224. Retrieved from https://ia.cr/2015/769
  • [6]Shi Bai, Tancrède Lepoint, Adeline Roux-Langlois, Amin Sakzad, Damien Stehlé, and Ron Steinfeld. 2018. Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather than the Statistical Distance. J. Cryptol. 31, 2 (2018), 610–640. Retrieved from https://ia.cr/2015/483
  • [7]Clément Hoffmann, Pierrick Méaux, Mélissa Rossi, and François-Xavier Standaert. 2026. Learning with Errors with Output Dependencies: LWE, LWR, and Physical Learning Problems Under the Same Umbrella. In Post-Quantum Cryptography - 17th International Workshop, PQCrypto 2026, Saint-Malo, France, April 14-16, 2026, Proceedings, Part I (Lecture Notes in Computer Science), 2026. Springer, 287–318. Retrieved from https://ia.cr/2025/2225
  • [8]Long Chen, Zhenfeng Zhang, and Zhenfei Zhang. 2018. On the Hardness of the Computational Ring-LWR Problem and Its Applications. In Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part I (Lecture Notes in Computer Science), 2018. Springer, 435–464. https://doi.org/10.1007/978-3-030-03326-2_15
  • [9]Feng-Hao Liu and Zhedong Wang. 2020. Rounding in the Rings. In Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II (Lecture Notes in Computer Science), 2020. Springer, 296–326. https://doi.org/10.1007/978-3-030-56880-1_11