[Busec] This Friday, Dec 2: The First Charles River Crypto day

Ran Canetti canetti at tau.ac.il
Tue Nov 29 09:00:44 EST 2011

Dear All - This is a reminder that the first Charles River Crypto Day will be
held at Boston University this Friday, December 2, 2011. The program 
appears below.
The event is open to the public. Please circulate!

Shafi, Yael, Ran

Program: (See abstracts below)

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 

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

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


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 

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.

More information about the Busec mailing list