分野別セミナー

he hardness of the Learning-with-errors (LWE) Problem has become one of the most useful assumptions in cryptography. Many applications, like public key cryptography, hierarchical identity-based encryption, and fully homomorphic encryption can be based on this assumption. Furthermore, the LWE Problem exhibits a worst-to-average-case reduction making the LWE assumption very plausible.
This worst-to-average-case reduction is based on a Fourier argument and therefore the error distribution for current applications of LWE must be chosen with a gaussian distribution. Sampling from a gaussian distribution is cumbersome and it is hence highly desirable to prove worst-to-average-case reductions for other distributions, in particular for the uniform distribution which can be sampled very efficiently.
We present the first worst-to-average case reduction for an LWE problem with uniformly distributed errors. This new worst-to-average-case connection comes with a slight drawback and we need to use a bounded variant of the LWE problem, where the number of samples to be learned from is fixed in advance. However, most applications of LWE can be based on the bounded variant.
The proof is based on a new tool called Lossy Codes. These codes are indistinguishable from good error correcting codes, but provably lose information when noisy codewords are decoded. The concept of lossy codes can further be used to transform other lattice/coding-based hardness assumptions like Learning Parity with Noise, thereby giving rise to primitives like lossy trapdoor functions from this assumption.