TY - GEN
T1 - Generalized learning problems and applications to non-commutative cryptography (Extended abstract)
AU - Baumslag, Gilbert
AU - Fazio, Nelly
AU - Nicolosi, Antonio R.
AU - Shpilrain, Vladimir
AU - Skeith, William E.
PY - 2011
Y1 - 2011
N2 - We propose a generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of group-theoretic learning problems that we term learning homomorphisms with noise (LHN). This class of problems contains LPN and LWE as special cases, but is much more general. It allows, for example, instantiations based on non-abelian groups, resulting in a new avenue for the application of combinatorial group theory to the development of cryptographic primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it.
AB - We propose a generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of group-theoretic learning problems that we term learning homomorphisms with noise (LHN). This class of problems contains LPN and LWE as special cases, but is much more general. It allows, for example, instantiations based on non-abelian groups, resulting in a new avenue for the application of combinatorial group theory to the development of cryptographic primitives. We then study a particular instantiation using relatively free groups and construct a symmetric cryptosystem based upon it.
KW - Burnside groups
KW - Learning with errors
KW - Non-commutative cryptography
KW - Post-quantum cryptography
UR - http://www.scopus.com/inward/record.url?scp=80053134381&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80053134381&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-24316-5_23
DO - 10.1007/978-3-642-24316-5_23
M3 - Conference contribution
AN - SCOPUS:80053134381
SN - 9783642243158
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 324
EP - 339
BT - Provable Security - 5th International Conference, ProvSec 2011, Proceedings
T2 - 5th International Conference on Provable Security, ProvSec 2011
Y2 - 16 October 2011 through 18 October 2011
ER -