Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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**: OAT S15/S16/S17

**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.

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

Previous talks by year: 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