Learning with Rounding (LWR) standard

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].

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 work has since improved on the provable security of LWR [4].

Note that the reductions presented above were not generalised to the ring- or module-setting. An attempt to prove Ring-LWR secure was made in [5] by giving a reduction from Ring-LWE to a modified version of R-LWR.

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]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
  • [5]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