Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, July 05, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Peter Chvojka (Slovak University of Technology in Bratislava, Slovakia)
Secret sharing schemes enable to share a key between finite set of participants in such a way that only specified sets of participants, called authorized sets, are able to determine the key. A system of authorized sets is called an access structure. Information rate is a parameter used as a measure of efficiency of the secret sharing scheme and it is defined as the ratio between entropy of random variable induced on the sets of keys and maximum entropy of random variable induced on the set of shares for given participant. Secret sharing schemes with information rate equal 1 are called ideal and their access structures are called ideal too, because their information rate is a maximal possible value. The optimalization of this parameter for access structure is a difficult open problem. In order to define which structures are ideal it was discovered a connection between secret sharing schemes and matroids. Brickell and Davenport prooved that every ideal access structure is a port of matroid. Indeed ideal secret sharing schemes define a matroid. But not every matroid port induces an ideal access structure. The first example of such matroid is the Vamos matroid. In recent years was created several techniques for estimating the lower and upper bounds on information rate. At the end of the presentation I will describe an algorithm computing whether a given access structure is a matroid port.
Automatic MiSe System Software Version 1.4803M | admin login