论文标题
与循环代数错误的非交换环学习
Non-Commutative Ring Learning With Errors From Cyclic Algebras
论文作者
论文摘要
错误的学习（LWE）问题是基于现代晶格的密码学的基本骨干，使人们能够建立有关研究精通计算问题的硬度的密码学。但是，基于LWE的方案通常是不切实际的，因此将RING LWE作为“结构性” LWE的一种形式引入，通过在选择精良的环上工作来量化难以量化的安全性损失，以提高效率。另一个流行的变体LWE通过在环上实现模块结构来概括此交换。在这项工作中，我们在周期性代数（CLWE）上引入了一种新型LWE的新型变体，以通过将LWE添加到模块LWE中，以将LWE添加到环LWE中复制环结构。所提出的构造既比模块LWE更有效，而且比两全其美的Ring LWE更安全。我们表明，LWE问题的预期安全性降低，即从某些结构化晶格问题减少到Clwe问题的决策变体的硬度。作为理论利益的贡献，我们将Clwe视为支持非交通乘法操作的环LWE的第一个变体。该环结构与模块LWE进行比较，并且自然允许更大的消息空间进行错误校正编码。
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. The proposed construction is both more efficient than Module LWE and conjecturally more secure than Ring LWE, the best of both worlds. 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. 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.
