Cryptology ePrint Archive: Report 2016/1169

LWE from Non-commutative Group Rings

Qi Cheng and Jincheng Zhuang

Abstract: The Ring Learning-With-Errors (LWE) problem, whose security is based on hard ideal lattice problems, has proven to be a promising primitive with diverse applications in cryptography. There are however recent discoveries of faster algorithms for the principal ideal SVP problem, and attempts to generalize the attack to non-principal ideals. In this work, we study the LWE problem on group rings, and build cryptographic schemes based on this new primitive. One can regard the LWE on cyclotomic integers as a special case when the underlying group is cyclic, while our proposal utilizes non-commutative groups, which eliminates the weakness associated with the principal ideal lattices. In particular, we show how to build public key encryption schemes from dihedral group rings, which maintains the efficiency of the ring-LWE and improves its security. We also propose a simple modification of the Peikert-Vaikuntanathan-Waters cryptosystem, which is an amortized version of Regev's original proposal based on LWE. Our modification improves the encryption and decryption complexity per bit to sublinear in the security level, without affecting the security.

Category / Keywords: Matrix-LWE, Non-commutative group ring, Dihedral group ring

Date: received 20 Dec 2016, last revised 14 Feb 2017

Contact author: zhuangjincheng at iie ac cn

Available format(s): PDF | BibTeX Citation

Note: 17 pages; writing revised; a math error fixed

Version: 20170215:060712 (All versions of this report)

Short URL: ia.cr/2016/1169

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]