Lattice-based Cryptography

Lattice-based cryptography is an approach for constructing security primitives. It is based on problems from an area of mathematics called “geometry of numbers.”

Suppose that one is given a square, full-rank matrix A and a value b = Ax mod p, where x is a vector with 0/1 coefficients and p is a small (e.g. 13-bit) prime. One is then tasked with finding x. This problem has a unique solution x, which is actually quite easy to find by using Gaussian elimination.

On the other hand, if one is given a slightly “noisy” version of Ax, that is Ax+e mod p, where e is some random vector with 0/1 coefficients, then for matrices of large-enough dimension (say, around 512), this problem becomes surprisingly difficult.

This type of problem is related to both the subset sum and the learning parity with noise problems that have been widely studied since the 1980s and have not succumbed to any algorithmic attacks, either classical or quantum.

Lattice-Based Zero-Knowledge Proof Systems and Privacy

Zero-knowledge proofs are the core building block for most of privacy-centered cryptography. There is currently a large performance gap between non-quantum-safe zero-knowledge proof systems and quantum-safe hash-based ones. One promising avenue for shrinking this gap is via the introduction of computational hardness assumptions such as lattice assumptions. In the area of basic signature schemes, lattice-based signatures are now significantly more efficient than hash-based signatures, both in terms of bandwidth requirements and computational performance. Therefore, it is likely that the same can eventually also be achieved for more advanced algorithms such as zero-knowledge proof systems used in privacy-based protocols and even for proving general circuits.

Our group is at the forefront of research in this area and we have achieved a steady stream of progress in terms of proof size over the last years. The proof systems we have developed can be used in the construction of privacy-preserving cryptography and lead to very practical schemes that are the best quantum-safe alternatives known to date.

Projects

FELICITY: Foundations of Efficient Lattice Cryptography (2016 – 2021)

European Research Council (ERC)

Public key cryptography is the backbone of internet security, but most of the current mathematical assumptions on which it relies can be broken by quantum computers. Lattice cryptography is considered the most promising candidate to become the basis of tomorrow’s cryptography. The FELICITY project is pushing the boundaries of what can be efficiently built based on the difficulty of lattice problems.

Principal investigator: Vadim Lyubashevsky