CryptoDB
On the Hardness of the Computational Ring-LWR Problem and Its Applications
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: | |
---|---|
Download: | |
Presentation: | Slides |
Conference: | ASIACRYPT 2018 |
Abstract: | 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 R-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 R-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 R-LWR with polynomial modulus prior to this work, to the best of our knowledge. |
BibTeX
@inproceedings{asiacrypt-2018-29150, title={On the Hardness of the Computational Ring-LWR Problem and Its Applications}, booktitle={Advances in Cryptology – ASIACRYPT 2018}, series={Lecture Notes in Computer Science}, publisher={Springer}, volume={11272}, pages={435-464}, doi={10.1007/978-3-030-03326-2_15}, author={Long Chen and Zhenfeng Zhang and Zhenfei Zhang}, year=2018 }