A1 Journal article (refereed)
Non-commutative Ring Learning with Errors from Cyclic Algebras (2022)


Grover, C., Mendelsohn, A., Ling, C., & Vehkalahti, R. (2022). Non-commutative Ring Learning with Errors from Cyclic Algebras. Journal of Cryptology, 35(3), Article 22. https://doi.org/10.1007/s00145-022-09430-6


JYU authors or editors


Publication details

All authors or editorsGrover, Charles; Mendelsohn, Andrew; Ling, Cong; Vehkalahti, Roope

Journal or seriesJournal of Cryptology

ISSN0933-2790

eISSN1432-1378

Publication year2022

Volume35

Issue number3

Article number22

PublisherSpringer Science and Business Media LLC

Publication countryUnited States

Publication languageEnglish

DOIhttps://doi.org/10.1007/s00145-022-09430-6

Publication open accessOpenly available

Publication channel open accessPartially open access channel

Publication is parallel published (JYX)https://jyx.jyu.fi/handle/123456789/82493

Web address of parallel published publication (pre-print)https://eprint.iacr.org/2019/680.pdf


Abstract

The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice-based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of ‘structured’ LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well-chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a ring. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. We show that the security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem (under the condition of constant rank d). As a contribution of theoretic interest, we view CLWE as the first variant of Ring LWE which supports non-commutative multiplication operations. This ring structure compares favorably with Module LWE, and naturally allows a larger message space for error correction coding.


Keywordscryptographyencryptiondata systemsimprovingerrorserror analysisalgebranumber theory

Free keywordsalgebraic number theory; lattices; learning with errors; non-commutative algebra; post-quantum cryptography


Contributing organizations


Ministry reportingYes

Reporting Year2022

JUFO rating3


Last updated on 2024-15-06 at 00:26