Non-Interactive Zero-Knowledge and Applications to Cryptocurrencies

Specialeforsvar ved Borg Jacob Albers

Titel: Non-Interactive Zero-Knowledge and Applications to Cryptocurrencies 

Abstract: In recent years, the cryptographic primitive of non-interactive zero-knowledge (NIZK) proof systems has received a great deal of research attention. This development was spurred on by the emergence and rapid growth of cryptocurrencies where non-interactive zero-knowledge proofs hold the promise of mitigating privacy and scalability concerns. Numerous NIZK constructions for \textbf{NP} are known. The first such proposals arise from \linebreak communication-efficient interactive protocols which use probabilistically checkable proofs. Interaction is removed using the Fiat-Shamir heuristic, resulting in a non-interactive protocol in the random oracle model. While asymptotically efficient, these schemes unfortunately introduce significant overhead that renders them totally impractical. A more recent proposal from 2013 constructs a NIZK in the common reference string model which achieves small proof sizes of less than 300 bytes, which are \textit{independent} of the size of the computation. Accordingly, the verifier is both concretely and asymptotically very efficient. The cryptographic building blocks are linear probabilistically checkable proofs and homomorphic encryption schemes that support addition but no other homomorphisms. The drawbacks of this NIZK are an expensive trusted setup (linear in the size of the computation) and the reliance on the non-standard knowledge-of-exponent assumption. Notwithstanding, the small proofs and quick verifier have made this NIZK an appealing candidate for cryptocurrency appli-cations. Most notably, the NIZK forms the cornerstone of the privacy protocol Zerocash, which has been deployed on a large scale in cryptocurrencies such as Zcash. In 2018, Ben-Sasson et al.\ constructed a NIZK in the random oracle model based on interactive oracle proofs, a generalization of probabilistically checkable proofs. While still somewhat impractical, the resulting construction is asymptotically optimal, i.e.\ it achieves quasilinear prover runtime, and polylogarithmic verifier runtime and proof sizes. In this thesis, we strive to provide a conceptual consolidation of the spread-out body of knowledge surrounding efficient NIZKs. We place particular focus on the lines of academic works resulting in the NIZK construc-tions mentioned above. Finally, we survey the universe of other stste-of-the-art NIZK proposals, which rest on different cryptographic foundations and achieve varied proof sizes, prover runtimes, and verification times.

Vejleder: Florian Speelman
Censor:   Ignacio Cascudo, Aalborg Universitet