On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC

Johannes Blömer; Jan Bobolz; Henrik Bröcher

Paper 2022/1762

On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC

Johannes Blömer

, Paderborn University

Jan Bobolz

, University of Edinburgh, Paderborn University

Henrik Bröcher

, Paderborn University

Abstract

Rational multiparty computation (rational MPC) provides a framework for analyzing MPC protocols through the lens of game theory. One way to judge whether an MPC protocol is rational is through weak domination: Rational players would not adhere to an MPC protocol if deviating never decreases their utility, but sometimes increases it. Secret reconstruction protocols are of particular importance in this setting because they represent the last phase of most (rational) MPC protocols. We show that most secret reconstruction protocols from the literature are not, in fact, stable with respect to weak domination. Furthermore, we formally prove that (under certain assumptions) it is impossible to design a secret reconstruction protocol which is a Nash equlibrium but not weakly dominated if (1) shares are authenticated or (2) half of all players may form a coalition.

Note: This article is the full version of an article with the same name which appeared at TCC 2023.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in TCC 2023
Keywords: Game Theory Rational Secret Sharing Multiparty Computation Rational Cryptography Weakly Dominated Strategies
Contact author(s): bloemer @ uni-paderborn de
jan bobolz @ ed ac uk
henrik broecher @ uni-paderborn de
History: 2023-10-18: revised; 2022-12-23: received; See all versions
Short URL: https://ia.cr/2022/1762
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1762,
      author = {Johannes Blömer and Jan Bobolz and Henrik Bröcher},
      title = {On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational {MPC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1762},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1762}
}