By: Christopher Leonardi, Security Researcher, ISARA Corporation, and Luis Ruiz-Lopez, Security Researcher, ISARA Corporation
Thu May 23, 2019
CFAIL is a conference for papers that describe “instructive failures or not-yet-successes” in cryptography. This paper presents our partially successful attempt to generalize the Learning With Errors (LWE) problem to general groups in order to create lattice-like public-key encryption algorithms in other environments. In the pursuit of this goal, we define the Learning Homomorphisms with Noise (LHN) problem, describe a new public-key encryption scheme, and present sample instantiations of this protocol using polynomial rings and isogenies. However, we show that these instantiations, as well as any other instantiation based on commutative groups, cannot be used to obtain a quantum-safe encryption scheme. The problem of finding an efficiently computable quantum-safe instantiation of our generalized LWE problem is still open.
Category/Keywords: Learning With Errors, isogenies, non-commutative cryptography