Jefferson's Wheel

I gave a talk today at the University of Richmond on secure computation, targeted to a general audience. [Richmond Abstract Page]

Two-party secure computation allows two parties to compute a function that depends on inputs from both parties, but reveals nothing except the output of the function. A general solution to this problem have been known since Andrew Yao’s pioneering work on garbled circuits in the 1980s, but only recently has it become conceivable to use this approach in real systems. This talk will provide an introduction to secure computation, and describe the work we are doing at UVa to make secure computation efficient and scalable enough to build real applications. The talk assumes no prior background in cryptography, and should be understandable all computing students.

Slides: [PDF] [PPTX]

For more, see: MightBeEvil.com

I gave a keynote talk on our secure computation work at the Seventh International Conference on Information Systems Security (ICISS) in Jadavpur University, Kolkata, India. 17 December 2011.

More Photos

Talk Slides: [PPTX] [PDF]

Our paper on using generic garbled circuits to perform private set intersection is now available:

The paper develops three circuit designs for securely computing the intersection of two sets, where each set is the private input from one protocol participant. We show that for many scenarios, protocols built using only generic garbled circuit secure computation techniques can be competitive with the best custom-designed protocols for private set intersection.

Yan Huang will present the paper at NDSS in San Diego, in February 2012.

Our paper on Efficient Secure Computation with Garbled Circuits (by Yan Huang, Chih-hao Shen, David Evans, Jonathan Katz, and abhi shelat) is now available (Abstract, Paper [PDF, 21 pages]).

The paper is connected with a keynote talk I will give at the Seventh International Conference on Information Systems Security (ICISS 2011) in Kolkata (previously known as Calcutta), India on 17 December 2011.

Abstract. Secure two-party computation enables applications in which participants compute the output of a function that depends on their private inputs, without revealing those inputs or relying on any trusted third party. In this paper, we show the potential of building privacy-preserving applications using garbled circuits, a generic technique that until recently was believed to be too inefficient to scale to realistic problems. We present a Java-based framework that uses pipelining and circuit-level optimizations to build efficient and scalable privacy-preserving applications. Although the standard garbled circuit protocol assumes a very week, honest-but-curious adversary, techniques are available for converting such protocols to resist stronger adversaries, including fully malicious adversaries. We summarize approaches to producing malicious-resistant secure computations that reduce the costs of transforming a protocol to be secure against stronger adversaries. In addition, we summarize results on ensuring fairness, the property that either both parties receive the result or neither party does. Several open problems remain, but as theory and pragmatism advance, secure computation is approaching the point where it offers practical solutions for a wide variety of important problems.

Yan Huang has been selected as a finalist for the NYU-Poly AT&T Best Applied Security Paper Award for the paper, Faster Secure Two-Party Computation Using Garbled Circuits (USENIX Security 2011, co-authored with David Evans, Jonathan Katz, and Lior Malka). The award recognizes the best paper on applied security in any venue between September 1, 2010 and August 31, 2011.

The award will be announced at a ceremony as part of the CSAW Cybersecurity Competition in New York on 11 November.

UVa Today has a story about our secure computation project: U.Va. Team Awarded $3 Million NSF Secure Computation Grant, Fariss Samarrai, UVa Today, 14 October 2011.

Photo: Cole Geddy

“Secure computation is the idea that you can have two people compute a function that depends on things that each one knows individually and wants to keep private without exposing their private data to the other person, or to anyone else,” Evans said.

The research has applications in everyday life, from private medical information, such as personal genomics, to privacy-preserving face recognition and electronic commerce.

As a simple example of how it works, consider two people who each have smartphones with personal address books. They would like to know if they know any of the same people by comparing their address books. But, they may not want to share their address books, which include potentially sensitive private information. So how can they find the common entries, without revealing anything about their other contacts?

Read More …

Yikan Chen presented his work on Auditing Information Leakage for Distance Metrics at the Third IEEE Conference on Privacy, Security, Risk and Trust today.

The slides are here: [PPTX] [PDF]

Here are the slides from my talk in cs6190, our seminar for new graduate students: [PPTX] [PDF]

Links from the talk:

• http://www.mightbeevil.com — secure computation with garbled circuits
• CommonContacts Android Secure Computation Demo
• Research group mailing list
• Publications

Today (August 30th) we are hosting the Kickoff Meeting for our new NSF-funded 5-year project, Practical Secure Two-Party Computation: Techniques, Tools, and Applications. This is a collaborative research project with abhi shelat and Aaron Mackey at UVa, Michael Hicks and Jonathan Katz at the University of Maryland, and Steven Myers at Indiana University. The goal of the project is to make privacy-preserving computation practical and accessible enough to be used routinely in applications such as personalized genetics, medical research, and privacy-preserving biometrics. For more, see http://securecomputation.org.

Yikan Chen and I are releasing a paper today on Auditing Information Leakage for Distance Metrics. The paper is a first step towards the goal of developing self-auditing secure computations that can determine when the output of a secure computation would leak too much information to be safe to release. Yikan will present the paper at the Third IEEE Conference on Privacy, Security, Risk and Trust in Boston, 9-11 October 2011.

Abstract. Many useful scenarios involve allowing untrusted users to run queries against secret data, so long as the results do not leak too much information. This problem has been studied widely for statistical queries, but not for queries with more direct semantics. In this paper, we consider the problem of auditing queries where the result is a distance metric between the query input and some secret data. We develop an efficient technique for estimating a lower bound on the entropy remaining after a series of query-responses that applies to a class of distance functions including Hamming distance. We also present a technique for ensuring that no individual bits of the secret sequence is leaked. In this paper, we formalize the information leakage problem, describe our design for a query auditor, and report on experiments showing the feasibility and effectiveness of our approach for sensitive sequences up to thousands of bits.

Full paper: [PDF, 10 pages]