Skip to main content
USENIX
  • Conferences
  • Students
Sign in
  • Overview
  • Symposium Organizers
  • At a Glance
  • Registration Information
    • Registration Discounts
    • Venue, Hotel, and Travel
  • Technical Sessions
  • Co-Located Workshops
  • Accepted Posters
  • Activities
    • Birds-of-a-Feather Sessions
    • Work-in-Progress Reports
  • Sponsorship
  • Students and Grants
  • Services
  • Questions?
  • Help Promote!
  • Flyer PDF
  • For Participants
  • Call for Papers
  • Past Symposia

sponsors

Gold Sponsor
Gold Sponsor
Gold Sponsor
Silver Sponsor
Bronze Sponsor
Bronze Sponsor
Bronze Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Industry Partner

twitter

Tweets by USENIXSecurity

usenix conference policies

  • Event Code of Conduct
  • Conference Network Policy
  • Statement on Environmental Responsibility Policy

You are here

Home » TRUESET: Faster Verifiable Set Computations
Tweet

connect with us

http://twitter.com/usenixsecurity
https://www.facebook.com/usenixassociation
http://www.linkedin.com/groups/USENIX-Association-49559/about
https://plus.google.com/108588319090208187909/posts
http://www.youtube.com/user/USENIXAssociation

TRUESET: Faster Verifiable Set Computations

Friday, July 25, 2014 - 5:15pm
Authors: 

Ahmed E. Kosba, University of Maryland; Dimitrios Papadopoulos, Boston University; Charalampos Papamanthou, Mahmoud F. Sayed, and Elaine Shi, University of Maryland; Nikos Triandopoulos, RSA Laboratories and Boston University

Abstract: 

Verifiable computation (VC) enables thin clients to efficiently verify the computational results produced by a powerful server. Although VC was initially considered to be mainly of theoretical interest, over the last two years impressive progress has been made on implementing VC. Specifically, we now have open-source implementations of VC systems that handle all classes of computations expressed either as circuits or in the RAM model. Despite this very encouraging progress, new enhancements in the design and implementation of VC protocols are required to achieve truly practical VC for real-world applications.

In this work, we show that for functions that can be expressed efficiently in terms of set operations (e.g., a subset of SQL queries) VC can be enhanced to become drastically more practical: We present the design and prototype implementation of a novel VC scheme that achieves orders of magnitude speed-up in comparison with the state of the art. Specifically, we build and evaluate TRUESET, a system that can verifiably compute any polynomial-time function expressed as a circuit consisting of “set gates” such as union, intersection, difference and set cardinality. Moreover, TRUESET supports hybrid circuits consisting of both set gates and traditional arithmetic gates. Therefore, it does not lose any of the expressiveness of previous schemes—this also allows the user to choose the most efficient way to represent different parts of a computation. By expressing set computations as polynomial operations and introducing a novel Quadratic Polynomial Program technique, our experiments show that TRUESET achieves prover performance speed-up ranging from 30x to 150x and up to 97% evaluation key size reduction compared to the state-of-the-art.

Ahmed E. Kosba, University of Maryland

Dimitrios Papadopoulos, Boston University

Charalampos Papamanthou, University of Maryland

Mahmoud F. Sayed, University of Maryland

Elaine Shi, University of Maryland, College Park

Nikos Triandopoulos, RSA Laboratories and Boston University

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {184499,
author = {Ahmed E. Kosba and Dimitrios Papadopoulos and Charalampos Papamanthou and Mahmoud F. Sayed and Elaine Shi and Nikos Triandopoulos},
title = {{TRUESET}: Faster {Verifiable} Set Computations},
booktitle = {23rd USENIX Security Symposium (USENIX Security 14)},
year = {2014},
isbn = {978-1-931971-15-7},
address = {San Diego, CA},
pages = {765--780},
url = {https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/kosba},
publisher = {USENIX Association},
month = aug
}
Download
Kosba PDF
View the slides

Presentation Video 

Presentation Audio

MP3 Download

Download Audio

  • Log in or    Register to post comments

Gold Sponsors

Silver Sponsors

Bronze Sponsors

Media Sponsors & Industry Partners

© USENIX

  • Privacy Policy
  • Contact Us