Duality between disjunctive and conjunctive hierarchical games

Get Complete Project Material File(s) Now! »

Simple games and secret sharing schemes

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 classic example of such situation is the United Nations Security Council voting on whether or not to impose sanctions on a country developing nuclear weapons. Nine members of the Security Council in total must vote in favour of the sanctions, including all five permanent members. The concept of a simple game, introduced by von Neumann & Morgenstern (1944), is flexible enough to model a large class of such situations.
In the theory of simple games seniority of players is usually modeled by assigning to players different weights and setting a threshold so that a coalition is winning (can undertake the activity) if and only if the combined weight of its players is at least the threshold. Such a simple game is called weighted or weighted threshold. This is perfectly natural, for example, in the context of corporate voting when different shareholders may hold different number of shares. More generally, if two players in a simple game are such that they are either equal to each other in seniority 1, or one is strictly more senior than the other, then they are comparable to each other, and if any two players in the game are comparable, then the game is called complete. The class of complete games includes the class of weighted games and more.
Secret sharing schemes , first introduced by Shamir (1979) and also independently by Blakley (1979), and now widely used in many cryptographic protocols, is a tool designed 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 players ‘shares’ of the secret so that only authorised coalitions can calculate the
secret combining their shares together. Different types of secret sharing schemes exist, and some of them are more efficient and secure than others. The most informationally efficient and secure secret sharing schemes are called ideal. The set of all authorised coalitions of a secret sharing scheme is known as the access structure (e.g., Simmons, 1990; Stinson, 1992). It can also be modeled by a simple game, for, mathematically speaking, an access structure is a simple game, and for simplicity, sometimes we will refer to them as ‘games’.
Our work in this thesis is game-theoretic in nature, however, it is ultimately applied to the study of ideal secret sharing schemes, hence the title of the thesis. Our approach to games here will be based on a way of relating players to each other that we will explain in Chapter 2, called Isbell’s desirability relation (see Isbell (1958), Maschler & Peleg (1966) and Taylor & Zwicker (1999)). It is
a way of organising a simple game into different levels of seniority, where each level contains players who all share the same seniority. This we found has simplified things, and has enabled us to re-write many of the existing results in a more transparent way.

READ THE NEUROMUSCULAR JUNCTION UNDER PHYSIOLOGICAL CONDITIONS

The project of characterising ideal secret sharing schemes

Since ideal secret sharing schemes are the most informationally efficient and secure, and since not all secret sharing schemes are ideal (see Benaloh & Leichter (1990)), the project of characterising all access structures that carry an ideal secret sharing scheme, or in other words characterising ideal access structures, has been pursued by numerous people (e.g., Brickell (1989); Brickell & Davenport (1991); Beimel & Chor (1994); Padr´o & S´aez (1998); Goli´c (1998); Collins 2002); Ng (2006); Mart´ı-Farr´e et al. (2006); Farras et al. (2007); Beimel, Livne,& Padr´o (2008); Beimel, Tassa, &Weinreb (2008); Herranz (2009); HSU ChingFang (2010); Farr`as et al. (2011); Farr`as & Padr´o (2011); Farr`as & Padr´o (2012); Farr`as et al. (2012)). It is now considered as one of the main open problems in the theory of secret sharing schemes. Finding a description of all access structures that can carry an ideal secret sharing scheme appeared to be quite difficult, and there has been two approaches to it.
The first approach, which may be called the top-down approach, employs Matroid Theory. A major milestone was achieved by Brickell & Davenport (1991) who showed that all ideal secret sharing schemes have matroids corresponding to them. Furthermore, matroids are either representable or not (see Oxley (1992) for definitions), and it has been found, also by Brickell & Davenport (1991), that all representable matroids realise ideal access structures. As for the nonrepresentable matroids, it was shown that in at least one case, the Vamos matroid, does not realise an ideal access structure (Seymour (1992)). So this approach is reduced to classifying those matroids that do realise ideal access structures. The papers by Beimel (2011) and Mart´ı-Farr´e & Padr´o (2007) give a nice overview and discussion of the problem, and the developments made therein.

1 Introduction
1.1 Background and Motivation
1.2 Our work in this thesis
2 Preliminaries
2.1 Simple games in real life
2.2 Properties, important classes and some operations in the theory of simple games
2.3 Basics of Secret Sharing Schemes .
3 Hierarchical Simple Games
3.1 The two types of hierarchical simple games, definitions
3.2 Canonical Representations
3.3 Duality between disjunctive and conjunctive hierarchical games .
3.4 Hierarchical Subgames and Reduced Games
3.5 Structural Characterisations
3.6 Weightedness
4 Tripartite Simple Games
4.1 The two types of tripartite simple games, definitions and examples
4.2 Canonical Representations
5 The Composition of Simple Games
6 The Characterisation Theorem
7 Ideal Roughly Weighted Simple Games
8 Conclusion and future research
References