Summer 2015

Breaking News Sessions / Young Researcher Presentations

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

Add to Calendar


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

Abstract: A typical computer user today manages passwords for many different online accounts. Users struggle with this task ---often forgetting their passwords or adopting insecure practices, such as using the same passwords for multiple accounts and selecting weak passwords. Before we can design good password management schemes it is necessary to address a fundamental question: How can we quantify the usability or security of a password management scheme? In this talk we will introduce quantitative usability and security models. Notably, our user model, which is based on research on human memory about spaced rehearsal, allows us to analyze the usability of a large family of password management schemes while experimentally validating only the common user model underlying all of them. We argue that these quantitative models can guide the development of usable and secure password management schemes. In support of our argument we present Shared Cues, a simple password management scheme in which the user can generate many strong passwords after memorizing a few randomly generated stories. Our password management schemes are precisely specified and publishable: the security proofs hold even if the adversary knows the scheme and has extensive background knowledge about the user (hobbies, birthdate, etc.).

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

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