Abstract:
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 spe- cial cases, but is much more general. It allows,
for example, instantiations based on non-abelian groups, resulting in
a new avenue for the applica- tion 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.
Publication Info:
In the 5th International Conference on Provable (ProvSec '11). Xi'an,
China, October 16-18, 2011. Springer LNCS 6980, pages 324-339
Download: [pdf] [bibtex entry]