Zero-knowledge Proofs

Time and Space Efficient Proof Systems

Imagine that a client with few resources wants to outsource an expensive computer simulation to a powerful, but untrusted cloud server. The client cannot run the simulation for themselves, so how can they check whether the results are correct? Zero-knowledge proof (ZKP) systems solve this problem. Using a ZKP, the server can provide a proof that they ran the simulation correctly without a need to provide additional information.

Years of dedicated research on ZKPs mean that clients can check proofs at a tiny fraction of the cost of the simulation. However, the cost of producing proofs remains high, leading to a large gap between what can be outsourced, and what can be verifiably outsourced.

ZKPs based on hash-functions offer the best solution to this problem. They are transparent, quantum-safe, and have the lowest computational overhead of all known ZKPs. By improving hash-based ZKPs, we will eliminate the verification gap and enable truly large-scale outsourced computing applications.

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 (pairing-based) 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

PLAZA: Post-Quantum Lattice-Based Zero-Knowledge (2021 – 2026)

European Research Council (ERC) Consolidator Grant

The digital world is experiencing a major shift in the direction of more privacy and decentralization. The currently most efficient privacy-granting cryptographic schemes, however, are not quantum-safe. The goal of the PLAZA project is to extend the efficient lattice-based techniques that were used to create the new quantum-safe NIST standards to create practical zero-knowledge proofs and privacy-based protocols. It is our hope to have all the necessary pieces in place before the decentralized, privacy-based ecosystem receives widespread adoption.

Principal investigator: Vadim Lyubashevsky