Paper 2017/174

Cost-Aware Cut-and-Choose Games with Applications in Cryptography and Prefix-Free Codes

Ruiyu Zhu and Yan Huang


Cost-aware cut-and-choose game is a fundamental technique that has many cryptographic applications. Best existing solutions of this game assumed for simplicity that the number of challenges is publicly known. This paper considers an extension of this game where the number of challenges can be picked probabilistically and hidden to the adversary. Although this small change leads to a linear program with infinitely many variables and constraints, we discover a surprising efficiency solver — using only O(n2) space and O(n2) time where n is the upper-bound on the number of challenges allowed in the strategy space. We then prove that n is bounded for any fixed cost ratio, implying the optimality of our solution extends to the strategy space that allow any number of challenges. As two interesting applications of our game solver, we demonstrate its value in constructing an actively secure two-party computation protocol and an optimal prefix-free code for encryptions.

Available format(s)
Publication info
Preprint. MINOR revision.
Cut-and-choose gamesAlgorithmic game theoryUnequal-cost Huffman codesActively-secure two-party computation
Contact author(s)
yhuang @ cs umd edu
2017-02-27: received
Short URL
Creative Commons Attribution


      author = {Ruiyu Zhu and Yan Huang},
      title = {Cost-Aware Cut-and-Choose Games with Applications in Cryptography and Prefix-Free Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/174},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.