As a tool in the reduction, we show that there is a ``lossy mode'' for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple new constructions of deterministic encryption, lossy trapdoor functions and reusable extractors.
Our approach is inspired by a technique of Goldwasser et al. [GKPV10] from ICS '10, which implicitly showed the existence of a ``lossy mode'' for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.
Category / Keywords: foundations / Learning with Errors, Learning with Rounding, Lossy Trapdoor Functions, Deterministic Encryption Date: received 21 Feb 2013 Contact author: wichs at ccs neu edu Available format(s): PDF | BibTeX Citation Version: 20130227:162718 (All versions of this report) Short URL: ia.cr/2013/098