Bay Area Crypto Day

Rendezvous is a communication system that cryptographically protects metadata. Unlike all existing systems for metadata-hiding communication, Rendezvous does not require users to communicate in synchronous messaging rounds: Rendezvous provides meaningful metadata-hiding guarantees even if different users interact with the system at different rates. A Rendezvous deployment consists of a three-server cluster, and the system protects user privacy even if an active attacker controls one of the servers and any number of users.

Every pair of Rendezvous users shares a secret virtual address that points to a unique mailbox stored at the servers. By cryptographically protecting accesses to virtual addresses, the honest servers prevent malicious servers and users from learning which mailbox has been updated when. By applying new cryptographic tools for detecting disruption attacks by malicious clients, Rendezvous reduces the bandwidth cost per message from O(√N) to O(logN) bits in an N-user deployment, which yields 4× and 8× overall performance improvements on the server and client sides, respectively, and reduces communication costs by one or more orders magnitude. Finally, we discuss how Rendezvous might apply in practice to protect communication between journalists and sources.

This is joint work with Henry Corrigan-Gibbs, Matei Zharia, and Dan Boneh.

Many organizations wish to collaboratively train machine learning models on their combined datasets for a common benefit (e.g., better medical research, or fraud detection). However, they often cannot share their plaintext datasets due to privacy concerns and/or business competition. In this paper, we design and build Helen, a system that allows multiple parties to train a linear model without revealing their data, a setting we call "coopetitive learning". Compared to prior secure training systems, Helen protects against a much stronger adversary who is malicious and can compromise m − 1 out of m parties. Our evaluation shows that Helen can achieve up to multiple orders of magnitude of performance improvement when compared to training using an existing state-of-the-art secure multi-party computation framework.

GGH15 encodings provide a way to "encrypt" many pairs of matrices, such that we can check whether any subset product is zero, while potentially hiding all other information about the matrices. This immediately yields a remarkably simple candidate obfuscator for NC1, whose security seems related to the LWE assumption. So, how far are we from obfuscation for circuits or NC1 from LWE? How about smaller classes of functions, like read-once branching programs, or the constant function?

In this talk, we will present some answers to this question:

• a proof from LWE that the simple obfuscator is indeed secure for a large sub-class of the all-reject function (which yields new constructions of lockable obfuscation, private constrained PRFs and mixed FE schemes for NC1);

• an attack on the GGH15-based obfuscator for read-once branching programs from CCS17;

• a new and simple candidate obfuscator for NC1 (and an even simpler one for witness encryption).

The presentation slides are available here.

The delegated preparation of single-qubit quantum states is an elementary building block in many quantum cryptographic protocols, including protocols for delegating quantum computations.

We introduce a protocol between a classical polynomial-time verifier and a quantum polynomial-time prover that allows the verifier to securely delegate to the prover the preparation of certain single-qubit quantum states. As a consequence we obtain a new protocol for blind and verifiable delegated quantum computation.

Compared to the recent work of (Mahadev 2018), who introduced the first such protocol, our protocol is more modular, applies to the measurement-based model of computation (instead of the Hamiltonian model) and is composable. Our proof of security builds on ideas introduced in (Brakerski et al. 2018).

In the talk I will not assume any background in quantum computing, and will focus on the motivation and main ideas behind our new resource of remote state preparation and its application to delegating quantum computations.

Based on joint work with Alexandru Gheorghiu.

In this talk, I will introduce ZEXE, a system for conducting privacy-preserving decentralized computations using zero-knowledge proofs. I will focus on how one can use the strong privacy, expressivity, and efficiency guarantees of ZEXE to realize privacy-preserving analogues of popular applications, such as private user-defined assets, regulation-friendly private stablecoins, and private decentralized exchanges that allow users to trade these while providing front-running resistance.

We present batching techniques for cryptographic accumulators and vector commitments in groups of unknown order. Our techniques are tailored for distributed settings where no trusted accumulator manager exists and updates to the accumulator are processed in batches. We develop techniques for non-interactively aggregating membership proofs that can be verified with a constant number of group operations. We also provide a constant sized batch non-membership proof for a large number of elements. These proofs can be used to build the first positional vector commitment (VC) with constant sized openings and constant sized public parameters. As a core building block for our batching techniques we develop several succinct proof systems in groups of unknown order. These extend a recent construction of a succinct proof of correct exponentiation, and include a succinct proof of knowledge of an integer discrete logarithm between two group elements. We use these new constructions to design a stateless blockchain, where nodes only need a constant amount of storage in order to participate in consensus. Further, we show how to use these techniques to reduce the size of IOP instantiations, such as STARKs. This is joint work with Dan Boneh and Ben Fisch.

We consider the problem of constructing leakage-resilient circuit compilers that are secure against global leakage functions with bounded output length. By global, we mean that the leakage can look at every wire of the circuit and output a low-complexity function (represented as a boolean circuit) applied on these wires. In this work, we design compilers both in the stateless (a.k.a. the single-shot leakage) as well as stateful (a.k.a. the continuous leakage) setting that are unconditionally secure against AC0 leakage and similar low-complexity classes. In the stateless case, we show that the original private circuits construction of Ishai, Sahai, and Wagner (Crypto 2003) is actually secure against AC0 leakage. In the stateful case, we modify the construction of Rothblum (Crypto 2012), obtaining a simple construction with unconditional security. Prior works that designed leakage-resilient circuit compilers against AC0 leakage had to rely either on secure hardware components (Faust et al., Eurocrypt 2010, Miles-Viola, STOC 2013) or on (unproven) complexity-theoretic assumptions (Rothblum, Crypto 2012).

Joint work with Andrej Bogdanov and Yuval Ishai.

Oblivious Transfer has played a crucial role in the design of secure multi party computation. Nevertheless, there are not many practical solutions that achieve simulation based security and at the same time are instantiable based on different assumptions.

In this work, we show how to construct highly efficient oblivious transfer in the random oracle model that achieves simulation based security under a wide range of assumptions, among them DDH, CDH, LWE and coding based assumptions. We revise classical security notions and propose a new security notion that we call endemic security. We construct an endemically secure oblivious transfer based on DDH that takes only a single communication round which allows significant performance gains over previously known solutions. We also instantiate our oblivious transfer with the Crystals.Kyber key agreement. Our implementation shows that both instantiations can be computed in under one millisecond.

Further, our new security notion also allows us to revisit, correct and improve existing oblivious transfer extension techniques. We provide an implementation of an oblivious transfer extension protocol in the ideal cipher model that is actively secure, processing up to 23 million OTs per second and up to 10 times faster than previous secure implementations. We also show that our framework can compute endemically secure OT extension and the base OTs in just two rounds.

Joint work with Daniel Masny.