Simple Games with Applications to Secret Sharing Schemes

Abstract

In many situations, cooperating agents have different status with respect to an activity. Often a coalition can undertake the activity only if sufficiently many agents, or agents of sufficient seniority participate in it. The concept of a simple game, introduced by von Neumann & Morgenstern (1944), is flexible enough to model a large class of such situations. In this dissertation, we consider two important classes of simple games called the classes of weighted simple games, and roughly weighted simple games, and apply the knowledge obtained from their study to make progress towards solving an important open problem in a branch of cryptography called secret sharing schemes. Secret sharing schemes were first introduced by Shamir (1979) and now widely used in many cryptographic protocols as a tool for securely storing information that is highly sensitive and highly important. Such information includes encryption keys, missile launch codes, and numbered bank accounts. A secret sharing scheme stipulates giving to each player a piece of information called ‘share’ so that only authorised coalitions can calculate the secret combining their shares together. The set of all authorised coalitions is called an access structure. Mathematically speaking, an access structure is a simple game. Different types of secret sharing schemes exist, and some of them are more efficient and secure than others. The most informationally efficient and secure schemes are called ideal, and these are obviously very sought after and therefore give rise to the question: Which access structures are ideal? Using game-theoretic methods, we contribute to the problem of characterising all ideal secret sharing schemes in the two aforementioned classes of weighted and roughly weighted simple games. We start with a study of two important classes of simple games in the ideal weighted setting, namely hierarchical and tripartite. Then we study the operation of composing simple games. We then apply our knowledge, and existing results by Beimel, Tassa, & Weinreb (2008) and Farr`as & Padr´o (2010), to providing an ‘if and only if’ characterisation theorem for all ideal weighted simple games. Finally, we undertake a study of some ideal roughly weighted simple games. Here, firstly we generalise our result regarding which hierarchical simple games are weighted to which hierarchical simple games are roughly weighted. Secondly, we answer the question of whether a tripartite simple game can be roughly weighted and nonweighted. Thirdly, we show that there exists an ideal roughly weighted simple game that is neither a hierarchical nor a tripartite simple game, showing that the classification of ideal roughly weighted simple games cannot be accomplished along the same lines as in (Beimel, Tassa, & Weinreb, 2008).