A Comprehensive study of arithmetic circuits and elliptic curves for efficient and scalable zero-knowledge proof systems

Abstract

In recent years, zero-knowledge proofs have come to play a crucial role in distributed systems where there is no trust between the parties involved. Most popular proof systems are for the NP-complete language of arithmetic circuit satisfiability. Although there have been tremendous efforts in understanding, developing, and improving zero-knowledge proof systems, not much work has been done towards the study of arithmetic circuits. In this thesis, we contribute to this matter in three different aspects. First, we present circom, a programming language for writing arithmetic circuits that abstracts the complexity of the proof system. Second, we provide a deterministic algorithm for generating twisted Edwards elliptic curves that can be used to prove elliptic-curve cryptography statements in zero knowledge efficiently. Finally, we explore recursive composition of pairing-based proof systems with native circuit arithmetic, delving into the study of cycles of pairing-friendly elliptic curves of prime order.

En els últims anys, les proves de coneixement zero han passat a tenir un paper crucial en el sistemes distribuïts on no hi ha confiança entre els participants. Els sistemes de prova més populars són pel llenguatge NP complet de satisfacibilitat de circuits aritmètics. Tot i que hi ha hagut molts esforços per entendre i millorar les proves de coneixement zero, no s’ha avançat tant en l’estudi dels circuits aritmètics. En aquesta tesi, contribuïm a aquest tema en tres aspectes. Primerament, presentem circom, un llenguatge de programació per escriure circuits aritmètics que abstreu la complexitat del sistema de prova. Segonament, proporcionem un algorisme determinista per a generar corbes el·líptiques que permeten demostrar eficientment declaracions de criptografia de corba el·líptica. Finalment, explorem la composició recursiva de sistemes de prova basats en aparellaments utilitzant l’aritmètica nativa dels circuits, aprofundint en l’estudi de cicles de corbes el·líptiques d’ordre primer amb aparellaments adients.