10:00–10:30 
Muthuramakrishnan Venkitasubramaniam

Ligero: Lightweight Sublinear Arguments Without a Trusted Setup



Abstract:
We design and implement a simple zeroknowledge argument protocol for NP whose communication complexity is proportional to the squareroot of the verification circuit size. The protocol can be based on any collisionresistant hash function. Alternatively, it can be made noninteractive in the random oracle model, yielding concretely efficient zkSNARKs that do not require a trusted setup or publickey 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 SHA256 preimage in zeroknowledge 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 zeroknowledge 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 zeroknowledge interactive PCP based on ``interleaved'' ReedSolomon codes.
Joint work with Scott Ames, Carmit Hazay and Yuval Ishai.

10:30–11:00 
Dima Kogan

The discretelogarithm problem with preprocessing



Abstract:
We study discretelog 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 P256). 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 discretelog 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 discretelog algorithm with preprocessing. Our lower bound, which is tight up to logarithmic
factors, uses a synthesis of incompressibility techniques and classic methods
for genericgroup lower bounds. We apply our techniques to prove related lower
bounds for the CDH, DDH, and multiplediscretelog problems.
Finally, we demonstrate two new generic preprocessing attacks: one for the
multiplediscretelog problem and one for certain decisionaltype 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 discretelog problem.
This is joint work with Henry CorriganGibbs.

11:00–11:30 

Break

11:30–12:30 
Amit Sahai

Super Simulation! (Keynote)



Abstract:
Polynomialtime simulation has long been the gold standard in cryptography. Indeed, polynomialtime 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, subexponential 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 subexponentially 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 superpolynomial 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 subexponential hardness assumptions such as subexponential DDH.
This talk is primarily based on joint work with Dakshita Khurana (FOCS 2017).

12:30–13:30 

Lunch (on your own)

13:30–14:00 
Akshayaram Srinivasan

Tworound secure multiparty computation from minimal assumptions



Abstract:
We give a construction of tworound secure multiparty computation based on the minimal assumption that tworound oblivious transfer exists.
Based on joint work with Sanjam Garg.

14:00–14:30 
Mohammad Hajiabadi

Can publickey encryption be based on oneway functions via nonblackbox garbling techniques?



Abstract:
Understanding whether publickey encryption can be based on oneway functions is a fundamental open problem in cryptography. The seminal work of Impagliazzo and Rudich (STOC 87) showed that blackbox constructions of publickey encryption from oneway functions are impossible. However, this impossibility result leaves open the possibility of using nonblackbox techniques for achieving this goal.
One of the most useful class of nonblackbox techniques in cryptography are garbling techniques (Yao FOCS'86).
We investigate whether we can use oneway functions and garbling schemes together to get publickey encryption.
In fact, the recent work of D\"ottling and Garg (CRYPTO'17) follows a similar recipe for bypassing known blackbox impossibility results for obtaining identitybased encryption.
We prove that similar nonblackbox uses of oneway functions together with garbling are still insufficient for realizing publickey 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 blackbox use of garbling of circuits that have oneway function (or even random oracle) gates in them is insufficient for obtaining publickey encryption.
Joint work with Sanjam Garg, Mohammad Mahmoody and Ameer Mohammed.

14:30–15:00 
Ari Juels

Enter the Hydra: Towards Principled Bug Bounties and ExploitResistant Smart Contracts



Abstract:
Vulnerability reward programs, a.k.a. bug bounties, are a nearuniversal 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 costeffectively 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 securitycritical vulnerability. We focus on a broadly applicable realization through a variant of the classic idea of Nversion 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 bugexploitation, 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 wellknown exploits todate against Ethereum smart contracts, showing that multilanguage 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.

15:00–15:30 

Break

15:30–16:00 
David Wu

QuasiOptimal SNARGs via Linear MultiProver Interactive Proofs



Abstract:
Succinct noninteractive 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 quasioptimally succinct if its proof length is quasilinear in the security parameter, and that it is quasioptimal, if moreover, its prover complexity is only polylogarithmically 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 quasioptimal SNARG for Boolean circuit satisfiability from a concrete cryptographic assumption. Our construction takes a twostep approach. The first is an informationtheoretic construction of a quasioptimal linear multiprover interactive proof (linear MIP) for circuit satisfiability. Then, we describe a generic cryptographic compiler that transforms our quasioptimal linear MIP into a quasioptimal SNARG by relying on the notion of linearonly vector encryption over rings introduced by Boneh et al. (Eurocrypt 2017). Combining these two primitives yields the first quasioptimal SNARG based on linearonly vector encryption.
Joint work with Dan Boneh, Yuval Ishai, and Amit Sahai.

16:00–16:30 
Mohammad Mahmoody

Blockwise pTampering Attacks on Cryptographic Primitives, Extractors, and Learners



Abstract:
Austrin, Chung, Mahmoody, Pass and Seth (Crypto'14) introduced the notion of bitwise ptampering 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 privacybased cryptographic primitives through bitwise ptampering 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 ptampering 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 multisource 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.
