Direct Reduction for Learning with Rounding and its Applications

Shi Bai, Katharina Boudgoust, Dipayan Das +3 more

Joël Alwen, Stephan Krenn, Krzysztof Pietrzak +1 more

Andrej Bogdanov, Siyao Guo, Daniel Masny +2 more

Zhuang Shan, Leyou Zhang, Qiqi Lai

Pseudorandom functions (PRFs) are a very important tool in cryptography, and the learning with rounding (LWR) problem is one of the main issues in their construction. LWR problem, is to find from ⌊ A s ⌋ p , where and is the rounding function. The LWR problem is considered a variant of the learning with error (LWE) problem, that is, to find s from b = A s + e , where , and LWE has been reduced to GapSVP and SIVP. The hardness of the lattice problems is the security foundation of the issued schemes. The best‐known reduction for LWR was completed using information‐theoretic entropy arguments, and the reduction requires q ≥ 2 n m p . It does not directly reduce to the closest vector problem (CVP) problem, but rather to the LWE problem. However, the reduction in the aforementioned work significantly reduces the difficulty of LWR. To more accurately characterize the hardness of LWR, this paper uses statistical approximation and a Quantum Fourier Transform to reduce LWR to the CVP, thereby ensuring the hardness of LWR. Furthermore, unlike the previous conclusions, our reduction involves minimal loss and has broad security conditions, requiring only that , where q and p are prime numbers and 0 < α < 1.

Joël Alwen, Stephan Krenn, Krzysztof Pietrzak +1 more

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.

Andrej Bogdanov, Siyao Guo, Daniel Masny +2 more

We show the following reductions from the learning with errors problem (LWE) to the learning with rounding problem (LWR): (1) Learning the secret and (2) distinguishing samples from random strings is at least as hard for LWR as it is for LWE for efficient algorithms if the number of samples is no larger than O(q/Bp), where q is the LWR modulus, p is the rounding modulus, and the noise is sampled from any distribution supported over the set {−B,..., B}. Our second result generalizes a theorem of Alwen, Krenn, Pietrzak, and Wichs (CRYPTO 2013) and provides an alternate proof of it. Unlike Alwen et al., we do not impose any number theoretic restrictions on the modulus q. The first result also extends to variants of LWR and LWE over polynomial rings. As additional results we show that (3) distinguishing any number of LWR samples from random strings is of equivalent hardness to LWE whose noise distribution is uniform over the integers in the range [−q/2p,..., q/2p) provided q is a multiple of p and (4) the “noise flooding” technique for converting faulty LWE noise to a discrete Gaussian distribution can be applied whenever q = Ω(B