IACR News item: 27 February 2013
Joel Alwen, Stephan Krenn, Krzysztof Pietrzak, Daniel Wichs
ePrint ReportAs 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.
Additional news items may be found on the IACR news page.