Talks
Summer 2015

# Breaking News Sessions / Young Researcher Presentations

Thursday, June 11th, 2015 2:00 pm2:30 pm

Speaker:

Multiple Speakers (Auditorium, Room 116 and the 2nd Floor Interaction Area)

Breakout Session Track #1

Speaker: Jeremiah Blocki, Carnegie-Mellon University

Title: Usable and Secure Human Authentication

This talk is based on joint work with Manuel Blum and Anupam Datta

Breakout Session Track #2

Speaker: Aloni Cohen (MIT)

Title: Publicly Verifiable Software Watermarking

Abstract: Software Watermarking is the process of transforming a program into a functionally equivalent watermarked  program in such a way that it is computationally hard to remove the mark without destroying functionality. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (CRYPTO 2001) defined software watermarking and showed that the existence of indistinguishability obfuscation implies that software watermarking is impossible. Given the recent candidate constructions of indistinguishability obfuscation, this result paints a bleak picture for the possibility of meaningful watermarking.

We show that slightly relaxing the functionality requirement gives us strong positive results for watermarking. Namely, instead of requiring the marked program to agree with the original unmarked program on all inputs, we require only that they agree on a large fraction of inputs.  With this relaxation in mind, our contributions are as follows.

1. We define publicly verifiable watermarking where marking a program requires a secret key, but anyone can verify that a program is marked. The handful of existing watermarking schemes are secretly verifiable, and moreover, satisfy only a weak definition where the adversary is restricted in the type of unmarked programs it is allowed to produce (Naccache, Shamir and Stern, PKC 1999; Nishimaki, EUROCRYPT 2013). Moreover, our definition requires security against chosen program attacks, where an adversary has access to an oracle that marks programs of her choice.

2. We construct a publicly verifiable watermarking scheme for any family of puncturable pseudo-random functions (PPRF), assuming indistinguishability obfuscation and injective one-way functions.  We also give an indication of the limits of watermarking by constructing "unwatermarkable" families of pseudorandom functions.

Joint work with Justin Holmgren and Vinod Vaikuntanathan.

Breakout Session Track #3

Speaker: Sunoo Park (MIT)

Title: On Time and Order in Multiparty Computation

Abstract:
The availability of vast amounts of data is changing how we can make medical discoveries, predict global market trends, save energy, improve our infrastructures, and develop new educational strategies. One obstacle to this revolution is the willingness of different entities to share their data with others.  The theory of secure multiparty computation (MPC) seemingly addresses this problem in the best way possible. Namely, parties learn the minimum necessary information: the value of the function computed on their joint data and nothing else. However, the theory of MPC does not deal with an important
aspect: {\it when} do different players receive their output? In time-sensitive applications, the timing and order of output discovery may be another important deciding factor in whether parties choose to share their data via the MPC.

In this work, we incorporate time and order of output delivery into the theory of MPC. We first extend classical MPC to \emph{ordered MPC} where different players receive their outputs according to an order which in itself is computed on the inputs to the protocol, and to refine the classical notions of guaranteed output delivery and fairness to require instead \emph{ordered output delivery} and \emph{prefix-fairness}. We then define {\it timed-delay MPCs} where explicit time delays are introduced into the output delivery schedule. We show general completeness theorems for ordered MPCs and timed-delay MPCs. We also introduce a new primitive called \emph{time-line puzzles}, which are a natural extension of classical timed-release crypto, in which multiple events can be serialized in time.

Next, we show how ordered MPC can give rise to MPCs which are provably worth'' joining, in competitive settings where relative time of output discovery may deter parties from joining the protocol. We formalize a model of collaboration and design a mechanism in which $n$ self-interested parties can decide, based on their inputs, on an ordering of output delivery and a distribution of outputs to be delivered in the mandated order. The mechanism guarantees a higher reward \emph{for all participants} when joining an ordered MPC or declares that such a guarantee is impossible to achieve. We show a polynomial time algorithm to compute the mechanism for a range of model settings.

Joint work with Pablo Azar and Shafi Goldwasser