Paper 2021/1026

On the Hardness of Ring/Module/Polynomial LWR Problems

Yang Wang, 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.