### LWE from Non-commutative Group Rings

Qi Cheng, Jun Zhang, 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.

Note: A refined security analysis is provided.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
ring-LWENon-commutative group ringDihedral group ring
Contact author(s)
zhuangjincheng @ iie ac cn
History
2017-06-21: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/1169

CC BY

BibTeX

@misc{cryptoeprint:2016/1169,
author = {Qi Cheng and Jun Zhang and Jincheng Zhuang},
title = {LWE from Non-commutative Group Rings},
howpublished = {Cryptology ePrint Archive, Paper 2016/1169},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/1169}},
url = {https://eprint.iacr.org/2016/1169}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.