[Resource Topic] 2018/536: On the Hardness of the Computational Ring-LWR Problem and its Applications

Welcome to the resource topic for 2018/536

On the Hardness of the Computational Ring-LWR Problem and its Applications

Authors: Long Chen, Zhenfeng Zhang, Zhenfei Zhang


In this paper, we propose a new assumption, the Computational Learning With Rounding over rings, which is inspired by the computational Diffie-Hellman problem. Assuming the hardness of ring-LWE, we prove this problem is hard when the secret is small, uniform and invertible. From a theoretical point of view, we give examples of a key exchange scheme and a public key encryption scheme, and prove the worst-case hardness for both schemes with the help of a random oracle. Our result improves both speed, as a result of not requiring Gaussian secret or noise, and size, as a result of rounding. In practice, our result suggests that decisional ring-LWR based schemes, such as Saber, Round2 and Lizard, which are among the most efficient solutions to the NIST post-quantum cryptography competition,stem from a provable secure design. There are no hardness results on the decisional ring-LWR with polynomial modulus prior to this work, to the best of our knowledge.

ePrint: https://eprint.iacr.org/2018/536

Slides: https://asiacrypt.iacr.org/2018/files/SLIDES/MONDAY/514/1330-1445/CRLWR - Asiacrypt 2018.key.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .