Bay Area Crypto Day

Aggregator-oblivious (AO) encryption is a useful notion that allows an untrusted aggregator to periodically compute aggregate statistics over sensitive data contributed by a set of users. Such encryption schemes find numerous applications, in particular in the context of privacy-preserving smart metering. Most existing AO schemes suffer from three main drawbacks:

1. Several schemes require the presence of a third-party and additional communication channels between users and these third-parties. In certain settings, such assumptions make the schemes impractical.

2. Many schemes do not tolerate user failures. Even if a single user fails to report their contribution, the aggregator will not be able to compute anything. In a fault-tolerant scheme, the aggregator is able to compute an aggregate, maybe imprecise, when some users fail.

3. In most cases, the group of users that are aggregated is static: the keys are dependent on the other users. For many applications, it is desirable to have a dynamic scheme. A dynamic scheme allows users to join or leave a group without redistribution of keys to everyone. With a dynamic scheme, the aggregator can easily perform the aggregation scheme with a subset of users without having to redistribute keys.

This talk will present a number of practical AO encryption schemes, which provably meet the AO security notion under standard complexity assumptions.

Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. In this talk, I will discuss a new protocol and implementation for secure three-party computation (3PC) based on garbled circuits that improves security (malicious security) while maintaining practical efficiency that is competitive with traditional information-theoretic protocols.

Joint Work with Mike Rosulek and Ye Zhang

The Snowden revelations expose a mass surveillance program that compromises cryptography in new ways: ways that are not captured by current theoretical models, and that current schemes, accordingly, do not resist. We discuss a research agenda that aims for greater security in this age by crafting models definitions that capture the new threats and then providing schemes meeting these new definitions. Specifically we will discuss algorithm-substitution attacks, key exfiltration via APTs, attacks on randomness and the subversion of public parameters.

Deciding “greater-than” relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of obfuscation machinery and is currently not implementable.

We construct the first implementable encryption system, which we call order-revealing encryption, that supports greater-than comparisons on encrypted data and provides the “best-possible” semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation, and only rely on multilinear maps.

Then, we study efficient order-revealing encryption schemes from one-way functions. We present the first order-revealing encryption scheme which achieves a simulation-based security notion with respect to a leakage function that precisely specifies what is leaked from encryptions. Our scheme, when composed with existing schemes, is strictly more secure than all other existing non-interactive order-preserving encryption schemes.

Joint works with Dan Boneh, Mariana Raykova, Amit Sahai, Mark Zhandry, and Joe Zimmerman, and also Nathan Chenette, Steve Weis, and David Wu.

A secure reverse firewall, as recently defined by Mironov and Stephens-Davidowitz, is a third party that "sits between a user and the outside world" and modifies the user's sent and received messages so that even if the user's machine has been corrupted, her security is still guaranteed! In other words, reverse firewalls allow us to provide meaningful (and, indeed, very strong) security guarantees against powerful adversaries that may have tampered with the user's hardware or software (or adversaries that are aware of bugs in the user's protocol implementation). A long list of recent events and disclosures shows that such threats are extremely common in practice, and they present a serious, arguably existential, threat to cryptography. Importantly, reverse firewalls defend against such threats without sharing any secrets with the user, and in general we expect the user to place no more trust in the firewall than she places in her communication channel.

While Mironov and Stephens-Davidowitz demonstrated that reverse firewalls can be constructed for very strong cryptographic primitives (which are of mostly theoretical interest), we study reverse firewalls for perhaps the most natural cryptographic task: secure message transmission. We find a rich structure of solutions that vary in efficiency, security, and setup assumptions, in close analogy with message transmission in the classical setting. Our strongest and most important result shows a protocol that achieves interactive, concurrent CCA-secure message transmission with a reverse firewall---i.e., CCA-secure message transmission on a possibly compromised machine! Surprisingly, this protocol is quite efficient and simple, requiring only a small constant number of public-key operations. It could easily be used in practice. Behind this result is a technical composition theorem that shows how key agreement with a sufficiently secure reverse firewall can be used to construct a message-transmission protocol with its own secure reverse firewall.

Recent advances in program obfuscation suggest that it is possible to create software that can provably safeguard secret information. However, software systems usually contain large executable code that is updated multiple times and sometimes very frequently. Freshly obfuscating the program for every small update will lead to a considerable efficiency loss. Thus, an extremely desirable property for obfuscation algorithms is {\em incrementality}: small changes to the underlying program translate into small changes to the corresponding obfuscated program.

We initiate a thorough investigation of {\em incremental program obfuscation}. We show that the strong simulation-based notions of program obfuscation, such as "virtual black-box" and "virtual grey-box" obfuscation, cannot be incremental even for very simple functions such as point functions. We then turn to the indistinguishability-based notions, and present two security definitions of varying strength. To understand the overall strength of our definitions, we formulate the notion of {\em incremental best-possible obfuscation} and show that it is equivalent to our (stronger) indistinguishability-based notion.

Finally, we present constructions for incremental program obfuscation satisfying both our security notions. We first give a construction achieving the weaker security notion based on the existence of general purpose indistinguishability obfuscation. Next, we present a generic transformation using {\em oblivious RAM} to amplify security from weaker to stronger, while maintaining the incrementality property.

Joint work with: Sanjam Garg

Garbled RAM, introduced by Lu and Ostrovsky in 2013, provides a novel method to garble RAM (Random Access Machine) programs directly. It can be seen as a RAM analogue of Yao's garbled circuits but achieves much more efficiency than first converting RAM programs into circuits. Secure RAM computation for two-parties is a key application of garbled RAM, but it is secure only against semi-honest adversaries. In this talk I will present LEGO for garbled RAM, a cut-and-choose technique for garbled RAM. This gives the first constant round two-party secure computation protocol for RAM programs secure against malicious adversaries that makes only black-box use of the underlying cryptographic primitives.

In a constrained pseudorandom function (PRF), the holder of the master secret key is able to derive constrained keys with respect to a boolean circuit C. The constrained key can be used to evaluate the PRF on all inputs x for which C(x) = 1. In almost all existing constructions of constrained PRFs, the constrained key itself reveals its underlying constraints. We introduce the concept of private constrained PRFs, which are constrained PRFs with the additional property that the constrained keys do not reveal their constraints. Our main notion of privacy captures the intuition that an adversary, given a constrained key for one of two circuits, is unable to tell which circuit is associated with its key. As a primitive, private constrained PRFs have many natural applications in searchable symmetric encryption, deniable encryption, and more. In this talk, I will introduce our notion of privacy for private constrained PRFs, and describe some of their applications. Finally, I will show how we can construct private constrained PRFs for different classes of constraints using indistinguishability obfuscation or concrete assumptions on multilinear maps.

Joint work with Dan Boneh and Kevin Lewi