This thesis is dedicated to the study of secret sharing schemes, which are cryptographic methods to share information in a secure way. The topics that are considered in the thesis are two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares for general access structures. These open problems are studied for multipartite secret sharing schemes. In these schemes the set of participants is divided into parts and the participants in each part have the same rights to obtain the secret. The results of the thesis are based on a new combinatorial property of secret sharing schemes, which is a connection between ideal multipartite secret sharing schemes and integer polymatroids. It provides new sufficient conditions and necessary conditions for an access structure to be ideal. Moreover, this connection is also used in the construction ideal linear multipartite secret sharing schemes. These results are useful for the study of multipartite access structures in which the number of parts is small in relation to the number of participants, and multipartite access structures in which the parts are related in a special way. This is the case of the family of hierarchical access structures, which are the ones in which the participants can be hierarchically ordered, and the family of tripartite access structures. Applying these results, the ideal access structures in these families are completely characterized. All the ideal multipartite secret sharing schemes presented in the literature are related to a particular family of integer polymatroids, the boolean ones. The analysis of these polymatroids leds to the find of new ideal multipartite secret sharing schemes. The optimization of the length of the shares is also studied for multipartite secret sharing schemes, in particular for the bipartite ones. The main results are a new method to find bound on the length of the shares that combines linear El tema d'aquesta tesi són els esquemes de compartició de secrets, uns mètodes criptogràfics que permeten fragmentar missatges de manera segura. En particular s'aborden dos dels principals problemes oberts en aquest camp: la caracterització de les estructures d'accés que admeten esquemes de compartició de secrets ideals i l'optimització de la llargada dels fragments en construccions per estructures d'accés generals. Aquests problemes oberts s'estudien per estructures d'accés multipartides, que són estructures en què el conjunt de participants està dividit en diferents parts i a cada part tots els participants tenen el mateix rol. Aquest plantejament resulta útil per estudiar famílies d'estructures d'accés en què el nombre de parts és petit i estructures en què hi ha alguna relació especial entre les parts, com les jeràrquiques i les compartmentades. L'eina principal d'aquest estudi és una nova propietat de les estructures ideals que es presenta en aquesta tesi, una connexió entre les estructures ideals multipartides i els polimatroides enters. A partir d'aquesta connexió s'obté una condició suficient i una de necessària perquè una estructura d'accés multipartida sigui ideal. Així, aquesta connexió permet discutir la idealitat de les estructures d'accés i també, en el cas que el polimatoride sigui representable, construir esquemes ideals a partir de les representacions. Aplicant aquests resultats s'obté un nou marc per descriure i analitzar mètodes per construir esquemes multipartits ideals. Com a resultat d'aquest estudi s'obté una caracterització completa de les estructures d'accés tripartides ideals i de les jeràrquiques ideals. Una estructura és jeràrquica si el conjunt de participants es pot ordenar de tal manera que si en un conjunt autoritzat es canvia un participant per un de jeràrquicament superior, el nou conjunt també és autoritzat. A partir d'aquest resultat s'obté una nova caracterització de les estructures de llindar amb pesos ideals. Després d'analitzar tots els esquemes de compartició de secrets ideals multipartits presentats fins l'actualitat, es mostra que tots ells estan relacionats amb una família molt senzilla de polimatroides enters, els booleans. A partir d'aquests polimatroides s'obté una nova família d'estructures ideals, les compartmentades, que inclouen diverses famílies estudiades prèviament. L'altre problema obert considerat a la tesi, l'estudi de l'optimització de la llargada dels fragments, es centra en les estructures bipartides. Combinant tècniques de programació lineal i polimatroides, es presenta un mètode per calcular fites en la llargada dels fragments per estructures d'accés no ideals que és vàlid per qualsevol estructura multipartida. A partir de tècniques algebraiques es presenten noves fites i una família d'esquemes bipartits òptims.
This thesis is dedicated to the study of secret sharing schemes, which are cryptographic methods to share information in a secure way. The topics that are considered in the thesis are two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares for general access structures. These open problems are studied for multipartite secret sharing schemes. In these schemes the set of participants is divided into parts and the participants in each part have the same rights to obtain the secret. The results of the thesis are based on a new combinatorial property of secret sharing schemes, which is a connection between ideal multipartite secret sharing schemes and integer polymatroids. It provides new sufficient conditions and necessary conditions for an access structure to be ideal. Moreover, this connection is also used in the construction ideal linear multipartite secret sharing schemes. These results are useful for the study of multipartite access structures in which the number of parts is small in relation to the number of participants, and multipartite access structures in which the parts are related in a special way. This is the case of the family of hierarchical access structures, which are the ones in which the participants can be hierarchically ordered, and the family of tripartite access structures. Applying these results, the ideal access structures in these families are completely characterized. All the ideal multipartite secret sharing schemes presented in the literature are related to a particular family of integer polymatroids, the boolean ones. The analysis of these polymatroids leds to the find of new ideal multipartite secret sharing schemes. The optimization of the length of the shares is also studied for multipartite secret sharing schemes, in particular for the bipartite ones. The main results are a new method to find bound on the length of the shares that combines linear El tema d'aquesta tesi són els esquemes de compartició de secrets, uns mètodes criptogràfics que permeten fragmentar missatges de manera segura. En particular s'aborden dos dels principals problemes oberts en aquest camp: la caracterització de les estructures d'accés que admeten esquemes de compartició de secrets ideals i l'optimització de la llargada dels fragments en construccions per estructures d'accés generals. Aquests problemes oberts s'estudien per estructures d'accés multipartides, que són estructures en què el conjunt de participants està dividit en diferents parts i a cada part tots els participants tenen el mateix rol. Aquest plantejament resulta útil per estudiar famílies d'estructures d'accés en què el nombre de parts és petit i estructures en què hi ha alguna relació especial entre les parts, com les jeràrquiques i les compartmentades. L'eina principal d'aquest estudi és una nova propietat de les estructures ideals que es presenta en aquesta tesi, una connexió entre les estructures ideals multipartides i els polimatroides enters. A partir d'aquesta connexió s'obté una condició suficient i una de necessària perquè una estructura d'accés multipartida sigui ideal. Així, aquesta connexió permet discutir la idealitat de les estructures d'accés i també, en el cas que el polimatoride sigui representable, construir esquemes ideals a partir de les representacions. Aplicant aquests resultats s'obté un nou marc per descriure i analitzar mètodes per construir esquemes multipartits ideals. Com a resultat d'aquest estudi s'obté una caracterització completa de les estructures d'accés tripartides ideals i de les jeràrquiques ideals. Una estructura és jeràrquica si el conjunt de participants es pot ordenar de tal manera que si en un conjunt autoritzat es canvia un participant per un de jeràrquicament superior, el nou conjunt també és autoritzat. A partir d'aquest resultat s'obté una nova caracterització de les estructures de llindar amb pesos ideals. Després d'analitzar tots els esquemes de compartició de secrets ideals multipartits presentats fins l'actualitat, es mostra que tots ells estan relacionats amb una família molt senzilla de polimatroides enters, els booleans. A partir d'aquests polimatroides s'obté una nova família d'estructures ideals, les compartmentades, que inclouen diverses famílies estudiades prèviament. L'altre problema obert considerat a la tesi, l'estudi de l'optimització de la llargada dels fragments, es centra en les estructures bipartides. Combinant tècniques de programació lineal i polimatroides, es presenta un mètode per calcular fites en la llargada dels fragments per estructures d'accés no ideals que és vàlid per qualsevol estructura multipartida. A partir de tècniques algebraiques es presenten noves fites i una família d'esquemes bipartits òptims.
Suposem que un conjunt de n participants vol calcular una determinada funcio (publica) de les seves entrades (secretes). De manera generica els protocols de computacio multipart s'encarreguen de garantir una solucio per a aquest tipus de situacions. Proposen protocols segurs on els participants executen conjuntament un protocol de manera distribuida que els permet obtenir, al final, el resultat de l'avaluacio de la funcio amb les seves entrades. A mes a mes es garanteixen alguns aspectes de seguretat, com la privacitat de les entrades dels participants aixi com l'exactitud del resultat, fins i tot si alguns participants del protocol es comporten de manera deshonesta. A finals dels anys 80 es van presentar les primeres solucions generals a aquest problema que garantien seguretat tot i que certes families de participants es comportessin de manera corrupta. Aquestes families estaven caracteritzades per un cert llindar t, de manera que la seguretat del protocol estava garantida nomes si menys de t participants eren corromputs. No va ser fins l'any 2000 que no es va presentar una solucio eficient per a resoldre aquest problema, permetent l'estructura mes general possible de participants per corrompre. La proposta relacionava la computacio multipart amb els esquemes lineals per a compartir secrets. En certa manera utilitzen la linealitat del esquemes lineals per a compartir secrets per a calcular la part lineal de la funcio. Pero per poder calcular qualsevol funcio es necessari poder avaluar la multiplicacio de manera distribuida entre el conjunt de participants. Aixi es com sorgeix el problema matematic de la multiplicacio dels esquemes lineals per a compartir secrets. En poques paraules, el problema consisteix en trobar protocols eficients que calculin el producte de dos secrets a partir dels fragments que cada participant te de cadascun dels secrets. Un dels punts clau de la seva proposta es la reduccio de la co
Secret sharing schemes are a fundamental cryptographic tool for securely distributing sensitive information among multiple parties according to a specified access structure. For a given access policy, several schemes with different levels of efficiency may exist. One of the main parameters in this analysis is the share size and a central goal is to minimize it. This thesis studies the complexity of secret sharing schemes by focusing on lower and upper bounds on the share size for arbitrary and explicit access structures. The main objective is to collect the most relevant results in the literature, ranging from early lower bounds due to Karnin et al. and Csirmaz and upper-bound of Liu and Vaikuntanathan to recent advances that have significantly improved known bounds. Despite this progress, a significant gap between lower and upper bounds remains, leaving the determination of the optimal share size an open problem.
Aquesta tesi tracta l’estudi de xarxes quantiques amb una estructura complexa, les implicacions que aquesta estructura te en la distribucio d’entrellacament i com el seu funcionament pot ser millorat mitjancant operacions en el regim quantic. Primer considerem xarxes complexes d’estats bipartits, tant purs com mescla, i estudiem la distribucio d’entrellacament a llargues distancies. Despres passem a analitzar xarxes de canals sorollosos i estudiem la creacio i distribucio de grans estats multipartits. El treball contingut en aquesta tesi esta motivat principalment per la idea que la interaccio entre la informacio quantica i les xarxes complexes pot donar lloc a una nova comprensio i caracteritzacio dels sistemes naturals. Les xarxes complexes tenen una importancia particular en les infraestructures de comunicacio, ja que la majoria de xarxes de telecomunicacio tenen una estructura complexa. En el cas de xarxes quantiques, que son el marc necessari per al processament distribuit d’informacio i comunicacio quantica, es ben possible que en el futur adquireixin una topologia complexa semblant a la de les xarxes existents, o que fins i tot es desenvolupin metodes per a utilitzar les infraestructures actuals en el regim quantic. Una tasca central en les xarxes quantiques es dissenyar estrategies per distribuir entrellacament entre els seus nodes. En la primera part d’aquesta tesi, considerem la distribucio d’entrellacament bipartit com un proces de percolacio d’entrellacament en una xarxa complexa. Des d’aquest enfocament, s’estableix entrellacament perfecte de manera probabilistica entre dos nodes arbitraris. Veiem que, per a xarxes grans, la probabilitat d’aconseguir-ho es una constant estrictament major que zero (i independent de la mida de la xarxa) si la quantitat inicial d’entrellacament esta per sobre d’un cert valor critic. La mecanica quantica ofereix aqui la possibilitat de canviar l’estructura de la xarxa sense necessitat d’establir nous canals “fisics”. Mitjancant una transformacio local adequada de la xarxa, es pot disminuir l’entrellacament critic i augmentar la probabilitat. Apliquem aquesta transformacio a models de xarxes complexes amb una distribucio de graus arbitraria. En el cas de xarxes sorolloses d’estats mescla, veiem que per algunes classes d’estat es pot utilitzar el mateix enfocament de percolacio d’entrellacament. Per a estats mescla generals considerem una percolacio de llargada de cami limitada per la quantitat de soroll de les connexions. Veiem com les xarxes complexes ofereixen encara un gran avantatge en la probabilitat de connectar dos nodes. En la segona part, passem a l’escenari multipartit. Estudiem la creacio i distribucio d’estats graf amb una estructura que imita la de la xarxa de comuicacio subjacent. En aquest cas, utilitzem una xarxa complexa arbitraria amb canals sorollosos, i considerem que les operacions i mesures son tambe sorolloses. Proposem un metode eficient per a distribuir i purificar petits subgrafs, que despres es fusionen per a reproduir l’estat desitjat. Comparem aquest enfocament amb dos protocols bipartits basats en un node central i coneixement complet de l’estructura de la xarxa. Mostrem que la fidelitat dels estats graf generats es pot escriure com la funcio de particio d’un sistema desordenat de spins classics (un vidre de spins), i la seva taxa de decaiment es l’analeg de l’energia lliure. Utilitzant els tres protocols en una xarxa unidimensional i en xarxes complexes veiem que son tots comparables, i que en alguns casos el protocol de subgrafs proposat, que necessita nomes informacio local de la xarxa, te inclus un comportament millor.
Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well-known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.
L'estudi de propietats de sistemes quantics formats per moltes particules es inherentment una tasca dificil. De fet, la solucio de problemes classics similars ja es un problema desafiant, encara mes complicat per la naturalesa quantica de les interaccions. Els recursos necessaris per l'estudi d'estats quantics en un espai de Hilbert creix exponencialment amb el nombre de particules. Resultats analitics son restringits a situacions particulars, i els resultats numerics son possibles nomes pera a poques particules. La teoria de la informacio quantica (QIT) proporciona una nova perspectiva per estudiar i explicar conceptes fonamentals de mecanica quantica, aprofitant aquest fenomens per dissenyar noves tecniques pel processat i manipulacio de la informacio. El desenvolupament de la QIT te una connexio directa amb els recents avencos experimental principalment en la interaccio de llum i la materia. Tot i tractar-se d'un camp relativament jove, aquest resultat teorics i experimental ja s'han traduit en aplicacions tecnologiques. La tesi s'ubica enmig de totes aquestes disciplines, actualment un camp de recerca molt fertil. Es centra en l'estudi de hamiltonians locals des de la perspectiva de la QIT, amb resultats en materia condensada. Es centra en metodes numerics per l'estudi de sistemes quantics formats per moltes particules, mostrant com resultats de QIT poden ser emprats en l'estudi de sistemes complexos. Es tracta d'un treball principalment numeric, amb resultats teorics pera a alguns casos particulars. Tot i aixo identifiquem propietats fonamentals dels sistemes quantics que apareixen indistintament en sistemes formats per especies completament diferents, fermions i bosons. Hem explorat les propietats fisiques dels estats termics de sistemes de moltes particules corresponents a situacions amb soroll termic. Estats termics son tipicament presents e escenaris experimentals, pero el seu estudi en llenguatge de la QIT es veu limitat per la dificultat de caracteritzar l' entanglement en estats mescla. Hem presentat un metode constructiu per mostrar la presencia de correlacions quantiques al sistema. A baixes temperatures, la fisica dels sistemes de moltes particules es dominada per les propietats de l'estat fonamental. Els hamiltonians locals poden ser simulats eficientment amb mitjans classics gracies a les propietats de l' entanglement de l'estat fonamental. Mostrem en aquesta tesi com la distancia d'interaccio juga un paper menor en aquest escenari, permetent una simulacio eficient en escenaris mes connectats que l'estandard regim d'interaccio al primers veins. La generalitat d'alguns dels resultats de la tesi permet una extensio directa. La nostra recerca actual es centra en la continuacio d'aquests resultats. Per una banda, la termodinamica quantica es un camp tan ampli que pot ser estes a multiples escenaris, en concret les geometries 2D permeten un millor estudi de la relacio entre lleis d'area i correlacions. Per altra banda, els metodes SDP desenvolupats en la tesi es poden adaptar a diferents problemes quantics, gracies a la seva generalitat basada en l' anticommutacio d'operadors.
In a bipartite secret sharing scheme, the set of participants is divided into two parts, and all participants in each part play an equivalent role. The ideal bipartite access structures were characterized by Padr´o and S´aez, but it is not known which is the optimal information rate of non ideal bipartite access structures. Determining the optimal information rate of general access structures is one of the major problems in secret sharing. We study this open problem restricted to the bipartite access structures, obtaining a new method to compute bounds on the optimal information rate. Namely, by using the connection between secret sharing schemes and polymatroids, we show a linear programming problem that determines, for each access structure, an upper bound on the information rate. Moreover, we show new optimal constructions for certain bipartite access structures.