Paper 2018/536
On the Hardness of the Computational Ring-LWR Problem and its Applications
Long Chen, Zhenfeng Zhang, and Zhenfei Zhang
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 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.
Note: Revise some typos.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2018
- Keywords
- Lattice TechniquesPublic Key Cryptography
- Contact author(s)
- chenlong0405 @ qq com
- History
- 2019-09-24: last of 2 revisions
- 2018-06-04: received
- See all versions
- Short URL
- https://ia.cr/2018/536
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/536,
author = {Long Chen and Zhenfeng Zhang and Zhenfei Zhang},
title = {On the Hardness of the Computational Ring-{LWR} Problem and its Applications},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/536},
year = {2018},
url = {https://eprint.iacr.org/2018/536}
}
