Bay Area Crypto Day

We design and implement a simple zero-knowledge argument protocol for NP whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography.

Our protocol is attractive not only for very large verification circuits but also for moderately large circuits (Boolean or Arithmetic) that arise in applications. For instance, for verifying a SHA-256 preimage in zero-knowledge with 2^{-40} soundness error, the communication complexity is roughly 44KB (or less than 34KB under a plausible conjecture), the prover running time is 140 ms, and the verifier running time is 62 ms. This proof is roughly 4 times shorter than a similar proof of ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo (Giacomelli et al., USENIX 2016).

The communication complexity of our protocol is independent of the circuit structure and depends only on the number of gates. For $2^{-40}$ soundness error, the communication becomes smaller than the circuit size for circuits containing roughly 3 million gates or more. Our efficiency advantages become even bigger in an amortized setting, where several instances need to be proven simultaneously.

Our zero-knowledge protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC 2007) to a variant of the protocol for secure multiparty computation of Damgård and Ishai (Crypto 2006). It can be viewed as a simple zero-knowledge interactive PCP based on ``interleaved'' Reed-Solomon codes.

Joint work with Scott Ames, Carmit Hazay and Yuval Ishai.

We study discrete-log algorithms that use preprocessing. In our model, an adversary may use a very large amount of precomputation to produce an "advice" string about a specific group (e.g., NIST P-256). In a subsequent online phase, the adversary's task is to use the preprocessed advice to quickly compute discrete logarithms in the group. Motivated by surprising recent preprocessing attacks on the discrete-log problem, we study the power and limits of such algorithms.

In particular, we focus on generic algorithms that operate in every cyclic group. We show a lower bound on the success probability of any generic discrete-log algorithm with preprocessing. Our lower bound, which is tight up to logarithmic factors, uses a synthesis of incompressibility techniques and classic methods for generic-group lower bounds. We apply our techniques to prove related lower bounds for the CDH, DDH, and multiple-discrete-log problems.

Finally, we demonstrate two new generic preprocessing attacks: one for the multiple-discrete-log problem and one for certain decisional-type problems in groups. This latter result demonstrates that, for generic algorithms with preprocessing, distinguishing tuples of the form [g, g^x, g^(x^2)] from random is much easier than the discrete-log problem.

This is joint work with Henry Corrigan-Gibbs.

Polynomial-time simulation has long been the gold standard in cryptography. Indeed, polynomial-time simulation delivers conceptually simple and generally composable notions of security. However, a drawback of polynomial simulation is the need for significant interaction to achieve security in the plain model.

At the same time, sub-exponential hardness is essential for the usefulness of cryptography as we know it. For example, if RSA were insecure against 2^{n^{0.1}} adversaries, the size of meaningfully secure RSA keys would need to exceed 10^18 bits!

In this talk, we ask: what is the "right" notion of simulation in a world of sub-exponentially hard problems? Can we gain advantages in interaction, while still enjoying the most essential composition properties of polynomial simulation?

To answer this question, we consider a notion we call super-polynomial strong simulation (SPSS), and show how it can offer powerful composition properties. We show how to achieve SPSS protocols with just a single message each from the prover and verifier, based on standard sub-exponential hardness assumptions such as sub-exponential DDH.

This talk is primarily based on joint work with Dakshita Khurana (FOCS 2017).

We give a construction of two-round secure multiparty computation based on the minimal assumption that two-round oblivious transfer exists.

Based on joint work with Sanjam Garg.

Understanding whether public-key encryption can be based on one-way functions is a fundamental open problem in cryptography. The seminal work of Impagliazzo and Rudich (STOC 87) showed that black-box constructions of public-key encryption from one-way functions are impossible. However, this impossibility result leaves open the possibility of using non-black-box techniques for achieving this goal.

One of the most useful class of non-black-box techniques in cryptography are garbling techniques (Yao FOCS'86). We investigate whether we can use one-way functions and garbling schemes together to get public-key encryption. In fact, the recent work of D\"ottling and Garg (CRYPTO'17) follows a similar recipe for bypassing known black-box impossibility results for obtaining identity-based encryption.

We prove that similar non-black-box uses of one-way functions together with garbling are still insufficient for realizing public-key encryption. In particular, we prove our impossibility result in a model introduced by Brakerski, Katz, Segev, and Yerukhimovich (TCC'11) and Asharov and Segev (FOCS'15) tailored to garbling schemes. Namely, we show that black-box use of garbling of circuits that have one-way function (or even random oracle) gates in them is insufficient for obtaining public-key encryption.

Joint work with Sanjam Garg, Mohammad Mahmoody and Ameer Mohammed.

Vulnerability reward programs, a.k.a. bug bounties, are a near-universal component of major software security programs. Today, though, such programs have three major deficiencies. They fail to provide strong technical (or other) assurances of fair payment for reported bugs, lack rigorous principles for setting bounty amounts, and can only effectively incentivize economically rational hackers to disclose bugs by offering rich bounties. As a result, rather than reporting bugs, hackers often choose to sell or weaponize them. We offer a novel, principled approach to administering and reasoning about bug bounties that cost-effectively boosts incentives for hackers to report bugs. Our key idea is a concept that we call an exploit gap. This is a transformation of program code that prevents a serious bug from being exploited as a security-critical vulnerability. We focus on a broadly applicable realization through a variant of the classic idea of N-version programming. We call the result a hydra program. As our main target application, we explore smart contracts, programs that execute on blockchains. Because smart contracts are often financial instruments, they offer a springboard for our rigorous framework to reason about bounty price setting. By modeling an economically rational hacker's bug-exploitation, we show how hydra contracts greatly amplify the power of bounties to financially incentivize disclosure. We also show how smart contracts can separately enforce fairness for bug bounties, guaranteeing payment for correctly reported bugs. We present a survey of well-known exploits to-date against Ethereum smart contracts, showing that multi-language hydra programming would have abated most of them. We also report on implementation of hydra Ethereum contracts.

Joint work with Lorenz Breidenbach, Phil Daian, and Florian Tramèr.

Succinct non-interactive arguments (SNARGs) enable verifying NP computations with significantly less complexity than that required for classical NP verification. In this work, we focus on simultaneously minimizing the proof size and the prover complexity of SNARGs. Concretely, for a security parameter k, we measure the asymptotic cost of achieving soundness error 2^{-k} against provers of size 2^k. We say a SNARG is quasi-optimally succinct if its proof length is quasilinear in the security parameter, and that it is quasi-optimal, if moreover, its prover complexity is only poly-logarithmically greater than the running time of the classical NP prover. These bounds are the best we could hope for assuming that NP does not have succinct proofs.

In this work, we give the first quasi-optimal SNARG for Boolean circuit satisfiability from a concrete cryptographic assumption. Our construction takes a two-step approach. The first is an information-theoretic construction of a quasi-optimal linear multi-prover interactive proof (linear MIP) for circuit satisfiability. Then, we describe a generic cryptographic compiler that transforms our quasi-optimal linear MIP into a quasi-optimal SNARG by relying on the notion of linear-only vector encryption over rings introduced by Boneh et al. (Eurocrypt 2017). Combining these two primitives yields the first quasi-optimal SNARG based on linear-only vector encryption.

Joint work with Dan Boneh, Yuval Ishai, and Amit Sahai.

Austrin, Chung, Mahmoody, Pass and Seth (Crypto'14) introduced the notion of bitwise p-tampering attacks over randomized algorithms in which an efficient `virus' gets to control each bit of the randomness with independent probability p in an online way, and they showed how to break the security of privacy-based cryptographic primitives through bitwise p-tampering attacks.

In this work, we revisit and extend the bitwise tampering model of Austrin et al. to the blockwise setting where each incoming block of randomness becomes tamperable with independent probability p. Our main result is an efficient blockwise p-tampering attack to bias the average of any efficient function f mapping arbitrary distribution X to [-1,+1] by \Omega(p Var[f(X)]), where Var[f(X)] is the variance of f(X), regardless of how X is partitioned into individually tamperable blocks X=(X_1,...,X_n). Further, relying on the blockwise nature of our biasing attack, we show how to bias the output of any seedless multi-source extractors if each source becomes tamperable with independent probability p. Finally we show how to increase the classification error of deterministic learners in the so called `poisoning' attack model under Valiant's adversarial noise where the adversary gets to tamper with each training example with independent probability p.

Joint work with: Saeed Mahloujifar.