Paper 2017/174

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

Ruiyu Zhu and Yan Huang

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Cut-and-choose gamesAlgorithmic game theoryUnequal-cost Huffman codesActively-secure two-party computation
Contact author(s)
yhuang @ cs umd edu
History
2017-02-27: received
Short URL
https://ia.cr/2017/174
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/174,
      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{https://eprint.iacr.org/2017/174}},
      url = {https://eprint.iacr.org/2017/174}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.