Accés ràpid intranet

Més informació...

a a a

Deim Seminar


Matroid Representations and Applications to Secret Sharing


Michael Bamiloshin

Professor/a organitzador/a

Oriol Farrs Ventura


Universitat Rovira i Virgili


14-11-2023 10:00


Abstract: Matroids are a combinatorial structure that abstract the notions of linear independence. Their representations come in various forms: entropic, linear, algebraic. On the other hand, a secret sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. The information ratio of a secret sharing scheme is the size in bits of the largest share of the scheme divided by the size of the secret. Matroids find application in cryptography via secret sharing where ports of representable matroids give rise to ideal access structures (those in which the information ratio is 1). In this talk, we will look briefly at different classes of representations of matroids, and some tools to find representable matroids. We will also look at the application of matroids to secret sharing. In particular, we will discuss matroid ports and the linear programming technique which is used to derive lower bounds on the information ratio of the schemes for access structures with a focus on the common information and the Ahlswede-Krner information properties. Finally, we will discuss how this technique finds application in the problem of matroid classification.