You are looking at a specific version 20180604:214059 of this paper. See the latest version.

Paper 2018/536

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

Long Chen and 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.