General Lattice-Based Zero-Knowledge

Zero-knowledge proof systems are an extremely versatile tool for the construction of advanced cryptographic protocols and especially privacy-preserving protocols. Their importance will increase in the expected post-quantum world where quantum computers break classical cryptography. Unfortunately, for many applications and despite enormous research efforts, state-of-the-art quantum-safe proof systems of PCP type do not yet offer the necessary performance required in practice. The time needed to compute a proof is often too long and the proof size too big. An important such application that shall serve as a guiding principle in this project are privacy-preserving protocols constructed on top of standard (random-oracle) schemes. In recent research a promising new family of proof systems has emerged that is based on lattice cryptography. Especially their computational performance and proof sizes warrant more research into them. But lattice-based proof systems do not currently match the functionality of the PCP-type ones and can not be used for proving general computation. The central objective of GLAZE is to research ways to bring the functionality of lattice-based proof systems to the state of PCP-type ones, and then work on improving their performance and proof sizes to levels that are orders of magnitude better than the state of the art, enabling applications that are completely beyond the reach of practicality at the moment. Concretely, this project would ideally result in lattice-based proof systems able to prove a standard post-quantum signature such as Falcon with its long unstructured full-domain hash in under 100 milliseconds prover time and 10 Kilobytes proof size on a mobile processor.