The Cut-and-Choose Game and Its Application to Cryptographic Protocols
summary
Claims that cut-and-choose parameter selection is a constrained optimization problem and gives equilibrium analyses and practical solvers; models differing costs of checking vs. evaluating, represents evaluator choices as a distribution x_i over how many of n circuits are checked, and enforces security as a bound ε on failure. Produces a linear-time greedy solver for the single-cut LP, plus game solvers on github, and demonstrates up to an order-of-magnitude bandwidth reduction and 12–106% runtime improvements (20–80% for single-cut, ~25–90% for majority, smaller gains for batch).
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:31What is Cut-and-Choose
- 2:24Applications of Cut-and-Choose
- 3:15Three Flavors of Cut-and-choose
- 4:57Existing SingleCut Strategy
- 6:55Our Key Intuition
- 7:49Problem Formulation
- 10:22Expected Cost of SingleCut
- 13:08Recap
- 13:30Fractional knapsack Problem
- 14:04Find the Best n
- 15:07Sample SingleCut Strategy for AES n = 2267
- 16:07Improvements on SingleCut
- 17:01Sample MajorityCut Strategy
- 18:08Improvements on MajorityCut
- 19:11Conclusion
related talks
54mFine-Grained Cryptography
38mAdvisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
33mGeometry of Secure Computation
32mSymmetric Cryptanalysis I
41mSpotlight Talks
19mCryptOpt: Verified Compilation with Randomized Program Search for Cryptographic Primitives
01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic
01h 08mCryptography from Ideal Lattices