Cryptology ePrint Archive: Report 2020/1238

Hardness of Module-LWE and Ring-LWE on General Entropic Distributions

Hao Lin and Yang Wang and Mingqiang Wang

Abstract: The hardness of Entropic LWE has been studied in a number of works. However, there is not work study the hardness of algebraically structured LWE with entropic secrets. In this work, we conduct a comprehensive study on establishing hardness reductions for Entropic Module-LWE and Entropic Ring-LWE. We show an entropy bound that guarantees the security of arbitrary Entropic Module-LWE and Entropic Ring-LWE, these are the first results on the hardness of algebraically structured LWE with entropic secrets. One of our central techniques is a new generalized leftover hash lemma over ring and a new decomposition theorem for continuous Gaussian distribution on KR, which might be of independent interests.

Category / Keywords: foundations / Lattice-based cryptography, Module learning with errors, Ring learning with errors, Entropic Module-LWE, Entropic Ring-LWE.

Date: received 7 Oct 2020

Contact author: lhao17 at mail sdu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20201009:113322 (All versions of this report)

Short URL: ia.cr/2020/1238