@inproceedings{ZHKS16,
 title = {The Cut-and-Choose Game and its Application to Cryptographic Protocols},
 author = {Ruiyu Zhu, Yan Huang, Jonathan Katz, abhi shelat},
 booktitle = {USENIX Security 2016},
 year = {2016},
}

PDF

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 a ``cut-and-choose game’’ and show optimal strategies for the parties in this game. 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–258% in terms of total time.