Hardness of Learning Problems over Burnside Groups of Exponent 3

Nelly Fazio; Kevin Iga; Antonio Nicolosi; Ludovic Perret; William E.  Skeith III

Paper 2011/398

Hardness of Learning Problems over Burnside Groups of Exponent 3

Nelly Fazio, Kevin Iga, Antonio Nicolosi, Ludovic Perret, and William E. Skeith III

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: Published elsewhere. Unknown where it was published
Keywords: Random self-reducibility Learning with errors Post-quantum cryptography Non-commutative cryptography Burnside groups.
Contact author(s): wes @ cs ccny cuny edu
History: 2012-05-19: last of 3 revisions; 2011-07-28: received; See all versions
Short URL: https://ia.cr/2011/398
License: CC BY

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}
}