An Optimized Implementation of a Succinct Non-Interactive Zero-Knowledge Argument System

Abstract

In this thesis, we construct an implementation of succinct non-interactive zero knowledge argument system. A non-interactive zero knowledge argument system is a protocol for a party (usually known as Prover) to provide a proof of knowledge to the solution of a statement to other parties (usually known as Verifier). The argument system will be able to provide such proof without leaking any other information regarding the solution. The non-interactivity allows such argument system to be done without requiring interaction between the parties involved. The statement that is proven in this work is the circuit satisfiability problem. The circuit satisfiability problem is a problem of deciding whether there exists an input that can make the final output of a circuit to be true. The argument system is based on Lipmaa's work \cite{eprint2013:Lipmaa:NIZKSPECC} which uses span programs and linear error-correcting codes in its construction. We also try to give a very general explanation on zero knowledge argument system along the way in order to provide a simple concept to people encountering the notion for the first time. The argument system we attempt to construct is the non-adaptive version of the argument system. This version is useful for verifiable computation as pointed out by \cite{Pinnochio2013:Parno} apart from its zero knowledge behavior. We begin by giving an overview on non-interactive zero knowledge, followed by span programs. We then proceed to describe on how to represent the circuit satisfiability problem using the mentioned tool. We present our implementation afterwards, listing out the libraries and implementation details that matters. We conclude by providing a speed measurement and possible future improvements of this work.