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

Ran Canetti canetti at tau.ac.il
Thu Dec 1 00:20:21 EST 2011

It turns out that the Hariri Institute can provide free parking at the
Warren Towers parking structure, next door to the Institute. Enterance is
on the right, immediately after turning right into Hinsdale street from
Commonwealth Ave.

If you wish to use this option, please send an email to
charles.river.crypto.day at gmail.com by thursday night, with your name in the
subject line. (We need to give a list to the guard.)

Best,
Ran

On 11/29/2011 9:00 AM, Ran Canetti wrote:
>
> 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
> (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.
>
>
>
>