Homomorphism learning problems and its applications to public-key cryptography : public key cryptography

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.

Continue Reading

While the ideal of public key cryptography is to have a “set and forget” group of algorithms that will guarantee security forever, increasingly we are realizing this ideal is not viable. There is not one cryptographic algorithm with a fixed set of parameters that will last indefinitely. As computers become more powerful and new attacks are found on existing protocols, it is important to update our cryptography. This can involve increasing parameters on widely used algorithms. There have also been times when it involved switching to new cryptographic schemes entirely. With the onset of large-scale quantum computing, we are currently at the start of the second major migration of public key cryptography, part of the constantly evolving progression of cryptography.

Continue Reading