Fractional LWE: A Nonlinear Variant of LWE

Chris Peikert, Zachary Pepin

Bo Gao, Yanfeng Shi, Chunli Yang +3 more

We construct a flexible lattice based scheme based on semitensor product learning with errors (STP‐LWE), which is a variant of learning with errors problem. We have proved that STP‐LWE is hard when LWE is hard. Our scheme is proved to be secure against indistinguishable chosen message attacks, and it can achieve a balance between the security and efficiency in the hierarchical encryption systems. In addition, our scheme is almost as efficient as the dual encryption in GPV08.

Yilei Chen, Qipeng Liu, Mark Zhandry

We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. The SIS, EDCP, and LWE problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for those variants. Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contributions are introducing a filtering technique and solving LWE given LWE-like quantum states with interesting parameters.

Chris Peikert, Zachary Pepin

Xuyang Wang, Aiqun Hu, Hao Fang

The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.

Sina Shiehian