Paper 2011/398 Original: eprint.iacr.org/2011/398 ↗
Hardness of Learning Problems over Burnside Groups of Exponent 3
Abstract
In this work we investigate the hardness of a computational problem introduced in the recent work of Baumslag et al. In particular, we study the $B_n$-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 $B_n$-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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2012-05-19: last updated
- 2011-07-28: published
- Short URL
- https://ia.cr/2011/398
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2011/398,
author = {Nelly Fazio and Kevin Iga and Antonio Nicolosi and Ludovic Perret and William E. Skeith III},
title = {Hardness of Learning Problems over Burnside Groups of Exponent 3},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/398},
year = {2011},
url = {https://eprint.iacr.org/2011/398}
}