Sep. 20 2010 1:30PM

Sep. 20 2010 3:00PM

A secret sharing scheme is a cryptographic method to protect a piece of information or data by dividing it into pieces, which are called shares, in such a way that it can only be recovered from certain subsets of shares. Considering that each share is held by a participant, the access structure of the scheme is defined as the family of coalitions of participants that can recover the secret. Secret sharing schemes are a very important primitive in cryptography, mainly due to the fact that secret sharing is an essential building block in multiparty computation protocols. Multiparty computation is a very general notion that covers many different kinds of protocols, as electronic elections, electronic biddings, data base access and data base computations, and joint signatures.

Ideal secret sharing schemes are those in which the size of the shares is the same as the size of the secret, which is the best possible situation. However, not all access structures admit ideal schemes, and the general bounds for the size of the shares is exponential on the number of participants. The characterization of ideal access structures is one of the main open problems in secret sharing, and both Matroids and polymatroids play a fundamental role in the study of this problem.

The aim of this talk is to show new results on the characterization of ideal access structures, based on the connection that exists between ideal multipartite access structures and integer polymatroids. These results were presented in TCC 2010 in a joint work with Carles Padro.

Pravidelný seminář Inteligentní systémy (Contact person: Tomáš Kroupa)