An application of game theoretic techniques to cryptography
Michael Fischer, Rebecca N. Wright · DIMACS series in discrete mathematics and theoretical computer science · 1993
This paper provides an application of game theoretic techniques to the analysis of a class of multiparty cryptographic protocols for secret bit exchange. 1 Introduction A cryptographic protocol is often thought of as a game between the honest participants in the protocol and a malicious adversary who tries to corrupt the protocol. In this paper, we consider a simple combinatorial game that arises in the analysis of the class of multiparty "key set" secret bit exchange protocols introduced in [FW92b]. We find an optimal strategy for the combinatorial game and show how this leads to a key set protocol that is optimal from among the class of all key set protocols. While key set protocols are too limited to be of much practical interest, this result is nevertheless interesting as an illustration of the close connection between protocols and games and the use of nontrivial game theoretic techniques in the analysis of protocols. The combinatorial game is a simple counting game a little l...