Paper 2021/1026
On the Hardness of Ring/Module/Polynomial LWR Problems
Yang Wang and Yanmin Zhao and Mingqiang Wang
Abstract
The Learning with Rounding (LWR) problem is an important variant of the Learning with Errors (LWE) problem. Recently, Liu {\it{et al.}} proposed a comprehensive study of LWR problems defined over algebraic number fields in CRYPTO 2020. However, their search-to-decision reductions of LWR problems depend heavily on the existence of the so-called {\it{Normal Integral Basis}} (NIB). Meanwhile, the aesthetic deficiency is a lack of discussions of choices of secret $s$, and one may could not show the {\it{worst-case}} hardness of decision LWR problems {\it{strictly}} even for fields with NIB. In this paper, we give a more refined analysis of reductions between different LWR problems. Our contributions are summarized as follows: (1) We give a search-to-decision reduction of ring/module LWR problems defined over {\it{any}} number field $K=\QQ[x]/(\Phi(x))$ which is {\it{Galois}} over $\QQ$ with suitable parameters, {\it{regardless of the existence of NIB}}. (2) To the best of our knowledge, we give the first reduction from search ring/module LWE problems to corresponding search/decision LWR problems. Hence, combining known hardness results of LWE problems, we could reduce {\it{worst-case}} ideal/module lattices problems to search/decsion LWR problems {\it{strictly}}. (3) For the first time, we show the {\it{worst-case}} hardness of search/decision polynomial LWR problems defined over polynomial rings $\ZZ_q[x]/(\Phi(x))$ with {\it{comparable small parameters}}, which could be regarded as a theoretical support for some ring/module LWR based crypto-systems, e.g. the NIST Round $3$ candidate - Saber. As a finish, we also give some hardness results of middle product polynomial LWR problems.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Lattice-based CryptographyRingModule LWR ProblemsPolynomial LWR ProblemsHardness Reduction
- Contact author(s)
-
wyang1114 @ sdu edu cn
wangmingqiang @ sdu edu cn
ymzhao @ cs hku hk - History
- 2021-09-01: withdrawn
- 2021-08-06: received
- See all versions
- Short URL
- https://ia.cr/2021/1026
- License
-
CC BY