Homomorphism learning problems and its applications to public-key cryptography

By: Christopher Leonardi, Security Researcher, ISARA Corporation, and Luis Ruiz-Lopez, Security Researcher, ISARA Corporation

Date: originally posted 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

Download the whitepaper in PDF format from IACR Cryptology ePrint Archive.

Review IACR Cryptology ePrint Archive page for this report.