Paper 2024/1696 Original: eprint.iacr.org/2024/1696 ↗

Revisiting the Robustness of {(R/M)LWR} under Polynomial Moduli and its Applications

Abstract

This work conducts a comprehensive investigation on determining the entropic hardness of (Ring/Module) Learning with Rounding (LWR) under polynomial modulus. Particularly, we establish the hardness of (M)LWR for general entropic secret distributions from (Module) LWE assumptions based on a new conceptually simple framework called rounding lossiness. By combining this hardness result and a trapdoor inversion algorithm with asymptotically the most compact parameters, we obtain a compact lossy trapdoor function (LTF) with improved efficiency. Extending our LTF with other techniques, we can derive a compact all-but-many LTF and PKE scheme against selective opening and chosen ciphertext attacks, solely based on (Module) LWE assumptions within a polynomial modulus. Additionally, we show a search-to-decision reduction for RLWR with Gaussian secrets from a new Rényi Divergence-based analysis.