Paper 2026/1233
Implementation of Learning with Errors in Non-Commuting Multiplicative Groups
, Kaunas University of Technology, Kaunas University of Technology, Kaunas University of TechnologyAbstract
In this paper, we demonstrate a way to generalize learning with errors (LWE) to the family of so-called modular-maximal cyclic groups which are non-commuting. Since the group $\mathbb{M}_{2^t}$ has two cycles of maximal multiplicative order, we use this fact to construct an accurate criterion for restoring the message bit with overwhelming probability. Furthermore, we implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of $\mathbb{M}_{2^t}$. Also we prove that using this approach we can achieve a level of security comparable to the original idea.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. https://arxiv.org/pdf/2509.11237
- Keywords
- Learning with errorsMatrix power functionPublic key encryptionPost-quantum cryptography.
- Contact author(s)
-
aleksejus michalkovic @ ktu lt
lina dindiene @ ktu lt
eligijus sakalauskas @ ktu lt - History
- 2026-06-11: approved
- 2026-06-10: received
- See all versions
- Short URL
- https://ia.cr/2026/1233
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1233,
author = {Aleksejus Mihalkovich and Lina Dindiene and Eligijus Sakalauskas},
title = {Implementation of Learning with Errors in Non-Commuting Multiplicative Groups},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1233},
year = {2026},
url = {https://eprint.iacr.org/2026/1233}
}
