Skip to main content
USENIX
  • Conferences
  • Students
Sign in
  • Home
  • Attend
    • Registration Information
    • Registration Discounts
    • Venue, Hotel, and Travel
    • Students and Grants
    • Co-located Workshops
  • Program
    • At a Glance
    • Technical Sessions
  • Activities
    • Birds-of-a-Feather Sessions
    • Poster Session
    • Work-in-Progress Reports (WiPs)
  • Sponsorship
  • Participate
    • Instructions for Authors and Speakers
    • Call for Papers
      • Important Dates
      • Symposium Organizers
      • Symposium Topics
      • Refereed Papers
      • Symposium Activities
      • Submitting Papers
  • About
    • Symposium Organizers
    • Questions
    • Services
    • Help Promote
    • Past Symposia
  • Home
  • Attend
  • Program
  • Activities
  • Sponsorship
  • Participate
  • About

sponsors

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

help promote

USENIX Security '16 button

Get more
Help Promote graphics!

connect with usenix


  •  Twitter
  •  Facebook
  •  LinkedIn
  •  Google+
  •  YouTube

twitter

Tweets by USENIXSecurity

usenix conference policies

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

You are here

Home » The Cut-and-Choose Game and Its Application to Cryptographic Protocols
Tweet

connect with us

The Cut-and-Choose Game and Its Application to Cryptographic Protocols

Authors: 

Ruiyu Zhu and Yan Huang, Indiana University; Jonathan Katz, University of Maryland; Abhi Shelat, Northeastern University

Abstract: 

The cut-and-choose technique plays a fundamental role in cryptographic-protocol design, especially for secure two-party computation in the malicious model. The basic idea is that one party constructs n versions of a message in a protocol (e.g., garbled circuits); the other party randomly checks some of them and uses the rest of them in the protocol. Most existing uses of cut-and-choose fix in advance the number of objects to be checked and in optimizing this parameter they fail to recognize the fact that checking and evaluating may have dramatically different costs.

In this paper, we consider a refined cost model and formalize the cut-and-choose parameter selection problem as a constrained optimization problem. We analyze “cut-and-choose games” and show equilibrium strategies for the parties in these games. We then show how our methodology can be applied to improve the efficiency of three representative categories of secure-computation protocols based on cut-and-choose. We show improvements of up to an-order-of-magnitude in terms of bandwidth, and 12–106% in terms of total time. Source code of our game solvers is available to download at https://github.com/cut-n-choose.

Ruiyu Zhu, Indiana University

Yan Huang, Indiana University

Jonathan Katz, University of Maryland

Abhi Shelat, Northeastern 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 {197265,
author = {Ruiyu Zhu and Yan Huang and Jonathan Katz and Abhi Shelat},
title = {The {Cut-and-Choose} Game and Its Application to Cryptographic Protocols},
booktitle = {25th USENIX Security Symposium (USENIX Security 16)},
year = {2016},
isbn = {978-1-931971-32-4},
address = {Austin, TX},
pages = {1085--1100},
url = {https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/zhu},
publisher = {USENIX Association},
month = aug,
}
Download
Zhu PDF
View the slides

Presentation Video 

Presentation Audio

MP3 Download

Download Audio

  • Log in or    Register to post comments

Platinum Sponsors

Gold Sponsors

Silver Sponsors

Bronze Sponsors

Media Sponsors & Industry Partners

© USENIX

  • Privacy Policy
  • Contact Us