Archive for the 'Secure Computation' Category

Growth of MPC Research

Friday, January 13th, 2017

I led a discussion breakout at the NSF SaTC PIs meeting on Secure Computation: Progress, Methods, Challenges, and Open Questions. To set up the session, I looked at the number of papers in Google scholar that match "secure computation" OR "multi-party computation" (which seems like a fairly good measure of research activity in the area):

There were 1800 MPC papers published in 2015! This means in one year, there are most papers published on MPC than there were from the beginning of time through the end of 2004. Gotta get reading…

Aggregating Private Sparse Learning Models Using Multi-Party Computation

Friday, December 9th, 2016

Bargav Jayaraman presented on privacy-preserving sparse learning at the Private Multi‑Party Machine Learning workshop attached to NIPS 2016 in Barcelona.



A short paper summarizing the work is: Lu Tian, Bargav Jayaraman, Quanquan Gu, and David Evans. Aggregating Private Sparse Learning Models Using Multi-Party Computation [PDF, 6 pages].

At the workshop, Jack Doerner also presented a talk on An Introduction to Practical Multiparty Computation.

Secure Stable Matching at Scale

Tuesday, August 30th, 2016

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

Jack Doerner, David Evans, abhi shelat. Secure Stable Matching at Scale. 23rd 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.

FTC Visit

Thursday, August 18th, 2016

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

ShanghaiTech Symposium

Saturday, June 25th, 2016

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!

Aarhus Workshop on Theory and Practice of Secure Multiparty Computation

Sunday, June 5th, 2016

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.

SRG at Oakland 2016

Wednesday, May 25th, 2016

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

Summer School at Notre Dame

Friday, May 13th, 2016

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.




CROSSING

Friday, June 5th, 2015

I went to a very interesting meeting at Darmstadt: CROSSING – Where Quantum Physics, Cryptography, System Security and Software Engineering meet. Lots more diversity than my typical computer security meeting, including a lively debate on quantum physics and superfluid vacuum theory between Nicolas Grisin (founder of ID Quantique and Ross Anderson. Interesting to learn that China is building a huge quantum key distribution network.

I gave a talk on Multi-Party Computation for the Masses:



CROSSING is a 12-year project funded by the German Science Foundation (with reviews every 4 years). Gives some context to US funding agencies that talk about long-range visionary projects with 5-year timelines.

SRG at Oakland 2015

Sunday, May 24th, 2015

Several SRGers were at IEEE Symposium on Security and Privacy (“Oakland” in San Jose).

Yuchen Zhou presented his work on Understanding and Monitoring Embedded Web Scripts. Yuchen graduated with his PhD the day before the conference, and will be joining Palo Alto Networks.

Samee Zahur is a co-author (along with Benjamin Kreuter, who is an “in-progress UVa PhD student” diverted by Google, and several researchers from Microsoft Research) on the paper, Geppetto: Versatile Verifiable Computation, which was presented by Bryan Parno.

Samee also presented a poster on Obliv-C.

Weilin Xu presented a poster on Automatically Evading Classifiers

It was also great to see SRG alums Yan Huang (who is not at Indiana University, and was a co-author on the paper about ObliVM), Jon McCune (who is now working on trusted computing at Google) and Adrienne Felt (who was the keynote speaker for the W2SP workshop, and gave a very interesting talk about user-facing security design and experiments in Google Chrome; Adrienne’s first paper was in W2SP 2008 when she was an undergraduate at UVa).