Universal product learning with errors: A new variant of LWE for lattice-based cryptography

The middle product learning with errors problem (MP-LWE) is a variant of the learning with errors problem (LWE). The public-key cryptography under MP-LWE assumption gets an equilibrium between “efficiency” and “security”. However, the hardness of MP-LWE has not been sufficiently explored since its i...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2022-05, Vol.915, p.90-100
Main Authors: Yang, Shaojun, Huang, Xinyi
Format: Article
Language:English
Subjects:
Asymmetric middle product
MP-LWE
PLWE
UP-LWE
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The middle product learning with errors problem (MP-LWE) is a variant of the learning with errors problem (LWE). The public-key cryptography under MP-LWE assumption gets an equilibrium between “efficiency” and “security”. However, the hardness of MP-LWE has not been sufficiently explored since its introduction. So in this paper, we focus on the hardness of MP-LWE. By the axiomatic method, we first investigate the essential attributes about the middle product in MP-LWE. Then we present the formal definition of universal product and the corresponding universal product learning with errors problem (UP-LWE). In this sense, MP-LWE can be viewed as an instance of UP-LWE. Then we proved that for more polynomials than those have been proved in the literature, PLWE(f) can be reduced to MP-LWE. In other words, we improve the result about the hardness of MP-LWE. Furthermore, we define the asymmetric middle product which can be viewed as a construction of universal product. The corresponding UP-LWE is discussed. It provides much more flexible parameter setting than MP-LWE.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2022.02.032