---
res:
bibo_abstract:
- "The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and
Rosen 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 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.\r\n\r\nAs 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 constructions
of deterministic encryption, lossy trapdoor functions and reusable extractors.\r\n\r\nOur
approach is inspired by a technique of Goldwasser et al. 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.\r\n@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Joel F
foaf_name: Alwen, Joel F
foaf_surname: Alwen
foaf_workInfoHomepage: http://www.librecat.org/personId=2A8DFA8C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Stephan
foaf_name: Krenn, Stephan
foaf_surname: Krenn
foaf_workInfoHomepage: http://www.librecat.org/personId=329FCCF0-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Daniel
foaf_name: Wichs, Daniel
foaf_surname: Wichs
bibo_doi: 10.1007/978-3-642-40041-4_4
bibo_issue: '1'
bibo_volume: 8042
dct_date: 2013^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: 'Learning with rounding, revisited: New reduction properties and applications@'
...