LWE Problem with Uniform Secret and Errors and Its Application

The learning with errors (LWE) assumption has been widely applied in cryptography for its unique properties in complexity. It is viewed as linear random decoding problem in Euclidian norm. Many variants of its average hardness are given in recent years. We introduce a variant of learning with errors problem in which the coordinates of secret and errors are all chosen from the uniform distribution over a small interval, where we use a transformation technique given by Applebaum et al. It maps LWE samples with uniform secret to LWE samples with the secret which accords to the same distribution of the errors. Meanwhile, there are only a small number of samples lost. The average hardness of our variant is based on the LWE with uniform errors. It enjoys a worst-to-average-case reduction and removes the gaussian sampler. We also construct a public-key encryption with key-dependent message security based on our new LWE variant. It is a variant of Regevs LWE-based schemes. Our scheme reduces the computational overhead of algorithms of key-generation and encryption by replacing the gaussian sampler, which costs a lot of time and space in practice, with the uniform sampler in small interval.