Josh will discuss interim results of the DARPA Securing Information for Encrypted Verification and Evaluation (SIEVE) program. The SIEVE program seeks to advance the state of the art in ZK proofs to enable complex, defense-relevant applications. SIEVE will use ZK proofs to enable the verification of capabilities relevant to the US Department of Defense without revealing the sensitive details associated with those capabilities. SIEVE will aim to accomplish this goal by dramatically increasing the expressivity of problem statements for which ZK proofs can be constructed. SIEVE will also focus on increasing the efficiency of ZK proof technology to enable large, complex proof statements (e.g., billions of gates or more).

Authors: Collin Chin, Howard Wu, Raymond Chu, Alessandro Coglio, Eric McCarthy and Eric Smith

Decentralized ledgers that support rich applications suffer from three limitations. First, applications are provisioned tiny execution environments with limited running time, minimal stack size, and restrictive instruction sets. Second, applications must reveal their state transition, enabling miner front running attacks and consensus instability. Third, applications offer weak guarantees of correctness and safety. We design, implement, and evaluate LEO, a new programming language designed for formally verified, zero-knowledge applications. LEO provisions a powerful execution environment that is not restricted in running time, stack size, or instruction sets. Besides offering application privacy and mitigating miner-extractable value (MEV),LEO achieves two fundamental properties. First, applications are formally verified with respect to their high-level specification. Second, applications can be succinctly verified by anyone, regardless of the size of application. LEOis the first known programming language to introduce a testing framework, package registry, import resolver, remote compiler, and theorem prover for general-purpose, zero-knowledge applications.

Authors: Stephan Krenn and Michele Orrù

Over the last years, zero-knowledge proofs of knowledge based on Σ-protocols have found numerous applications. However, up to date there is still a lack of standardization of such protocols, potentially hindering even broader deployment, and increasing the risk of insecure implementations. This document proposes a standardization effort for non-interactive Σ-protocols in prime order groups, allowing for AND and OR composition, either in compact (challenge, response) or batchable form(commitment, response). The document provides the necessary formal background, specifies the protocols in full details, provides examples, suggests concrete instantiations (e.g., regarding the selection of elliptic curves or hash functions), and provides guidelines to ease the secure and compatible implementation of Σ-protocols.

Authors: Carla Ràfols and Arantxa Zapico

We introduce Verifiable Subspace Sampling Arguments, a new information theoretic interactive proof system in which the prover shows that a vector has been sampled in a subspace according to the verifier’s coins. We show that this primitive provides a unifying view that explains the technical core of most of the constructions of universal and updatable pairing-based zkSNARKs.

Authors: Chaya Ganesh, Anca Nituescu and Eduardo Soria-Vazquez

Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the choice of the prime field F_p is limited by the existence of groups of matching order for which secure bilinear maps exist. In this work we overcome such restrictions and enable verifying computations over rings. We construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough exceptional sets. Exceptional sets consist of elements such that their pairwise differences are invertible. Our contribution is threefold: We fist introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is overa ring. Second, inspired by the framework in Gennaro, Gentry, Parno and Raykova (EUROCRYPT2013), we design SNARKs over rings in a modular way. We generalize pre-existent assumptions employed in field-restricted SNARKs to encoding schemes over rings. As our encoding notion is generic in the choice of the ring, it amenable to different settings. Finally, we propose two applications for our SNARKs. In the first one, we instantiate our construction for the Galois RingGR(2^k,d), i.e. the degree-d Galois extension of Z_{2^k}. This allows us to naturally prove statements about circuits over e.g. Z_{2^64}, which closely matches real-life computer architectures such as standard CPUs. Our second application is verifiable computation over encrypted data, specifically for evaluations of Ring-LWE-based homomorphic encryption schemes.

The sum-check protocol is an essential tool for designing highly scalable succinct arguments, especially without a trusted setup. This talk will explain the protocol and its use in SNARK design, unifying a large number of succinct arguments along the way.

Distributed zero-knowledge (D-ZK) proofs give a means for proving statements on data held distributedly across multiple parties. Concretely, there are multiple verifiers who each hold pieces of the input x, and zero knowledge must additionally guarantee that subsets of verifiers do not learn about x beyond their original knowledge. In this talk, we will introduce the notion of D-ZK proofs, briefly survey known constructions, and present recent developments using information-theoretic D-ZK machinery to achieve low-overhead compilers for attaining general secure computation with security against malicious adversaries. Based on joint works with Dan Boneh, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai, and Ariel Nof.

This one-day social event is a satellite to the ZKProofs workshops and is the 3rd installment of the zkSessions online event series, hosted by Anna Rose from Zero Knowledge Podcast. If you are looking for talent and serious about hiring, then this should be a great opportunity to meet potential candidates and also to learn more from them about what they are looking for in an employer.

A zkSNARK is a cryptographic primitive that enables a prover to prove to a verifier the knowledge of a satisfying witness to an NP statement by producing a proof such that: (1) the proof reveals no information beyond what is implied by the validity of the NP statement; and (2) the size of the proof and the cost to verify it are both sub-linear (ideally, at most polylogarithmic) in the size of the statement. Given these properties, zkSNARKs are a core building block for various forms of delegation of computation to untrusted platforms. Two key problems in this research area are: (1) achieving excellent asymptotic and concrete efficiency for the prover, verifier, and proof sizes; and (2) avoiding a trusted setup. This talk will describe our recent progress in constructing high-speed zkSNARKs without trusted setup. A core building block in our construction is an highly-efficient information-theoretic proof system for R1CS that achieves a linear-time prover, and logarithmic proof sizes and verification times in the polynomial IOP proof model. We then describe how to compile such an information-theoretic proof system into a zkSNARK using polynomial commitments (with extensions to efficiently handle sparse multilinear polynomials). We will also touch upon a polynomial commitment scheme with a linear-time prover, which when used with the aforementioned linear-time polynomial IOP leads to a linear-time SNARK for R1CS.

In this talk, I will discuss a recent paradigm of using vector oblivious linear evaluation (VOLE) to construct efficient zero-knowledge protocols. The basic approach follows the commit-and-prove paradigm, using VOLE to obtain homomorphic commitments based on information-theoretic MACs. This allows supporting very large circuits with low computational resources, while having communication linear in the circuit size. I will then discuss some optimizations, including (1) an OR proof transformation for proving the disjunction of m statements with communication complexity proportional only to the longest statement, and (2) using the Fiat-Shamir transform to obtain non-interactive proofs to a designated verifier, with a constant memory overhead.

We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of n source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by 6 log n target group exponentiations. Proofs are of size 6 log n target group elements, computed using 6n pairings and 4n exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, O( √ d) prover complexity for degree d polynomials (not including the cost to evaluate the polynomial), and a CRS of size O( √ d). Concretely, this means that for d = 228, producing an evaluation proof in our protocol is 76× faster than doing so in the KZG [KZG10] commitment scheme, and the CRS in our protocol is 1, 000× smaller: 13MB vs 13GB for KZG. This gap only grows as the degree increases. Our polynomial commitment scheme is applicable to both univariate and bivariate polynomials. As a second application, we introduce an argument for aggregating n Groth16 zkSNARKs into an O(log n) sized proof. Our protocol is significantly more efficient than aggregating these SNARKs via recursive composition [BCGMMW20]: we can aggregate about 130,000 proofs in 25min, while in the same time recursive composition aggregates just 90 proofs. Finally, we show how to apply our aggregation protocol to construct a low-memory SNARK for machine computations.

In this talk we will describe recent advances on the concrete efficiency of MPC-in-the-Head based protocols. The ZK systems derived from this powerful framework share some interesting features such as transparency and public coin, so that they can be made non-interactive in the random oracle model using Fiat-Shamir. Furthermore, they do not require computational assumption and are plausibly post-quantum secure.

Authors: Markulf Kohlweiss, Mary Maller, Mikhail Volkhov and Janno Siim

Succinct non-interactive arguments of knowledge (SNARKs) have found wide-scale adoption in recent years. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). We propose a general security framework for non-interactive zero-knowledge (NIZK) arguments with a ceremony protocol. In particular, our framework generalizes the notion of updatable reference strings, proposed by Groth, Kohlweiss, Maller, Meiklejohn, and Miers[Crypto, 2018], to multiple independent update phases. Importantly, this allows us to also capture existing setup ceremonies as performed for Groth16 SNARKs.

Authors: Nikolaj Sidorenco, Sabine Oechsner and Bas Spitters

Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai etal.,STOC ’07) which use secure multiparty computation (MPC) protocols as basis. Efficient instances of this paradigm has emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al.,USENIX ’16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.

Individuals expose personally identifying information to access a website or qualify for a loan, undermining privacy and security. Firms share proprietary information in dealmaking negotiations; if the deal fails, the negotiating partner may use that information to compete. Regulators that comply with public transparency and oversight requirements can risk subjecting algorithmic governance tools to gaming that destroys their efficacy. Litigants might have to reveal trade secrets in court proceedings to prove a claim or defense. Such “verification dilemmas,” or costly choices between opportunities that require the verification of some fact, and risks of exposing sensitive information in order to perform verification, appear across the legal landscape. Yet, existing legal responses to them are imperfect. Legal responses often depend on ex post litigation that are prohibitively expensive for those most in need, or that fail to address abuses of information entirely. Zero-knowledge proofs (ZKPs)—a class of cryptographic protocols that allow one party to verify a fact or characteristic of secret information without revealing the actual secret—can help solve these verification dilemmas. ZKPs have recently demonstrated their mettle, for example, by providing the privacy backbone for the blockchain. Yet they have received scant notice in the legal literature. This Article fills that gap by providing the first deep dive into ZKPs’ broad relevance for law. It explains ZKPs’ conceptual power and technical operation to a legal audience. It then demonstrates how, and that, ZKPs can be applied as a governance tool to transform verification dilemmas in multiple legal contexts. Finally, the Article surfaces, and provides a framework to address, the policy issues implicated by the potential substitution of ZKP governance tools in place of existing law and practice.

Authors: Nicolas Gailly, Mary Maller and Anca Nitulescu

Groth16 arguments of knowledge have become a de-facto standard used in several blockchain projects due to the constant size of their proofs and their appealing verifier time. In this context, all nodes verify proofs posted on each block individually. Given an upper bound on the number of proofs allowed per blocks this solution doesn’t scale further. [BMM+19] presents a way to create an aggregate proof fromnGroth16 proofs with a O(log n) size and verifier time. However, the protocol requires a custom trusted setup, different than the Groth16 one. In this work, we modify the previous construction with a different commitment scheme that allows to aggregate existing Groth16 proofs by re-using existing powers of tau ceremonies transcript. Our protocol can aggregate1024 proofs in 2s and verifies them in 23ms, yielding an exponentially faster verification mechanism than batching.