Titles and Abstracts
ZKP for audits of Unsolicited Consumer Communication
Hitarshi Buch and Harihara Natarajan, Wipro
The menace of Unsolicited Commercial Communication (text messages / voice calls ) is growing day by day as phone subscribers keep receiving unwanted messages and calls. Telecom regulatory bodies have now mandated that this kind of communication should be filtered based on subscriber’s preferences & consent. These preferences are managed by the respective telecom service providers (TSP) like Vodafone, AT&T etc. Exposing this data would result in the subscriber being subjected to more spam and also targeted advertising etc. Therefore the TSP needs to provide evidence that messages are segregated based on subscriber’s preferences so that a level playing field is maintained, without compromising the user preference data. Our solution leverages a combination of ZKP and blockchain to enable the prover (TSP) to construct a proof which can be used by the verifier (Auditor) to validate the proof of delivery / exclusion . We will demonstrate a prototype using zk-SNARKs for on-demand proof generation and describe a technique leveraging Merkle trees for pre-computed proofs that can be applied to this real-life use case. We will also discuss the merits & demerits of each approach and the practical limitations.
Applications of Zero Knowledge Proofs in the Banking Industry
Eduardo Moraes, ING
In this talk we will present the implementation of ZKPs at ING. We will show interesting use cases in the banking industry, describing findings and challenges that we faced during this effort.
Bringing ZKP to Traditional Industries, Physical World Use-cases
Shiri Lemel, QEDIT
Taking Zero Knowledge into traditional industries requires an end-to-end overview of the use-case and deep understanding of processes and flows. In this talk we will review use-cases in supply chain management and user consent systems to understand the role of ZKP in enabling digitalisation, and how QEDIT is addressing the needs of these industries in our Asset Transfer solution.
Privacy Pass: a Lightweight Zero Knowledge Protocol Designed for the Web
Nick Sullivan, Cloudflare
Privacy Pass is a project launched in 2017 to help make solving CAPTCHAs online less painful using zero-knowledge cryptography. The core of Privacy Pass is a 1-RTT cryptographic protocol (based on an implementation of an oblivious pseudorandom function) that allows users to receive a significant amount of anonymous tokens in exchange for solving a challenge. These tokens can be exchanged in the future for access to services without having to interact with a challenge and without the service knowing which specific challenge was originally solved. Privacy Pass is now in use by over a hundred thousand monthly active users in the form of the Privacy Pass browser extension for Chrome and Firefox. In this talk I'll explore both the mathematical underpinnings of this project and its future directions.
Tooling Infrastructure for Zero-Knowledge Proofs
Henry de Valence, Zcash Foundation
Developing and deploying zero-knowledge proofs into production systems without catastrophic failures along the way is a significant challenge. This talk will discuss tooling for zero-knowledge proofs, aiming at reducing the time and effort to produce high-quality implementations, as well as some challenges for standardization.
An R1CS based Implementation of Bulletproofs
Cathie Yun, Interstellar
I will discuss our Bulletproofs constraint system implementation, explaining the R1CS API and an extension to Bulletproofs which takes advantage of the lack of setup to select a circuit from a family parameterized by Fiat-Shamir challenges. I will illustrate these concepts by walking through the construction of a shuffle gadget, which proves that one list of Pedersen commitments is a permutation of another. I'll also talk about the multiparty computation protocol for interactive aggregation, and how we encode the protocol states into the Rust type system, ensuring that any compilable instantiation of the protocol executes in the correct order, with no possibility of replay attacks. Lastly, I'll discuss the applications we are building using Bulletproofs R1CS proofs - a confidential assets protocol (Cloak), and a confidential smart contract language (ZkVM).
Fragile Nonce Selection and ZKPs as a Solution
Andrew Poelstra, Blockstream
Elliptic-curve-based signature schemes such as Schnorr and ECDSA require fresh uniform randomness for every signature. Deviations from uniform, even by fractions of a bit, can be exploited by lattice-based attacks to extract secret key material. On the other hand, uniform randomness is difficult to reliably obtain in many constrained environments, such as virtual machines or cheap hardware devices. The traditional solution to this, for signatures, is to derive randomness deterministically by hashing a secret key and message to be signed (i.e. using RFC6979). The message and nonce determine the Fiat-Shamir challenge, ensuring that distinct signatures will always have independently uniform randomness. However, in the multiparty setting, the Fiat-Shamir challenge is now determined by input from all participants. This means that individual participants can no longer ensure unique randomness by hashing data known at nonce-generation time. Safe nonce generation requires some unique input, such as a monotonic counter, or direct access to uniform randomness; neither of which are simple to obtain in a robust manner. If all parties were guaranteed to generate their nonces deterministically, we would again have the simple situation where the message and signing keys completely determined the Fiat-Shamir challenge, again allowing the simple solution of hashing the message with some secret. Such a guarantee is hard to obtain directly, but easy (in principle) to obtain by modifying the signing protocol to require all signers provide zero-knowledge proofs of their nonce generation. We discuss challenges in such an approach, including the difficulties with provable security and the limitations of using popular zero-knowledge proof schemes in resource-constrained environment such as hardware signing keys.
Notes from the SNARKonomicon: Techniques for Writing SNARK Programs
Izaak Mekler, O(1) Labs
Writing programs for SNARKs is, for now, somewhat of an obscure art. This showcase will cover the techniques learned in the process of writing the large SNARK programs used in Coda, as a way to spread this knowledge to the community at large. There are several kinds of knowledge that comprise “how to program SNARKs”. One is algorithmic techniques for efficiently encoding certain kinds of functions. Another is ways of thinking or mindsets that are useful in effectively structuring large non-deterministic programs. The primary goal of this showcase is to widely disseminate both the algorithmic techniques and the ways of thinking that we have found to be useful. The showcase will also acquaint the audience with concrete, real-world examples of different techniques, which they can use going forward as a “cook-book”.
Zero Knowledge Proofs and Self-Sovereign Identity
Jordi Baylina, Iden3
We will introduce iden3 project with a quick overview of our identity technology including the circom compiler and snarkJS library. Then we will talk about a proposal of how such ZK identity could be standardized with specific modules, protocols and data structures. Then we will talk about a proposal of a self sovereign identity standard with the ZK technology in mind. We will also explain the advantages and possibilities of such a system and will give an overview about the specific modules, protocols and data structures.
zk-SHARKs: Combining Succinct Verification and Public-Coin Setup
Madars Virza, MIT
We investigate the goal of deploying efficient non-interactive zero-knowledge proofs for moderately complex statements. Motivated by the desire to deploy ZK proofs in real world distributed ledger systems. we seek ZK proof systems that have fast verification time, short proof size, and no trusted setup. However, in terms of concrete parameters, we can achieve only two out of the three. In particular, it was not known how to achieve all of the following for million-gate circuits: * fast (milliseconds) verifier; * short proofs (couple kilobyte-long); and * does not reply on a structured reference string (e.g., trusted setup) for soundness or zero-knowledge. We propose a new form of proof systems: zk-SHARK (zero-knowledge Succinct Hybrid ARguments of Knowledge). These combine the fast verification of zk-SNARKs with the no-trusted-setup of some non-succinct NIZKs. A zk-SHARK has two verification modes: a prudent mode (relying on a uniform random string), and an optimistic mode (relying on a structured reference string). Crucially, even complete corruption of the setup used by optimistic verification does not invalidate the prudent verification. Moreover, old “prudent proofs” can be re-accelerated with a new optimistic mode setup (in case the old setup becomes unconvincing or compromised). We propose a construction of zk-SHARKs, tailored for efficiency of both modes: it is competitive with both state-of-the-art SNARKs (in terms of prover and verifier time) and NIZKs (in terms of proof size). Our zk-SHARK construction acieves all three properties outlined above. We also discuss the applicability to transaction and block verification in blockchain applications. Joint work with Mariana Raykova and Eran Tromer.
LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs
Dario Fiore, IMDEA
We study the problem of building SNARKs modularly by linking small specialized "proof gadgets" SNARKs in a lightweight manner. Our motivation is both theoretical and practical. On the theoretical side, modular SNARK designs would be flexible and reusable. In practice, specialized SNARKs have the potential to be more efficient than general-purpose schemes, on which most existing works have focused. If a computation naturally presents different "components" (e.g. one arithmetic circuit and one boolean circuit), a general-purpose scheme would homogenize them to a single representation with a subsequent cost in performance. Through a modular approach one could instead exploit the nuances of a computation and choose the best gadget for each component. In this talk I will present LegoSNARK, a “toolbox" (or framework) for commit-and-prove zkSNARKs (CP-SNARKs) that includes: (1) General composition tools: build new CP-SNARKs from proof gadgets for basic relations, simply. (2) A “lifting" tool: add commit-and-prove capabilities to a broad class of existing zkSNARKs, efficiently. This makes them interoperable (linkable) within the same computation. For example, one QAP-based scheme can be used prove one component; another GKR-based scheme can be used to prove another. (3) A collection of succinct proof gadgets for a variety of relations. Additionally, through our framework and gadgets, we are able to obtain new succinct proof systems. Notably: – LegoGro16, a commit-and-prove version of Groth16 zkSNARK, that operates over data committed with a classical Pedersen vector commitment, and that achieves a 5000x speedup in proving time. – LegoUAC, a pairing-based SNARK for arithmetic circuits that has a universal, circuit-independent, CRS, and proving time linear in the number of circuit gates (vs. the recent scheme of Groth et al. (CRYPTO'18) with quadratic CRS and quasilinear proving time). This is a joint work with Matteo Campanelli and Anais Querol.
Sonic: zkSNARKs from Linear-Size Universal and Updatable SRS
Sean Bowe, Electric Coin Company
Ever since their introduction, zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in a variety of applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zk-SNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal and updatable structured reference string, but the string scales quadratically in the size of the supported relations. Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updatable structured reference string that scales linearly in size. Sonic proofs are constant size, and in the batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature. We also describe a generally useful technique in which untrusted “helpers” can compute advice that allows batches of proofs to be verified more efficiently.
DIZK: a Distributed Zero Knowledge Proof System
Howard Wu, UC Berkeley and Dekrypt Capital
Recently there has been much academic and industrial interest in practical implementations of *zero knowledge proofs*. These techniques allow a party to *prove* to another party that a given statement is true without revealing any additional information. In a Bitcoin-like system, this allows a payer to prove validity of a payment without disclosing the payment's details. Unfortunately, the existing systems for generating such proofs are very expensive, especially in terms of memory overhead. Worse yet, these systems are "monolithic", so they are limited by the memory resources of a single machine. This severely limits their practical applicability. We describe DIZK, a system that *distributes* the generation of a zero knowledge proof across machines in a compute cluster. Using a set of new techniques, we show that DIZK scales to computations of up to billions of logical gates (100x larger than prior art) at a cost of 10μμs per gate (100x faster than prior art). We then use DIZK to study various security applications.
Enterprise Features for Confidential Asset Transfers
Ori Wallenstein, QEDIT
Enterprise Blockchains are substantially different than public Blockchains. Businesses looking to adopt zero-knowledge proofs for preserving privacy have unique constraints and requirements that allow offering new features and taking different trade-offs that would not be possible in a public Blockchain. In this talk I will discuss the zero-knowledge proof based solution QEDIT offers for confidential asset transfer. I will share details on some of the features of our solution and highlight how they were tailored for the specific needs of enterprise customers.
Zether: Towards Privacy in a Smart Contract World
Shashank Agrawal, Visa Research
Blockchain-based smart contract platforms like Ethereum have become quite popular as a way to remove trust and add transparency to distributed applications. While different types of important applications can be easily built on such platforms, there does not seem to be an easy way to add a meaningful level of privacy to them. In this talk, I will describe Zether, a fully-decentralized, confidential payment mechanism that is compatible with Ethereum and other smart contract platforms. Zether takes an account-based approach similar to Ethereum for efficiency and usability. It consists of a new smart contract that keeps the account balances encrypted and exposes methods to deposit, transfer and withdraw funds to/from accounts through cryptographic proofs. Zether also incorporates a mechanism to enable interoperability with arbitrary smart contracts. This helps to make several popular applications like auctions, payment channels, voting, etc. confidential. I will also talk about Sigma-Bullets, an improvement of the existing zero-knowledge proof system, Bulletproofs, which helps to make Zether more efficient. Sigma-Bullets make Bulletproofs more inter-operable with Sigma protocols, which is of general interest. We implemented Zether as an Ethereum smart contract and measured the amount of gas used. A Zether confidential transaction costs about 0.014 ETH or approximately $1.51 (as of early Feb, 2019). I will discuss how small changes to Ethereum, which are already being discussed independently of Zether, would drastically reduce this cost.
Succinct Proofs on Ethereum
Barry Whitehat, Ethereum Foundation
The ability to validate zero-knowledge proofs using bilinear pairings was added to Ethereum in October 2017. Since then the community has built 2 high-level languages to make writing zero-knowledge applications easier, and made many more advances. They have built solutions for: 1. private identity and credentials 2. anonymous voting/signaling 3. scalablity 4. private transactions and proposed solutions for anonymous reputation systems. Come hear about what we have built and what we are planning to build :)
Aurora, Transparent Succinct Arguments for R1CS
Nick Spooner, UC Berkeley
We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size O(log^2 n); it can be produced with O(nlogn) field operations and verified with O(n). At 128 bits of security, proofs are less than 250kB even for several million constraints, more than 10x shorter than prior SNARGs with similar features. A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed--Solomon codeword over any subgroup of a field. We also provide libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.
Public Accountability vs. Secret Laws: Can They Coexist?
Shafi Goldwasser, UC Berkeley, MIT and Weizmann
Post 9/11, journalists, scholars and activists have pointed out that secret laws --- a body of law whose details and sometime mere existence is classified as top secret --- were on the rise in all three branches of the US government due to growing national security concerns. Amid heated current debates on governmental wishes for exceptional access to encrypted digital data, one of the key issues is: which mechanisms can be put in place to ensure that government agencies follow agreed-upon rules in a manner which does not compromise national security objectives? This promises to be especially challenging when the rules, according to which access to encrypted data is granted, may themselves be secret. In this work we show how the use of cryptographic protocols, and in particular, the use of zero-knowledge proofs can ensure accountability and transparency of the government in this extraordinary, seemingly deadlocked, setting. We propose an efficient record-keeping infrastructure with versatile publicly verifiable audits that preserve perfect (information-theoretic) secrecy of record contents as well as of the rules by which the records are attested to abide. Our protocol is based on existing blockchain and cryptographic tools including commitments and zero-knowledge SNARKs, and satisfies the properties of indelibility (i.e., no back-dating), perfect data secrecy, public auditability of secret data with secret laws, accountable deletion, and succinctness. We also propose a variant scheme where entities can be required to pay fees based on record contents (e.g., for violating regulations) while still preserving data secrecy. Our scheme can be directly instantiated on the Ethereum blockchain (and a simplified version with weaker guarantees can be instantiated with Bitcoin).
Efficient Zero-Knowledge Protocols: The Modular Approach
Yuval Ishai, Technion
I will discuss the following modular approach for the design of efficient zero-knowledge protocols: (1) design an “information-theoretic” probabilistic proof system; (2) apply a cryptographic compiler to obtain a zero-knowledge protocol whose security is based on cryptographic assumptions. Most efficient zero-knowledge protocols from the literature can be cast into the above framework. The talk will give an overview of different types of proof systems and cryptographic compilers that give rise to a wide range of efficiency and security tradeoffs.
Privacy-enhancing Cryptography at NIST
Rene Peralta, NIST
We will talk about crypto standards at NIST and how it may relate to the ZKProof initiative. We will overview some of the history of crypto standards development at NIST. This informs our thinking regarding crypto areas that currently fall in uncharted territory with respect to standardization. An area of current interest at NIST is privacy-enhancing cryptography (PEC). Within this scope, we believe that it would be useful to develop reference material (documentation and implementations). Zero-knowledge techniques are an important component of this, along with techniques from Secure Multiparty Computation. Considering some PEC use cases as a basis, we will ask whether the current ZKProof proposal (as spelled out in the various public documents) is a good match for the anticipated needs.
Panel: Zero Knowledge in the Enterprise
Carlos Kuchovsky (BBVA), Yael Kalai (Microsoft), Mike Hearn (R3) and Jonathan Levi (HACERA); moderated by Jonathan Rouach (QEDIT)
Discrete Log based Zero-Knowledge Proofs
Dan Boneh, Stanford
MPC-in-the-Head based Zero-Knowledge Proofs
Amit Sahai, UCLA
GKR based Zero-Knowledge Proofs
Yael Kalai, Microsoft Research
IOP based Zero-Knowledge Proofs
Alessandro Chiesa, UC Berkeley
Bilinear Pairings based Zero-Knowledge Proofs
Jens Groth, DFINITY
From Public-Key Cryptography to PKI: Reflections on Standardizing the RSA Algorithm
Jim Bidzos and Burt Kaliski, Verisign
When Rivest, Shamir and Adleman invented the RSA public-key cryptosystem in 1977, security applications — to the extent they employed encryption at all — relied on symmetric-key cryptography and infrastructures, such as the Data Encryption Standard (DES). Public-key cryptography had just been discovered by Diffie, Hellman and Merkle, and it would still take another decade or so until all the elements were in place — from algorithms to protocols to public-key infrastructure (PKI) —that have made public-key cryptography the standard way to secure applications today. Specifying those elements involved a collaborative effort where industry not only learned the new language of public-key cryptography in a technical sense but also started speaking it in products and policies. The story of the standardization of the RSA algorithm offers insights both for understanding how today’s public-key infrastructure came to be, and for approaching standards efforts for additional cryptographic technologies such as zero knowledge proofs. Jim Bidzos Jim Bidzos is president and chief executive officer of Verisign. He also serves as chairman of the board of directors and has been executive chairman since August 2009. As the founder of Verisign, Bidzos is an Internet and security industry pioneer whose accomplishments include building RSA Security into the early standard-bearer for authentication and encryption, and launching Verisign as a company in 1995 to develop the digital certificate infrastructure for Internet commerce. Burt Kaliski Burt Kaliski is senior vice president and chief technology officer of Verisign. Kaliski started his career at RSA Security in 1989, where, as the founding scientist of RSA Laboratories, his contributions included the development of the Public-Key Cryptography Standards (PKCS), now widely deployed in Internet security.
Zero Knowledge Ideal Functionality
Muthu Venkitasubramaniam, University of Rochester and Ligero