TY - JOUR
T1 - Hardness of learning problems over Burnside groups of exponent 3
AU - Fazio, Nelly
AU - Iga, Kevin
AU - Nicolosi, Antonio R.
AU - Perret, Ludovic
AU - Skeith, William E.
N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.
PY - 2015/4
Y1 - 2015/4
N2 - In this work, we investigate the hardness of learning Burnside homomorphisms with noise ((Formula presented.)LHN(Formula presented.)), 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 (Formula presented.)LHN(Formula presented.). 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.
AB - In this work, we investigate the hardness of learning Burnside homomorphisms with noise ((Formula presented.)LHN(Formula presented.)), 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 (Formula presented.)LHN(Formula presented.). 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.
KW - Burnside groups
KW - Learning with errors
KW - Non-commutative cryptography
KW - Post-quantum cryptography
KW - Random self-reducibility
UR - http://www.scopus.com/inward/record.url?scp=84925292256&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84925292256&partnerID=8YFLogxK
U2 - 10.1007/s10623-013-9892-6
DO - 10.1007/s10623-013-9892-6
M3 - Article
AN - SCOPUS:84925292256
SN - 0925-1022
VL - 75
SP - 59
EP - 70
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 1
ER -