Non-commutative Ring Learning with Errors from Cyclic Algebras
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
Published in
Journal of CryptologyDate
2022Copyright
© The Author(s) 2022
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.
...
Publisher
Springer Science and Business Media LLCISSN Search the Publication Forum
0933-2790Keywords
Publication in research information system
https://converis.jyu.fi/converis/portal/detail/Publication/148956560
Metadata
Show full item recordCollections
License
Related items
Showing items with similar title or keywords.
-
The minimal number of generators for ideals in commutative rings
Pirnes, Erika (2018)Olkoon R kommutatiivinen rengas. Tämän tutkielman tarkoituksena on etsiä ylä- ja alarajat äärellisviritteisen ideaalin I = (a1, . . . , an) ⊂ R minimaaliselle virittäjämäärälle. Tärkeänä työkaluna toimii moduliteoria; ... -
Sectorial Mertens and Mirsky formulae for imaginary quadratic number fields
Parkkonen, Jouni; Paulin, Frédéric (Birkhäuser, 2024)We extend formulae of Mertens and Mirsky on the asymptotic behaviour of the usual Euler function to the Euler functions of principal rings of integers of imaginary quadratic number fields, giving versions in angular sectors ... -
Spectral function for overoccupied gluodynamics from real-time lattice simulations
Boguslavski, Kirill; Kurkela, A.; Lappi, Tuomas; Peuron, Jarkko (American Physical Society, 2018)We study the spectral properties of a highly occupied non-Abelian nonequilibrium plasma appearing ubiquitously in weak coupling descriptions of QCD matter. The spectral function of this far-fromequilibrium plasma is ... -
Kvanttilaskenta ja salausmenetelmät
Vanas, Linus (2019)Kvanttilaskenta ja Shorin algoritmi rikkovat useita nykyisin yleisessä käytössä olevia julkisen avaimen salausmenetelmiä, kuten RSA-menetelmän. Tässä tutkielmassa tarkastellaan kvanttilaskennan vaikutusta salausmenetelmiin ... -
Digital signing process automation and optimization
Hytönen, Heikki (2020)Ohjelmiston digitaalinen allekirjoitus on välttämätön osa luotettujen ohjelmistojen julkaisuprosessia. Digitaalinen allekirjoitus nojautuu julkisen avaimen infrastruktuuriin ja sen tehtävänä on varmistaa, että julkaistu ...