Secure Computation
on Smartphones

Secure two-party computation has been an interesting theoretical concept for decades, but until recently has been considered too expensive for practical applications. With significant advances in the design and implementation of secure protocols, secure computation is becoming feasible in practice. However, with the notable exceptions of biometric identification and secure auctions, the research community has historically struggled to find realistic and useful applications for secure computation. In this work, we explore new opportunities implementing secure computing applications on rapidly evolving mobile computing platforms. Through a series of Android applications, we demonstrate the feasibility and power of secure computation protocols in this new domain.

Applications

CommonContacts

The CommonContacts app allows two people to discover that mutual contacts while protecting the rest of their contact list. Since the state space for this application is large (10¹⁰ for phone numbers and even greater for email addresses) we use an efficient private set intersection scheme that we developed that we have dubbed Sort-Compare-Shuffle (SCS). At the end of the protocol, both devices display the matching contacts.

To install visit our Android Market page. Or, install from our site (your device must be set up to allow applications from unknown sources) by downloading CommonContacts.apk or scanning this barcode:

FavoritePapers

The FavoritePapers apps allows two users to see what papers they both liked, without revealing the unshared selections. Since the element space of the intersection is small, we use a bit-vector-AND-based scheme to perform the comparison. Each "liked" paper is represented as a 1 in the bit-vector. We AND the two bit-vectors together to generate the desired output. For larger element spaces (e.g., > 2²⁰), the AND-based scheme is impractical as the vector grows exponentially in the number of bits used to denote the input, but for small input spaces like this one it is very efficient.

To install, download FavoritePapers.apk or scan this barcode:

Paper

This paper describes our vision for privacy-preserving applications on smartphones:

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]

Talk

Peter Chapman's talk at 6th USENIX Workshop on Hot Topics in Security (HotSec 2011), San Francisco. 9 August 2011: Slides: [PDF], Videos: Presentation, Panel Q & A

Software

The secure computation framework used to build these applications is described in this paper:

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]

Posters

Oakland 2011 Poster Proposal: [PDF]
Oakland 2011 Poster: [PDF, 3MB]

Photo by Thomas Baldwin

People

Peter Chapman (University of Virginia)
David Evans (University of Virginia)
Yan Huang (University of Virginia)
Sang Koo (University of Virginia)

Funding. This work was supported in part by grants from the Air Force Office of Scientific Research (MURI), National Science Foundation, and DARPA. We thank Google for providing Nexus One phones.