Jefferson's Wheel

Our paper on secure stable matching is now available [PDF, 12 pages]:

Jack Doerner, David Evans, abhi shelat. Secure Stable Matching at Scale. 23^rd ACM Conference on Computer and Communications Security (CCS). Vienna, Austria. 24-28 October 2016.

See the OblivC.org site for the code and data. Jack Doerner will present the paper at CCS in October.

Abstract

When a group of individuals and organizations wish to compute a stable matching — for example, when medical students are matched to medical residency programs — they often outsource the computation to a trusted arbiter to preserve the privacy of participants’ preference rankings. Secure multi-party computation presents an alternative that offers the possibility of private matching processes that do not rely on any common trusted third party. However, stable matching algorithms are computationally intensive and involve complex data-dependent memory access patterns, so they have previously been considered infeasible for execution in a secure multiparty context on non-trivial inputs.

We adapt the classic Gale-Shapley algorithm for use in such a context, and show experimentally that our modifications yield a lower asymptotic complexity and more than an order of magnitude in practical cost improvement over previous techniques. Our main insights are to design new oblivious data structures that exploit the properties of the matching algorithms. We then apply our secure computation techniques to the instability chaining algorithm of Roth and Peranson, currently in use by the National Resident Matching Program. The resulting algorithm is efficient enough to be useful at the scale required for matching medical residents nationwide, taking just over 17 hours to complete an execution simulating the 2016 NRMP match with more than 35,000 participants and 30,000 residency slots.

Great to visit our former student Joseph Calandrino at the Federal Trade Commission in DC, where he is now a Research Director.

Denis Nekipelov and I gave a joint talk there about using secure multi-party computation techniques to enable data analyses across sensitive, divided data sets in the room where the FTC commissioners meet.

Denis Nekipelov, Joseph Calandrino, David Evans, Devesh Ravel

I’m co-organizing a workshop to be held in conjunction with NIPS on Private Multi‑Party Machine Learning, along with Borja Balle, Aurélien Bellet, Adrià Gascón. The one-day workshop will be held Dec 9 or Dec 10 in Barcelona.

NIPS workshops are different from typical workshops attached to computer security conferences, with lots of invited talks (and we have some great speakers lined up for PMPML16), but there is also an opportunity for researchers to submit short papers to be presented at the workshop either as short talks or posters.

Hannah Li presented a poster at USENIX Security Symposium on how popular web frameworks perform authentication.

Insecure by Default? Authentication Services in Popular Web Frameworks
[Abstract (PDF)] [Poster (PDF)]

The work studies how different design choices made by web frameworks impact the security of web applications built by typical developers using those frameworks, with a goal of understanding the usability and performance trade-offs that lead frameworks to adopt insecure defaults, and develop alternatives that lead to better security without sacrificing the needs of easy initial development and deployment.

Kevin Zhao is working on building an open source “Amazon echo” personal voice assistant (using Jasper).

His first post about it is here: Building The Open Source Amazon Echo-Jasper.

I went to Shanghai for the ShanghaiTech Symposium on Information Science and Technology. ShanghaiTech was only founded three years ago, but has made tremendous progress and recruited a talented group of faculty and students.

Zheng Zhang and Haibo Chen

Hao Bai

For the Symposium, I presented a tutorial introduction to secure multi-party computation (focused towards systems researchers), and an invited talk on Memory for Data-Oblivious Computation. Was a special honor to be able to speak about MPC applications build using Yao’s protocol following Andrew Yao’s opening keynote.

Thanks a bunch to Hao Chen for inviting me to the Symposium!

I’m back from the Workshop on Theory and Practice of Secure Multiparty Computation are Aarhus University in Denmark. Aarhus is a great city for biking – you can rent bikes (with trailers for children), and bike down the coast from the old city, past the beach, and to the countryside, all on a bikes-only roadway.

Highlight of the workshop was unquestionably the musical performance by Ivan Damgård, Claudio Orlandi, and Marcel Keller:

I gave a talk on circuit structures and Square-Root ORAM:

abhi shelat also presented on Jack Doerner’s work on private stable matching.

After the workshop, we had a family visit to Legoland (about an hour by train and bus from Aarhus). Photo albums: Aarhus, Legoland.

At the IEEE Symposium on Security and Privacy in San Jose, CA, Samee Zahur presented on Square-Root ORAM and Anant, Jack, and Sam presented posters.

Anant Kharkar Evading Web Malware Classifiers using Genetic Programming

Jack Doerner Secure Gale-Shapley: Efficient Stable Matching for Multi-Party Computation

Samuel Havron Secure Multi-Party Computation as a Tool for Privacy-Preserving Data Analysis

I presented two tutorials on oblivious computation at Notre Dame’s Summer School on Secure and Oblivious Computation and Outsourcing. SRG PhD Yan Huang, now at Indiana University, was one of the other tutorial presenters. I also learned a lot about verifiable computation and argument systems from Justin Thaler. Thanks to Marina Blanton for organizing a great summer school!

Slides for my tutorials on garbling techniques and memory for data oblivious computation are below.

Top row: Anant Kharkar, Glenn Field, Ethan Robertson, David Evans, Hao Bai (BSCS 2016), Wenjiang Fan (honorary), Mohammad Etemad, Samee Zahur (PhD 2016), Jack Doerner, Weilin Xu, Longze Chen (MCS 2015), Kevin Zhao.
Front row: Mahnush Movahedi, Ziqi Liu (BACS DMP 2016), Hannah Li

Congratulations to our 2016 SRG Graduates:

Dr. Samee Zahur, PhD 2016
Dissertation: Demystifying Secure Computation: Familiar Abstractions for Efficient Protocols
Dr. Zahur will be joining Google, and working in the group that works on secure computation (broadly) led by SRG alumnus Jonathan McCune.

Hao Bai, BSCS 2016
Thesis project: Mitigating Memory Trace Side-Channels through Cache Loading
Hao will be starting graduate school at Harvard University in the fall.

Ziqi Liu, Distinguished Major with High Distinction in Computer Science (BACS) 2016
DMP project: A Proxy for Mitigating Threats from Embedded Third-party Scripts
Ziqi will be joining Microsoft (Redmond).