- Vadim Lyubashevsky
- Ngoc Khanh Nguyen
- et al.
- 2022
- CRYPTO 2022
Zero-knowledge Proofs
Overview
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
Publications
- Vadim Lyubashevsky
- Ngoc Khanh Nguyen
- et al.
- 2020
- CCS 2020
- Rafaël Del Pino
- Vadim Lyubashevsky
- et al.
- 2018
- CCS 2018
- Jonathan Bootle
- Vadim Lyubashevsky
- et al.
- 2021
- ESORICS 2021
- Carsten Baum
- Jonathan Bootle
- et al.
- 2018
- Crypto 2018
- Jonathan Bootle
- Alessandro Chiesa
- et al.
- 2022
- Eurocrypt 2022
- Jonathan Bootle
- Alessandro Chiesa
- et al.
- 2021
- CRYPTO 2021
- Jonathan Bootle
- Vadim Lyubashevsky
- et al.
- 2020
- CRYPTO 2020