dc.contributor
Universitat Rovira i Virgili. Departament d'Enginyeria Informàtica i Matemàtiques
dc.contributor.author
Olugbenga Bamiloshin, Michael
dc.date.accessioned
2021-07-22T10:11:20Z
dc.date.available
2022-07-08T02:00:09Z
dc.date.issued
2021-07-08
dc.identifier.uri
http://hdl.handle.net/10803/672219
dc.description.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.
en_US
dc.description.abstract
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.
en_US
dc.description.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.
en_US
dc.format.extent
113 p.
en_US
dc.format.mimetype
application/pdf
dc.language.iso
eng
en_US
dc.publisher
Universitat Rovira i Virgili
dc.rights.license
ADVERTIMENT. Tots els drets reservats. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Matroides
en_US
dc.subject
esquemes de compartició de secrets
en_US
dc.subject
teoria de la informació
en_US
dc.subject
esquemas de compartición de secretos
en_US
dc.subject
Secret sharing
en_US
dc.subject
Matroids
en_US
dc.subject
Information theory
en_US
dc.subject.other
Ciències
en_US
dc.title
Common information techniques for the study of matroid representation and secret sharing schemes
en_US
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.contributor.director
Farràs Ventura, Oriol
dc.embargo.terms
12 mesos
en_US
dc.rights.accessLevel
info:eu-repo/semantics/openAccess