Thumbnail
Access Restriction
Open

Author Alwen, Joël ♦ Krenn, Stephan ♦ Pietrzak, Krzysztof ♦ Wichs, Daniel
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword New Reduction ♦ Modulus-to-error Ratio ♦ Lossy Mode ♦ Lwr Problem ♦ Deterministic Encryption ♦ Simple New Construction ♦ Weakly Random Secret ♦ Worst-case Hardness ♦ New Application ♦ Rosen Bpr12 ♦ Deterministic Rounding ♦ Main Open Problem ♦ Reveal Partial Information ♦ Reusable Extractor ♦ Approximation Factor ♦ Random Error ♦ Sufficient Minentropy ♦ Lossy Trapdoor Function ♦ Polynomial Modulus
Abstract Abstract. The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen [BPR12] at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem of [BPR12] and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. 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 minentropy, 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article