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

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 a paper to be presented at USENIX Security 2016, 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.

Paper: Ruiyu Zhu, Yan Huang, Jonathan Katz, and abhi shelat. The Cut-and-Choose Game and its Application to Cryptographic Protocols. USENIX Security Symposium, 2016.

Source code of our game solvers: