What are the benefits of lattice based cryptography?

Question

Previously we visited the benefits of elliptic curves for cryptography. Lattice based cryptography is starting to become quite popular in academia. The primary benefit of lattice based crypto is the resistance to quantum algorithms. Are there other benefits to lattice based crypto? For example, speed, ciphertext/key sizes, etc?

Answer 1

• Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer.

• Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem is hard on average or more precisely hard to solve for random instances drawn from some particular distribution. For example, we may assume that factoring a product of two random primes cannot be done by a poly-time algorithm. While this is usually safe, it is in principle possible that someone will find an efficient factoring algorithm that works often on random instances but not on all instances. Lattice-based cryptography does not suffer from this drawback: Those schemes are proven secure assuming that lattice problems are hard in the worst case, meaning they are secure as long as no one can find, say, a poly-time algorithm for approximating shortest vectors in every lattice, not just random ones. This is a huge theoretical advance, but determining exactly what it will mean in practice is difficult for me to say.

• Efficiency improvements: I'll be a little sheepish on this point, but it's often noted that lattice-based schemes have a parallelizable structure that may make them faster in certain contexts. This is because the algorithms involved are usually simple matrix multiplication with relatively small modular arithmetic (i.e., not cryptographic-sized numbers). However, my understanding is that implementations of lattice-based schemes would have larger keys, and I'm also not aware of any studies that definitively compare lattice based schemes to traditional schemes.

• New primitives: We only know how to build fully homomorphic encryption from lattices or from very similar techniques. There is a ton of potential here, and we have no idea how to build such things from factoring or other traditional assumptions.