Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, July 05, 2012, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Peter Chvojka (Slovak University of Technology in Bratislava, Slovakia)

Secret sharing schemes on nonstandard structures

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login