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.
In Designs, Codes and Cryptography. Springer 2013.
Download: [pdf] [bibtex entry]