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

Abstract

La caracterització dels matroides representables es un problema obert que està relacionat amb la caracterització de les estructures d'accés que admeten esquemes de compartició ideals. En aquests esquemes, la llargada del secret és la mateixa que la de cada fragment, essent aquest el cas òptim. En aquesta tesi desenvolupem noves tècniques per comprovar la representabilitat dels matroides. Aquestes tècniques estan basades en diversos resultats de la teoria de la informació com la propietat de la informació comuna i el lema d' Ahswelde-Körner. Amb aquestes tècniques, aconseguim una caracterització completa dels matroides multilineals de 8 punts, trobant els matroides multilineals més petits que no admeten representació lineal. Combinant aquestes tècniques basades en la teoria de la informació amb la propietat de la intersecció Euclidiana i altres propietats de la intersecció en matroides estenem aquest estudi als matroides de 9 punts, trobant noves famílies de matroides que satisfan la desigualtat d'Ingleton però que no són linealment representables. Per tots els ports de matroides de 8 punts, calculem fites inferiors en la taxa d'informació pels esquemes de compartició de secrets, trobant un resultat de separació per ports de matroides sparse-paving que no satisfan la desigualtat d'Ingleton. Per ports de matroides sparse-paving, trobem esquemes de compartició de secrets amb fragments de llargada subexponencial. A més, demostrem que per quasi tots els ports de matroides requereixen esquemes de compartició de secrets lineals amb taxa d'informació exponencial.

La caracterización de los matroides representables es un problema abierto que está conectado con la caracterización de las estructuras de acceso que admiten esquemas de compartición de secretos ideales. En estos esquemas, los fragmentos y el secreto tienen el mismo tamaño, siendo este el caso óptimo. En esta tesis desarrollamos nuevas técnicas para comprobar la representabilidad de los matroides. Estas técnicas están basadas en distintos resultados de la teoría de la información como la propiedad de la información común y el lema de Ahswelde-Körner. Con estas técnicas, conseguimos obtener una caracterización completa de los matroides multilineales de 8 puntos, encontrando los matroides multilineales más pequeños que no admiten representación lineal. Combinando estas técnicas basadas en la teoría de la información con la propiedad de la intersección Euclidiana y otras propiedades de la intersección en matroides extendemos este estudio a matroides de 9 puntos, encontrando nuevas familias de matroides que satisfacen la desigualdad de Ingleton pero que no son linealmente representables. Para todos los puertos de matroides de 8 puntos, calculamos cotas inferiores a la tasa de información de esquemas de compartición de secretos, encontrando un resultado de separación para puertos matroides sparse-paving que no satisfacen la desigualdad de Ingleton. Para puertos de matroides sparse- paving, encontramos esquemas de compartición de secretos con fragmentos de tamaño subexponencial. Además, demostramos que casi todos los puertos de matroide requieren esquemas de compartición de secretos lineales con tasa de información exponencial.

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.