Common information techniques for the study of matroid representation and secret sharing schemes

Identifier:  TDX:3200

Handle: https://hdl.handle.net/20.500.11797/TDX3200

Authors:  Olugbenga Bamiloshin, Michael

Abstract:
The characterization of representable matroids is a longstanding open problem. This problem is connected to the characterization of access structures that admit ideal secret sharing schemes. In these schemes, the size of each share is equal to the size of the secret, which is an optimal situation. In this thesis, we develop new techinques to check representability properties that are based on different results of information theory such as the common information property and the Ahswelde-Körner lemma. With these techniques, we give a complete characterization of matroids on 8 points that admit folded linear (i.e., multilinear) representations, finding the smallest matroids that are not linearly representable but admit folded linear representations. Combining these new techniques based on information theory with the Euclidean intersection property and other matroid intersection properties, we move further to 9-point matroids, finding new families of non-representable matroids that are Ingleton-compliant. We give lower bounds on the information ratio of secret sharing schemes for the ports of all matroids on 8 points and show a separation result for non-Ingleton- compliant sparse-paving matroids. We show that ports of sparse-paving matroids admit schemes with sub-exponential share size. We also present exponential lower bounds for the information ratio of linear secret sharing schemes for almost all matroids.