LWE from non-commutative group rings
LWE from non-commutative group rings
复制标题
DOI：
10.1007/s10623-021-00973-6
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Qi Cheng;Jun Zhang;Jincheng Zhuang
中科院分区：
文献类型：
--
作者：
Qi Cheng;Jun Zhang;Jincheng Zhuang
带错误学习（LWE）问题（及其变体包括环LWE和模LWE）的安全性基于硬理想格问题，已被证明是密码学中具有多种应用的有前途的原语。为了扩大构造LWE的来源，本文研究群环上的LWE问题。我们可以把分圆整数上的Ring-LWE看作是基础群是循环的特殊情况，而我们的建议利用了非交换群。特别是，我们展示了如何从二面角群环建立公钥加密方案，同时保持环LWE的效率。通过将群环理想格的SIVP问题转化为判定群环LWE问题，证明了PKC系统是语义安全的。事实证明，群的不可约表示在这里起着重要的作用。我们相信，引入代表性的观点，丰富了研究环LWE问题的工具集。
The Learning-With-Errors (LWE) problem (and its variants including Ring-LWE and Module-LWE), whose security are based on hard ideal lattice problems, has proven to be a promising primitive with diverse applications in cryptography. For the sake of expanding sources for constructing LWE, we study the LWE problem on group rings in this work. One can regard the Ring-LWE on cyclotomic integers as a special case when the underlying group is cyclic, while our proposal utilizes non-commutative groups. In particular, we show how to build public key encryption schemes from dihedral group rings, while maintaining the efficiency of the Ring-LWE. We prove that the PKC system is semantically secure, by providing a reduction from the SIVP problem of group ring ideal lattice to the decisional group ring LWE problem. It turns out that irreducible representations of groups play important roles here. We believe that the introduction of the representation view point enriches the tool set for studying the Ring-LWE problem.