Hardness of Learning Problems over Burnside Groups of Exponent 3

Authors: N. Fazio, K. Iga, A. Nicolosi, L. Perret, and W.E. Skeith.

In this work we investigate the hardness of a computational problem introduced in the recent work of Baumslag etal. in [BFNSS11,BFNSS11-full]. In particular, we study the Bn-LHN problem, which is a generalized version of the learning with errors (LWE) problem, instantiated with a particular family of non-abelian groups (free Burnside groups of exponent 3). In our main result, we demonstrate a random self-reducibility property for Bn-LHN. Along the way, we also prove a sequence of lemmas regarding homomorphisms of free Burnside groups of exponent 3 that may be of independent interest.

Publication Info:
In Designs, Codes and Cryptography. Springer 2013.

Download: [pdf] [bibtex entry]

Copyright © Nelly Fazio