Multiplicative Learning with Errors and Cryptosystems

Abstract

We first introduce a new concept of multiplicative learning with errors (MLWE), which is multiplicative version of the learning with errors (LWE). Then we reduce that the hardness of the search version for MLWE to its decisional version under the condition of modulo of a product of sufficiently large smoothing prime factors. Next we construct the MLWE-based private-key and public-key encryption schemes, and prove that the security of our schemes is based on the worst-case hardness assumption of MLWE. Finally, we discuss the LWE on additive group to the LWE on general abelian group and approximate lattice problem on abelian group.