Aarhus University Seal / Aarhus Universitets segl

Zero-Knowledge

Zero-Knowledge

  • A powerful tool to balance trust and privacy 

Zero-knowledge proofs are cryptographic primitives that allow a party, a prover, to convince a verifier that a given statement is true, without revealing anything beyond the validity of the statement. Zero-knowledge thus provides a powerful tool to balance trust and privacy. 

In addition to being studied as a fundamental primitive with rich connections to theory of computation, zero-knowledge proofs have found numerous applications as building blocks in cryptographic protocols. These applications range from signature schemes, secure multi-party computation, signature and identification schemes to name a few. Unsurprisingly, zero-knowledge proofs have tremendous potential in achieving privacy and anonymity in transactions on the blockchain. For example, one can prove to the nodes of the peer-to-peer system that one is a legal user of the system, without leaking any information about one's identity. This will allow users of the system to remain anonymous, yet ensure that only legal users can use the system.

 

Seminal results from the past decades prove that every language in NP has a zero-knowledge proof, and since then, there has been progress in constructing proofs that are efficient enough to be implemented in practice. For applications on the blockchain, we need zero-knowledge proofs that do not require any interaction, have small proof size, and are computationally efficient for the prover and the verifier. Proofs that do not add too much overhead to the underlying computation (without zero-knowledge), will make them truly deployable on the blockchain.

 

One of the research topics we will consider is how to construct new zero-knowledge proofs that are efficient in all relevant complexity parameters. Zero-knowledge proofs that are based on zk-SNARKs(Zero-knowledge Succinct Non-interactive ARgument of Knowledge), allow for small proofs and efficient verification, making them particularly suitable for blockchain. Another approach resulting in practical proofs for certain languages, is Sigma protocols. A challenging research topic is designing zero-knowledge proofs for compositestatements that frequently arise in blockchain-related applications. Composite statements are statements 

that have components represented in different ways: Boolean circuit, arithmetic circuit, algebraic representation. All known techniques are tailor-made for certain representations and forego efficiency when used on composite statements. An interesting research topic that we will consider, is to explore “best of all worlds”. Here, we would like to make the different approaches for zero-knowledge proofs like zk-SNARKs, Sigma protocols and other approaches based on MPC, work well together, so we can get the efficiency advantage of each.

 

Another pertinent research topic is to design zk-SNARKs that are post-quantum secure, that is zero-knowledge proofs such that the security guarantees hold even against a quantum computer.