Welcome to the resource topic for 2024/2058
Title:
Learning with Errors from Nonassociative Algebras
Authors: Andrew Mendelsohn, Cong Ling
Abstract:We construct a provably-secure structured variant of Learning with Errors (LWE) using nonassociative cyclic division algebras, assuming the hardness of worst-case structured lattice problems, for which we are able to give a full search-to-decision reduction, improving upon the construction of Grover et al. named `Cyclic Learning with Errors’ (CLWE). We are thus able to create structured LWE over cyclic algebras without any restriction on the size of secret spaces, which was required for CLWE as a result of its restricted security proof. We reduce the shortest independent vectors problem in ideal lattices, obtained from ideals in orders of such algebras, to the decision variant of LWE defined for nonassociative CDAs. We believe this variant has greater security and greater freedom with parameter choices than CLWE, and greater asymptotic efficiency of multiplication than module LWE. Our reduction requires new results in the ideal theory of such nonassociative algebras, which may be of independent interest. We then adapt an LPR-like PKE scheme to hold for nonassociative spaces, and discuss the efficiency and security of our construction, showing that it is immune to certain subfield attacks. Finally, we give example parameters to construct algebras for cryptographic use.
ePrint: https://eprint.iacr.org/2024/2058
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .