Summer 2015

Breaking News Sessions / Young Researcher Presentations

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

Add to Calendar


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

Breakout Session Track #1

Speaker: Andrew Miller, University of Maryland

Title: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies

Abstract:At this point, you will have seen at least four presentations on Bitcoin-related results. Out of necessity, you will have therefore heard at least one introduction-to-Bitcoin! So this talk will not introduce Bitcoin (For a self-contained introduction and survey on cryptocurrency research, see
our Systemization of Knowledge (SoK) paper [BMCNKF15]).

Instead, I’ll complement the earlier presentations with the following:

1. The Bitcoin user experience is public-key cryptography *made to come alive!* I will give each of you your very own "pet Bitcoin," in the form of a paper wallet. Paper wallets have a public key on the front, and a private key inside a folded paper seal.

2. In the spirit of SoK, I will briefly present a "map" that organizes and recaps the most recent cryptocurrency results (including ones you’ve heard over the past few days!) and reveals many open problems and interesting directions.

3. In particular: while the academic research so far has only modelled a single cryptocurrency in isolation, in actuality there are already hundreds of rival "altcoins" that coexist and compete. The cryptocurrency development "industry" has already invented many surprising techniques for these concurrent systems to either support each other or violently attack! I’ll tell a couple of short stories that motivate adding "multiple cryptocurrency" extensions to our models.

[BMCNKF15] SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, Edward W. Felten IEEE S&P 2015

Breakout Session Track #2

Speaker: Divya Gupta (UCLA)

Title: Secure Authentication and Communication with an Obfuscated Program: Hosting Services on an Untrusted Cloud

Abstract: We consider a scenario where a service provider has created a software service S and desires to outsource the execution of this service to an untrusted cloud. The software service contains secrets that the provider would like to keep hidden from the cloud. For example, the software might contain a secret database, and the service could allow users to make queries to different slices of this database depending on the user's identity.  

This setting presents significant challenges not present in previous works on outsourcing or secure computation.  Because secrets in the software itself must be protected against an adversary that has full control over the cloud that is executing this software, our notion implies indistinguishability obfuscation. Furthermore, we seek to protect knowledge of the software S to the maximum extent possible even if the cloud can collude with several corrupted users.

In this work, we provide the first formalizations of security for this setting, yielding our definition of a secure cloud service scheme. We provide constructions of secure cloud service schemes assuming indistinguishability obfuscation and non-interactive zero-knowledge proofs.

At the heart of our paper are novel techniques to allow parties to simultaneously authenticate and securely communicate with an obfuscated program, while hiding this authentication and communication from the entity in possession of the obfuscated program.

Joint work with Dan Boneh, Ilya Mironov and Amit Sahai

Breakout Session Track #3

Speaker: Antigoni Polychroniadou, Aarhus University

Title: Efficient Multi-Party Computation: from Passive to Active Security via Secure SIMD Circuits

Abstract: A central problem in cryptography is that of converting protocols that offer security against passive (or semi-honest) adversaries into ones that offer security against active (or malicious) adversaries. This problem has been the topic of a large body of work in the area of secure multiparty computation (MPC). Despite these efforts, there are still big efficiency gaps between the best protocols in these two settings. In two recent works, Genkin et al. (STOC 2014) and Ikarashi et al. (ePrint 2014) suggested the following new paradigm for efficiently transforming passive-secure MPC protocols into active-secure ones. They start by observing that in several natural information-theoretic MPC protocols, an arbitrary active attack on the protocol can be perfectly simulated in an ideal model that allows for additive attacks on the arithmetic circuit being evaluated. That is, the simulator is allowed to (blindly) modify the original circuit by adding a different field element to each wire. To protect against such attacks, the original circuit is replaced by a so-called AMD circuit, which can offer protection against such attacks with constant multiplicative overhead to the size.

Our motivating observation is that in the most efficient known information- theoretic MPC protocols, which are based on packed secret sharing, it is not the case that general attacks reduce to additive attacks. Instead, the corresponding ideal attack can include limited forms of linear combinations of wire values. We extend the AMD circuit methodology to so-called secure "SIMD circuits", which offer protection against this more general class of attacks.

We apply secure SIMD circuits to obtain several asymptotic and concrete efficiency improvements over the current state of the art. In particular, we improve the additive per-layer overhead of the current best protocols from O(n2) to O(n), where n is the number of parties, and obtain the first protocols based on packed secret sharing that "natively" achieve near- optimal security without incurring the high concrete cost of Bracha’s committee-based security amplification method.

Our analysis is based on a new modular framework for proving reductions from general attacks to algebraic attacks. This framework allows us to reprove previous results in a conceptually simpler and more unified way, as well as obtain our new results. 

Joint work with Daniel Genkin and Yuval Ishai