Post-Quantum Lattice-Based Zero-Knowledge

The world is on a seemingly irreversible path towards a more privacy-oriented and decentralized mode ofstoring and operating on data.

A lot of this transformation is being enabled by advanced cryptography that’sdesigned to cut out the need for trusted third parties that we rely on today.

The effect of this transformationis a more secure and, at the same time, a more efficient way of interaction in which the manual checks andaudits are instead embedded into the cryptographic protocols themselves.

Another technological developmentthat’s on the horizon is a general-purpose quantum computer, whose utility comes from the fact that it willbe able to solve some problems considerably faster than a classical computer.

Because of the multitude ofits positive scientific applications, building such a computer is being vigorously pursued by governments andprivate companies.

The main negative consequence of quantum computing is that it breaks most of thecryptography that’s crucial to the privacy transformation.The main ingredient of privacy-centric cryptography is a zero-knowledge proof for showing knowledgeof an x satisfying f(x) = y without revealing anything else about x.

The most compact zero-knowledgeproofs currently rely on the hardness of various mathematical assumptions which are no longer difficult inthe presence of quantum computers.

The central objective of the PLAZA project will be to create practicalzero-knowledge proofs that can withstand quantum attacks by basing them on the hardness of lattice problems.Lattice problems are a very promising set of assumptions upon which to base cryptography and theyare currently being used to create the most efficient quantum-resistant encryption and signature schemes.Creating more complex, but still practical, lattice-based schemes has so far proved to be a major challengemostly due to the difficulty of constructing efficient zero-knowledge proofs – and this is the problem that theproject proposes to solve.