09:50–10:00 

Welcome

10:00–10:30 
Dakshita Khurana

Statistical WI (and more) in Two Messages



Abstract:
In this talk, I will present techniques that use twomessage oblivious transfer (OT) to construct twomessage arguments with strong privacy guarantees. Specifically, assuming quasipolynomial security of OT, we construct twomessage arguments that are witness indistinguishable, and in the delayedinput setting, are also strong witness indistinguishable and witness hiding. We also show how to achieve (similar) statistical privacy guarantees, which were previously not known to be achievable in protocols requiring two messages.
This is based on joint works with Abhishek Jain, Yael Kalai, Ron Rothblum and Amit Sahai.

10:30–11:00 
Pratyush Mishra

Oblix: An Efficient Oblivious Search Index



Abstract:
In this talk we present Oblix, a search index for encrypted data that is oblivious (provably hides access patterns), is dynamic (supports inserts and deletes), and has good efficiency (operations take only a few milliseconds).
To achieve these properties, Oblix uses novel obliviousaccess techniques inside remote hardware enclaves (e.g., Intel SGX). In particular, since these enclaves leak memory access patterns, we design and implement doublyoblivious data structures, which hide access patterns to both external (server) memory, and to the (enclaved) client's internal memory.
We demonstrate the usefulness of Oblix in several applications: private contact discovery for Signal, private retrieval of public keys for Key Transparency, and searchable encryption that hides access patterns and result sizes.
This is joint work with Rishabh Poddar, Jerry Chen, Alessandro Chiesa, and Raluca Ada Popa.

11:00–11:30 

Break

11:30–12:30 
Yael Kalai

A Unified Approach for Delegating Computations Under Standard Assumptions (Keynote)



Abstract:
In the past few years there have been several new constructions of oneround delegation schemes based on standard assumptions (such as the Learning with Error assumption). We have seen such constructions for all deterministic computations, for batch NP computations, for NTISP computations, and more. In this talk, I will survey these results with a single unifying approach.

12:30–13:30 

Lunch (provided)

13:30–14:00 
Benedikt Buenz

Bulletproofs: Short Proofs for Confidential Transactions and More



Abstract:
This talk will describe Bulletproofs, a new noninteractive zeroknowledge proof protocol with very short proofs and without a trusted setup; the proof size is only logarithmic in the witness size. Bulletproofs are especially well suited for efficient range proofs on committed values: they enable proving that a committed value is in a range using only 2log2(n)+9log2(n)+9 group and field elements, where n is the bit length of the range. Proof generation and verification times are linear in n. Moreover, Bulletproofs supports aggregation of range proofs, so that a party can prove that m commitments lie in a given range by providing only an additive O(log(m)) group elements over the length of a single proof. We show that verification time, while asymptotically linear, is very efficient in practice. Moreover, the verification of multiple Bulletproofs can be batched for further speedup.
Bulletproofs build on the techniques of Bootle et al. (EUROCRYPT 2016). Beyond range proofs, Bulletproofs provide short zeroknowledge proofs for general arithmetic circuits while only relying on the discrete logarithm assumption and without requiring a trusted setup. The efficiency of Bulletproofs is particularly well suited for the distributed and trustless nature of blockchains.
This work is joint with Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Greg Maxwell.

14:00–14:30 
abhi shelat

Hyrax vs Ligero vs STARK vs Bullets



Abstract:
I will first present Hyrax, [Wahby, Tzialla, shelat, Thaler, Walfish’ 2018], a zeroknowledge argument for NP with low communication complexity, low concrete cost for both the prover and the verifier, and no trusted setup, based on standard cryptographic assumptions (DDH) and the random oracle model. Specifically, communication is sublinear in the size of the witness plus $d⋅log(G)$ where $d$ is the depth and $G$ is the width of the verifying circuit. When applied to batched or dataparallel statements, the prover’s cost is linear and the verifier’s cost is sublinear in the verifying circuit size, both with good constants. Together, these properties represent a new point in the tradeoffs among setup, complexity assumptions, proof size, and computational cost. We evaluate Hyrax on three benchmarks, SHA256 Merkle trees, image transformation, and matrix multiplication and show scalability and smaller proof sizes versus prior work.
Recently, there are 3 other interesting zeroknowledge argument systems with sublinear proof sizes: Ligero, STARKs, and bulletproofs. I will present comparisons between these 4 systems and share brisk commentary on how these ideas may lead to even better schemes.

14:30–15:00 
David Wu

MultiTheorem Preprocessing NIZKs from Lattices



Abstract:
Noninteractive zeroknowledge (NIZK) proofs are fundamental to modern cryptography. Numerous NIZK constructions are known in both the random oracle and the common reference string (CRS) models. In the CRS model, there exist constructions from several classes of cryptographic assumptions such as trapdoor permutations, pairings, and indistinguishability obfuscation. Notably absent from this list are constructions from standard lattice assumptions. While there has been partial progress in realizing NIZKs from lattices for specific languages, constructing NIZK proofs (and arguments) for all of NP from standard lattice assumptions remains open.
In this work, we make progress on this problem by giving the first construction of a multitheorem NIZK argument for NP from standard lattice assumptions in the preprocessing model, where a (trusted) setup algorithm generates a proving and a verification key. In the multitheorem setting, the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zeroknowledge. Existing constructions of preprocessing NIZKs that rely on weaker assumptions like oneway functions or oblivious transfer are only secure in a singletheorem setting. Thus, constructing multitheorem NIZKs in the preprocessing model does not seem to be inherently easier than constructing them in the CRS model.
In this talk, I will first show how we can construct a multitheorem preprocessing NIZK from contexthiding homomorphic signatures (based on LWE). Then, I show how to efficiently implement the preprocessing step using a new cryptographic primitive called blind homomorphic signatures. Finally, I will show how our latticebased preprocessing NIZKs can be used to obtain new malicioussecure MPC protocols from standard lattice assumptions.

15:00–15:30 

Break

15:30–16:00 
Peihan Miao

TwoRound Multiparty Secure Computation Minimizing Public Key Operations



Abstract:
We show new constructions of semihonest and malicious tworound multiparty secure computation protocols using only (a fixed) poly(n,k) invocations of a tworound oblivious transfer protocol (which use expensive publickey operations) and poly(k, C) cheaper oneway function calls, where k is the security parameter, n is the number of parties, and C is the circuit being computed. All previously known tworound multiparty secure computation protocols required poly(k,C) expensive publickey operations.
Based on joint work with Sanjam Garg and Akshayaram Srinivasan.

16:00–16:30 
Pratyay Mukherjee

Threshold Authenticated Encryption



Abstract:
Threshold cryptography provides a mechanism for protecting secret keys by sharing them among multiple parties, who then jointly perform a cryptographic task. An attacker who actively corrupts up to a threshold number of parties, however, is unable to recover the secret nor violate security of the cryptographic task. There are many real world applications, ranging from keymanagement in servers to distributed authentication in cryptocurrencies where threshold primitives can be/have been extremely useful. Prior works in this space have mainly focused on definitions and constructions for publickey cryptography and digital signatures, and fail to capture the security concerns and efficiency challenges of symmetrickey based applications.
In this work we put forward the first formal treatment for threshold authenticated encryption. We propose a generic construction of threshold authenticated encryption based on any distributed pseudorandom function (DPRF). Instantiating with two concrete DPRF schemes we obtain two efficient constructions with different qualities. Our most efficient instantiation only uses symmetrickey primitives and achieves a throughput of up to 1 million encryptions/decryptions per seconds, or alternatively a submillisecond latency with up to 18 participating parties.
In this talk I will first discuss the new notions, and the subtleties that arise in the distributed setting. Then I will be describing our constructions in detail. I will be concluding with a comparative analysis of our concrete instantiations.
Joint work with Shashank Agrawal (Visa Research), Payman Mohassel (Visa Research) and Peter Rindal (Oregon State).

16:30–17:00 
Dan Boneh

Multisignatures for cryptocurrencies



Abstract:
We construct new multisignature schemes that provide new functionality. Our schemes are designed to reduce the size of the Bitcoin blockchain, but are useful in many other settings where multisignatures are needed. All our constructions support both signature compression and publickey aggregation. Hence, to verify that a number of parties signed a common message m, the verifier only needs a short multisignature, a short aggregation of their public keys, and the message m. We give new constructions that are derived from Schnorr signatures and from BLS signatures. Our constructions are in the plain public key model, meaning that users do not need to prove knowledge or possession of their secret key.
In addition, we construct the first short accountablesubgroup multisignature (ASM) scheme. An ASM scheme enables any subset S of a set of n parties to sign a message m so that a valid signature discloses which subset generated the signature (hence the subset S is accountable for signing m). We construct the first ASM scheme where signature size is only O(k) bits over the description of S, where k is the security parameter. Similarly, the aggregate public key is only O(k) bits, independent of n. The signing process is noninteractive. Our ASM scheme is very practical and well suited for compressing the data needed to spend funds from a tofn Multisig Bitcoin address, for any (polynomial size) t and n.
