Jefferson's Wheel

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]

Yan Huang’s talk on Faster Secure Two-Party Computation Using Garbled Circuits at USENIX Security 2011 is now available: [PPTX] [PDF].

You can also download our framework and try our Android demo application.

University of Virginia people at USENIX Security in Union Square
San Francisco, 10 August 2011

Front row (left-to-right):

• Joseph Calandrino (UVa BS Math with CS 2004, UVa MCS 2005, soon to finish a PhD at Princeton).
• Erika Chin (UVa BSCS 2007, now a PhD student at UC Berkeley)
• Michael Dietz (UVa BSCS 2008, now a PhD student at Rice University)
• Jiamin Chen (finishing a UVa BACS in 2012, currently an undergraduate researcher on secure computation)
• Brittany Harris (finishing a UVa BACS in 2013, currently an undergraduate researcher on secure computation)
• Sang Koo (finishing UVa BSCS and BSCpE in 2013, currently an undergraduate researcher on mobile secure computation)
• Yuchen Zhou (currently PhD student in Computer Engineering at UVa, working on web security
• Yikan Chen (currently a PhD student in Computer Engineering at UVa, working on auditing information leakage)
• Pieter Hooimeijer (nearly finished PhD student at UVa, working in Westley Weimer’s group on programming languages and security)

Back row:

• Nate Paul (UVa PhD 2008, now at Associate Professor at the University of Tennessee, with a joint appointment at Oak Ridge National Labs)
• Nicholas Christin (UVa PhD 2003, now faculty at CMU Cylab)
• Adrienne Porter Felt (UVa BSCS 2008, now PhD student at UC Berkeley)
• Samee Zahur (currently a PhD student in Computer Science at UVa, working on improving secure computations using partial evaluation)
• Austin DeVinney (visiting researcher at UVa, completing a BSCS at Radford University in 2012)
• Yan Huang (currently a PhD student at UVa, working on secure computation)

UVa students book-ended the symposium, with Pieter presenting the first paper (Fast and Precise Sanitizer Analysis with BEK), and Yan presenting the last paper (Faster Secure Two-Party Computation Using Garbled Circuits). Adrienne Felt (Permission Re-Delegation: Attacks and Defenses and Michael Dietz (Quire: Lightweight Provenance for Smart Phone Operating Systems) also presented papers in a session that I was privileged to chair. Erika Chin, Joseph Calandrino, and Nicholas Christin were also co-authors of papers, and Austin, Brittany, Jiamin, Samee, Yan, and Yuchen also presented posters. Peter Chapman (BACS 2012) also presented a paper at HotSec, but wasn’t able to stay for the rest of the symposium.

Several of our students presented posters at the USENIX Security Symposium Poster Session.

Peter Chapman presented our paper on Privacy-Preserving Applications on Smartphones at the 6th USENIX Workshop on Hot Topics in Security today. Here are the talk slides [PDF].

The CommonContacts demonstration app is now available in the Android Market.

Project Website

Our paper on Privacy-Preserving Applications on Smartphones is now available:

Yan Huang, Peter Chapman, and David Evans. Privacy-Preserving Applications on Smartphones. 6th USENIX Workshop on Hot Topics in Security (HotSec 2011), San Francisco. 9 August 2011. [PDF, 6 pages]

Abstract: Smartphones are increasingly becoming the most trusted computing device typical people own. They are often used to store highly sensitive information including email, financial accounts, and medical records. These properties make smartphones an ideal platform for privacy-preserving applications. To date, this area remains largely unexplored mainly because theoretical solutions to privacy-preserving computation were thought to be too heavyweight, even for standard PCs. We propose using smartphones to perform secure two (or more)-party computation. The limitations of smartphones provide a number of challenges for building such applications, but the novel trust model they provide, in particular the interactions between the phones and carriers, provides unique opportunities for useful secure computations against realistic adversaries. In this paper, we introduce the issues that make smartphones a unique platform for secure computation, identify some interesting potential applications, and describe our initial experiences creating privacy-preserving applications on Android devices.

You can also try our out demo applications and download the secure computation framework used to build them.

Peter Chapman will present the paper at HotSec on August 9 in San Francisco.

Yan Huang presented Private Editing Using Untrusted Cloud Services at the Second International Workshop on Security and Privacy in Cloud Computing in Minneapolis this morning.

Here are the slides from his talk: [PPTX, PDF].
The full paper is also available: [PDF, 10 pages].

Our paper on protecting private web content from embedded scripts is now available:

Yuchen Zhou and David Evans. Protecting Private Web Content from Embedded Scripts. European Symposium on Research in Computer Security (ESORICS 2011). Lueven, Belguim. 12-14 September 2011. [PDF, 20 pages]

The paper addresses the problem of when web pages embed scripts from third parties (such as advertising networks or analytics tools) in their pages that contain user’s personal content. Since many such scripts must be embedded directly (that is, not in a separate iframe), they have access to the full page DOM and can access and manipulate this data. Our solution adopts the isolated worlds mechanism to isolate embedded scripts and provide a policy-limited access model. We also present a technique for automatically learning which nodes in a web page may contain sensitive data that should be protected from third-party scripts.

Yuchen will present the paper at ESORICS in Belgium in September.

Source Code

Modified Chromium: https://github.com/Treeeater/Chromium_on_windows

Policy Learner Proxy: https://github.com/Treeeater/GreasySpoon-proxy-script

Today, we are releasing our secure computation framework. Our Java-based framework and library enable programmers to build efficient and scalable privacy-preserving applications using Yao’s garbled circuit techniques.

This paper describes the framework in more detail:

Yan Huang, David Evans, Jonathan Katz, and Lior Malka. Faster Secure Two-Party Computation Using Garbled Circuits, 20th USENIX Security Symposium, San Francisco, CA. 8-12 August 2011. [PDF, 16 pages]

Abstract. Secure two-party computation enables two parties to evaluate a function cooperatively without revealing to either party anything beyond the function’s output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its inefficiency. We demonstrate several techniques for improving the running time and memory requirements of the garbled-circuit technique, resulting in an implementation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of circuits with over 10⁹ gates at a rate of roughly 10 microseconds per garbled gate, and showing order-of-magnitude improvements over the best previous privacy-preserving protocols for computing Hamming distance, Levenshtein distance, Smith-Waterman genome alignment, and AES.

The framework and applications are available under the MIT open source license: Download Fast Garbled Circuits Framework.

Yan Huang will present the paper at USENIX Security Symposium in San Francisco this August.

Yan Huang and Peter Chapman presented a poster and demo at Oakland 2011 conference on Secure Computation on Smartphones.