- 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