The First Charles River Crypto day

Program

9:30-10:00 Gathering and breakfast
10:00-11:00 Vinod Vikunthanatan, U of Totonto: Computing Blindfolded: New Developments in Fully Homomorphic Encryption
11:30-12:30 Rafael Pass, Cornell U: An Epistemic Approach to Mechanism Design
12:30-13:30 Lunch (provided)
13:30-14:30 Tal Malkin, Columbia U: Secure Computation with Sub-linear Amortized Work
14:45-15:45 Guy Rothblum, Microsoft Research: How to compute in the presence of leakage

Location

The event will take place at the Hariri institute, located at the east end of the Computer Science building at BU (111 Cummington st., Boston, MA.) There is metered parking on Commington st. The nearest public parking lot is the Granby Lot, across Comm Ave at 665 Commonwealth Ave (http://www.bu.edu/maps/?id=2307)

We wish to thank BU’s Rafik B. Hariri Institute for Computing and Computational Science & Engineering, as well as the Center for Reliable Information Systems and Cyber Security (RISCS) for making this event possible via generous support.

Organizers

Shafi Goldwasser (MIT), Yael Kalai (MSR), Ran Canetti (BU)

Abstracts

Computing Blindfolded: New Developments in Fully Homomorphic Encryption

Vinod Vikunthanatan, U of Totonto

Is it possible to delegate arbitrarily complex computation on data without giving away access to the data? This problem — called “fully homomorphic encryption” — has long been regarded as cryptography’s prized holy grail, and calls for the ability to compute on encrypted data without decrypting it and without knowing any secret keys.

We will present a new notion of fully homomorphic encryption (FHE) that we call a multi-key FHE that permits computation on data encrypted under multiple unrelated keys, a new construction of multi-key FHE based on the NTRU encryption scheme, and a new application of multi-key FHE to the problem of constructing minimally interactive MPC protocols in the presence of a cloud.

Joint Work with Adriana Lopez-Alt (NYU) and Eran Tromer (Tel-Aviv U).

An Epistemic Approach to Mechanism Design

Rafael Pass, Cornell U

We introduce an epistemic framework for analyzing mechanisms. This framework enables mechanism designers to define desirability of outcomes not only based on players’ actual payoff types and their beliefs about the payoff types of other players (as in the classic models), but also based on higher order beliefs of the players (i.e., beliefs about beliefs about Š the payoff types of the players). In this framework, we may also use epistemic solution concepts to analyze what outcomes are consistent with different levels of rationality: a player is k-level rational if he is rational and considers all other players (k-1)-level rational; following Aumann, we consider a very weak notion of rationality: player i is *rational* if he uses a strategy \sigma such that for every alternative strategy \sigma’, i considers some world possible where \sigma performs at least as well as \sigma’.

We showcase this framework in the context of single-good auctions, presenting an interim individually-rational mechanism with the following revenue guarantee: for any k\geq 0, any outcome consistent with all players being (k+1)-level rational guarantees the seller a revenue of G^k

– \epsilon (for any \epsilon > 0), where G^k is the second highest belief about belief about Š (k times) about the highest valuation of some player.

We additionally show that no interim individually rational mechanism can guarantee a revenue of G^k – \epsilon for any constant \epsilon, if only assuming players are k-level rational (as opposed to (k+1)-level rational). Taken together, these results demonstrate the existence of a “revenue-rationality hierarchy”: strictly higher revenue may be extracted by assuming players satisfy higher levels of rationality.

Towards analyzing our mechanism and proving our lower bounds, we introduce an iterative deletion procedure of dominated strategies which precisely characterizes strategies consistent with k-level rationality.

Joint work with Jing Chen and Silvio Micali

Secure Computation with Sublinear Amortized Work

Tal Malkin, Columbia U

Abstract: Traditional approaches to secure computation begin by representing the function f being computed as a circuit. For any function f that depends on each of its inputs, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for secure computation of non-trivial functions, since each party must “touch” every bit of their input lest information about other party’s input be leaked. This seems to rule out many interesting applications of secure computation in scenarios where at least one of the inputs is huge and sublinear-time algorithms can be utilized in the insecure setting; private database search is a prime example.

We present an approach to secure two-party computation that yields sublinear-time protocols, in an amortized sense, for functions that can be computed in sublinear time on a random access machine~(RAM). Furthermore, a party whose input is “small” is required to maintain only small state. We provide a generic protocol that achieves the claimed complexity, based on any oblivious RAM and any protocol for secure two-party computation. We then present an optimized version of this protocol, where generic secure two-party computation is used only for evaluating a small number of simple operations.

Joint work with Dov Gordon, Jonathan Katz, Vlad Kolesnikov, Mariana Raykova, and Yevgeniy Vahlis

How to compute in the presence of leakage

Guy Rothblum, Microsoft Research

We address the following problem: how to execute any algorithm P, for an unbounded number of executions, in the presence of an attacker who gets to observe partial information on the internal state of the computation during executions.

This general problem has been addressed in the last few years with varying degrees of success. It is important for running cryptographic algorithms in the presence of side-channel attacks, as well as for running non-cryptographic algorithms, such as a proprietary search algorithm or a game, on a cloud server where parts of the execution’s internals might be observed.

Our main result is a general compiler for transforming any algorithm into one that is secure in the presence of a rich family of partial observation attacks (and computes the same functionality). This result is unconditional, it does not rely on any secure hardware components or cryptographic assumptions.