Hardness of learning problems over Burnside groups of exponent 3

In this work, we investigate the hardness of learning Burnside homomorphisms with noise (\(B_{n} \hbox {-}\mathsf {LHN}\)), a computational problem introduced in the recent work of Baumslag et al. This is a generalization of the learning with errors problem, instantiated with a particular family of non-abelian groups, known as free Burnside groups of exponent 3. In our main result, we demonstrate a random self-reducibility property for \(B_{n} \hbox {-}\mathsf {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.