Learning with rounding, revisited: New reduction properties and applications

Alwen, Joël and Krenn, Stephan and Pietrzak, Krzysztof and Wichs, Daniel (2013) Learning with rounding, revisited: New reduction properties and applications. In: CRYPTO: International Cryptology Conference, Ausgust 18-22, 2013, Santa Barbara, CA, USA.

[img] Text
098.pdf - Submitted Version
Available under License Creative Commons Attribution.
[IST-2016-684-v1+1]
Download (574Kb)
Official URL: http://dx.doi.org/10.1007/978-3-642-40041-4_4

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. 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 constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our 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.

Item Type: Conference or Workshop Item (Paper)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Pietrzak Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 02 Dec 2016 08:40
Last Modified: 05 Sep 2017 14:09
URI: https://repository.ist.ac.at/id/eprint/684

Actions (login required)

View Item View Item