Abstract:
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]