Department of Mathematics


Simple games and secret sharing schemes

mathematics_algebra_combinatorics_shamirsecretsharing

A simple game provides a model of collective decision-making in which some coalitions are winning (can undertake certain activity, e.g., pass a bill), whereas other coalitions are losing (and cannot undertake it). The United Nations Security Council is an example of a simple game. This project contributes to the program of numerical characterisation and classification of simple games outlined in the classical monograph of von Neumann and Morgenstern (1944). One of the most fundamental questions of this program is what makes a simple game a weighted majority game, i.e., when we can assign weights to the players so that a coalition is winning if and only if the combined weight of their players exceed a certain threshold. Simple games have numerous applications.

Certain cryptographic keys, such as missile launch codes,  numbered bank  accounts and the secret decoding exponent in an RSA public key cryptosystem, are so important that they present a dilemma. If too many copies are distributed, one may be leaked. If too few, they might all be lost or accidentally destroyed. Secret sharing schemes invented by Shamir (1979) and Blakley (1979) aim to address this problem, and allow arbitrarily high levels of confidentiality and reliability to be achieved. A secret sharing scheme `divides' the secret S into `shares' - one for every user - in such a way that S can be easily reconstructable by any authorised subset of users, but an unauthorised subset of users can extract absolutely no information about S. A secret sharing scheme, for example, can secure a secret over multiple servers and remain recoverable despite multiple server failures. The set of authorised coalitions of a secret sharing scheme, called the access structure, is mathematically a simple game, which allows us to study secret sharing schemes by game-theoretic methods.

 

Selected recent publications:

 

1. Tatiana Gvozdeva and Arkadii Slinko: Weighted and roughly weighted simple games. Mathematical Social Sciences. 2011, 61: 20--30.

 

2. Tatiana Gvozdeva, Lane Hemaspaandra and Arkadii Slinko: Three hierarchies of simple games parameterized by ``resource'' parameters. International Journal of Game Theory, 2013, 42: 1-17.

 

3. Tatiana Gvozdeva, Ali Hameed and Arkadii Slinko: Weightedness and structural characterization of hierarchical simple games.  Mathematical Social Sciences. 2013, 65: 181-189.

 

4. Ali Hameed and Arkadii Slinko: A characterization of ideal weighted secret sharing schemes, 2013,  arXiv:1308.3763 [cs.CR].

 

 

Researchers at The University of Auckland:

 

Arkadii Slinko