Aquesta tesi presenta algunes contribucions en l'area dels fonaments de la criptografia i del xifrat funcional demostrablement segur.
La primera contribucio es en l'area dels predicats hard-core i consisteix en donar una prova alternativa de la seguretat dels bits interns de la preimatge de les permutacions amb trampa m'es comuns utilizant la metodologia basada en decodificacio en llista d'Akavia, Goldwasser i Safra.
La segona contribucio es un estudi mes detallat del problema de correccio d'errors del codi de Reed-Solomon a l'exponent, que sorgeix de manera natural en molts protocols criptografics de llindar. Mes generalment, estudiem el problema de correccio d'aquest codi quan esta xifrat amb una funcio unidireccional.
Demostrem que la correccio d'errors eficient es possible quan la funcie unidireccional te certes propietats homomorfiques.
Tambe donem evidencia parcial que indica que el nostre resultat es optim en el sentit que la correccio eficient quan el codi esta xifrat es dificil si la funcio unidireccional en questio no te aquestes propietats homomorfiques. Els nostres resultats estan inspirats en un treball anterior de Peikert del 2006.
La tercera contribucio es en el domini del xifrat basat en identitats, en el qual demostrem que qualsevol esquema que sigui segur sota atacs de missatge en clar escollit selectius i que sigui anonim sota atacs adaptatius, tambe es segur contra atacs de missatge en clar escollit adaptatius.
L'ultima contribucio es el disseny del primer esquema basat en atributs que produeix textos xifrats de mida constant i que admet politiques de xifrat de llindar no trivials. El nostre resultat esta inspirat en l'esquema de llindar dinamic de Delerablee i Pointcheval.
Aquesta tesi presenta algunes contribucions en l'area dels fonaments de la criptografia i del xifrat funcional demostrablement segur.
La primera contribucio es en l'area dels predicats hard-core i consisteix en donar una prova alternativa de la seguretat dels bits interns de la preimatge de les permutacions amb trampa m'es comuns utilizant la metodologia basada en decodificacio en llista d'Akavia, Goldwasser i Safra.
La segona contribucio es un estudi mes detallat del problema de correccio d'errors del codi de Reed-Solomon a l'exponent, que sorgeix de manera natural en molts protocols criptografics de llindar. Mes generalment, estudiem el problema de correccio d'aquest codi quan esta xifrat amb una funcio unidireccional.
Demostrem que la correccio d'errors eficient es possible quan la funcie unidireccional te certes propietats homomorfiques.
Tambe donem evidencia parcial que indica que el nostre resultat es optim en el sentit que la correccio eficient quan el codi esta xifrat es dificil si la funcio unidireccional en questio no te aquestes propietats homomorfiques. Els nostres resultats estan inspirats en un treball anterior de Peikert del 2006.
La tercera contribucio es en el domini del xifrat basat en identitats, en el qual demostrem que qualsevol esquema que sigui segur sota atacs de missatge en clar escollit selectius i que sigui anonim sota atacs adaptatius, tambe es segur contra atacs de missatge en clar escollit adaptatius.
L'ultima contribucio es el disseny del primer esquema basat en atributs que produeix textos xifrats de mida constant i que admet politiques de xifrat de llindar no trivials. El nostre resultat esta inspirat en l'esquema de llindar dinamic de Delerablee i Pointcheval.
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
Cette these s'est elaboree dans cette periode de l'histoire de la cryptographie quantique ou plusieurs protocoles avaient ete proposes sans que leur fiabilite n'ait pu etre encore demontree, du moins pas face a toute attaque. De plus, certaines des attaques qui avaient ete mises de cote etaient en fait accessibles a l'aide de la technologie actuelle.
D'un autre cote, le but de la cryptographie quantique a toujours ete la conception de protocoles inconditionnellement fiables, cest-a-dire, fiables face a toute attaque permise par les lois de la physique sans consideration pour aucune contrainte dans le temps ou dans l'espace. Tel etait le niveau de fiabilite espere des protocoles quantiques proposes. Seule la cryptographie quantique pouvait meme oser offrir un tel niveau de securite.
Une certaine application appelee la mise en gage jouait un role primordial dans l'ensemble des applications proposees par les cryptographes quantiques et une preuve de securite inconditionnelle avait ete proposee par Brassard, Crepeau, Jozsa et Langlois pour un protocole realisant cette tache. Notre objectif de depart etait de demontrer que les protocoles de la cryptographie quantique permettent effectivement de realiser avec une securite inconditionnelle la plupart des applications proposees, pas seulement la mise en gage. Cependant, a notre grande surprise et a l'etonnement de plusieurs, nous avons au contraire demontre qu'un protocole quantique de mise en gage inconditionnelle fiable est impossible et ainsi avons remis serieusement en question une partie importante des applications de la cryptographie quantique, en plus d'avoir demoli la preuve mentionnee plus haut. Par contre, en nous appuyant sur les travaux de Bennett, Brassard, Crepeau, Salvail et plus recemment de Yao, nous avons obtenu une preuve de la securite inconditionnelle d'un protocole quantique de distribution de cle.
Un des principes importants que nous avons utilises dans notre these est celui qui dit que tous les phenomenes peuvent etre decrits comme l'execution d'une mesure quantique. De plus, nous avons utilise le fait que cette mesure peut elle-meme etre decrite comme une transformation unitaire sur le systeme qui est compose du systeme mesure, de l'appareil de mesure et du systeme final si celui-ci est different du systeme initial.
Aquesta tesi doctoral tracta sobre alguns aspectes de la generacio de comprimida en cavitats no lineals tipus Kerr. La comprimida es un dels tipus de llum quantica, un tipus de que posseeix propietats relatives a les fluctuacions en els valors esperats dels seus observables de les que no es pot donar compte si no es mitjancant l'us de la teoria quantica de la radiacio. L'estat buit del camp electromagnetic posseeix fluctuacions d'acord amb el principi d'incertitud d'Heisenberg. En aquest context, denominem comprimida a un tipus de radiacio que presenta en algun dels seus observables fluctuacions menors que les corresponents a l'estat buit. Aquest tipus especial de radiacio ha assolit forca importancia per diverses raons. D'una banda, permet anar mes enlla dels limits de la precisio que la mecanica quantica imposa per a les mesures realitzades emprant estats coherents - semblants als camps produits pels lasers -. A mes a mes, cal afegir que una nova area d'aplicacio ha fet creixer l'interes per la comprimida: el camp de la informacio quantica; coincidencia d'interessos ja que compressio de la i entrellacat quantic (entanglement) son dues cares de la mateixa moneda i l'entanglement es l'element fonamental responsable dels avantatges de la informacio quantica respecte de la informacio classica. Donat que l'estudi d'aquest tipus de implica l'analisi quantica cal remarcar que en aquest treball unicament descriurem quanticament la radiacio electromagnetica, pero obviarem la quantitzacio de la materia i de les interaccions a les quals puguera donar lloc. Aixi doncs, si partim d'aquesta descripcio, l'obtencio d'aquesta comprimida exigeix que estiga generada per processos optics no lineals, es a dir, processos l'Hamiltonia dels quals siga no lineal en els operadors creacio i destruccio quantics. La dinamica seguida en la interaccio entre el medi no lineal i el camp electromagnetic aporta graus alts de compressio per alguns valors dels parametres del sistema i dels camps injectats, els punts que anomenem critics i que corresponen als valors per als quals l'evolucio del sistema presenta una bifurcacio o be perque entra en un regim de biestabilitat o be perque s'engega un altre mode del camp electromagnetic. Pel que fa a les interaccions no lineals, tambe poden ser de diversos tipus, pero les de tipus ??²? i les del tipus ??³? son les mes emprades, ja que les interaccions ressonants son frequentment acompanyades de processos d'emissio espontania que devaluen la compressio. En aquesta tesi s'estudien les propietats per a produir comprimida de les cavitats no lineals del tipus ??³? tambe conegudes com cavitats Kerr. Pel que fa a la redaccio d'aquesta tesi, es pot agrupar en dos grans blocs. Per una part, hem dut a terme una contribucio en el domini de les eines matematiques que son necessaries per estudiar aquestos processos. La nostra contribucio, relativa a l'us de les distribucions de quasiprobablitat, apareix dins d'aquesta exposicio. A la segona part de la tesi s'aborden la resta d'aportacions: generacio de amb polaritzacio comprimida en una cavitat Kerr vectorial, obtencio de compressio no critica per trencament espontani de la simetria de rotacio i tambe per trencament espontani de la simetria de polaritzacio. Aquestes dues ultimes contribucions constitueixen exemples particulars d'un mecanisme de generacio de comprimida que ha estat proposat originalment pel nostre grup d'investigacio i tot fa pensar que aquesta tecnica fara possible obtenir nivells de compressio encara millors que els detectats fins aquest moment. El treball es tanca amb una recapitulacio critica dels resultats obtinguts aixi com de les perspectives de futur que s'obren amb la seua cloenda.
Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication .
This PhD thesis focuses on lattice-based cryptography and how to apply it to build post-quantum online voting systems. It is the result of the research done by the author at Scytl in close collaboration with Dr. Paz Morillo, from the Department of Applied Mathematics at UPC and Ramiro Martínez, PhD student. As part of her work at the electronic voting company Scytl, the author has participated in the design of several electronic voting systems as well as in their implementation, by providing support to the development team. Nevertheless, all these systems use standard and well-known cryptographic primitives, i.e., not lattice-based primitives, to ensure that the security requirements are fulfilled. Due to this, one of the main challenges of this PhD has been to start researching on a field which was not familiar to the author and contribute to its state of the art. This has allowed the company to enter the post-quantum world by participating in a project which aims to implement a lattice-based online voting system. The thesis has the following contents: an introduction to the lattice theory by describing some of its basic concepts and the computational problems in which the security of lattice-based cryptosystems relies. In this first part it is also described in detail those cryptosystems that are used as building blocks of three new protocols proposed in the thesis: a lattice-based coercion-resistant cast-as-intended protocol, a post-quantum mix-net and a fully post-quantum proof of a shuffle. The former is the lattice version of an existing protocol and allows the voter to check that the vote cast contains the selected voting options. The second and third protocols are the result of the research on lattice-based mix-nets. Two constructions are proposed: the first one allows to demonstrate that a mix-node has permuted and re-encrypted a list of RLWE ciphertexts without modifying them, but it cannot be considered fully post-quantum since the binding property of the commitment scheme relies on classical computational problems. The second one is fully post-quantum since all the cryptographic schemes used for building it, i.e., commitment scheme and zero-knowledge proofs, are based on lattices. Last but not least, for this second proposal a security definition and a proof of security are also provided. Finally, the last part of the thesis consists of building a post-quantum online voting system using as building blocks the protocols already presented and existing lattice-based constructions. This system is considered secure under quantum attacks and provides long-term privacy. It also guarantees vote anonymity, vote authenticity, vote integrity, individual verifiability and receipt-freeness. The algorithms involved in each phase are described in detail as well as the interaction among the participants. An implementation of this system is not given as part of this thesis although a lattice-based online voting system based on that is already being implemented at the company. Aquest tesi es centra en la criptografia basada en reticles i com aplicar-la a la construcció de sistemes de votació electrònica post-quàntics. És el fruit de la recerca feta per l'autora de la tesi a Scytl en estreta col·laboració amb la Dra. Paz Morillo, del Departament de Matemàtica Aplicada de la UPC i en Ramiro Martínez, estudiant de doctorat. Com a part de la seva feina a l'empresa de vot electrònic Scytl, l'autora ha participat tant en el disseny de sistemes de votació electrònica com en la seva implementació, donant suport a l'equip de desenvolupament. No obstant, tots aquests sistemes utilitzen primitives criptogràfiques estàndard (primitives no basades en reticles) per assegurar que els requisits de seguretat es compleixen, i és per aquest motiu que un dels principals reptes d'aquest doctorat ha estat fer en recerca en un camp que no era familiar per l'autora, i contribuir-hi. Per altra banda, això ha permès a l'empresa endinsar-se en el món post-quàntic i participar en un projecte que té per objectiu implementar un sistema de vot electrònic basat en reticles. Aquest tesi consta dels següents continguts: una introducció a la teoria dels reticles on es descriuen alguns dels seus conceptes bàsics i els problemes computacionals dels quals depèn la seguretat dels criptosistemes basats en reticles. En aquesta primera part també es descriuen en detall aquells criptosistemes utilitzats en la construcció dels tres nous protocols presentats en aquesta tesi: un protocol basat en reticles resistent a la coacció i que ofereix verificabilitat “cast-as-intended”; una “mix-net post-quàntica” i una prova de coneixement nul totalment post-quàntica que permet demostrar que la barreja de vots s'ha realitzat correctament. El primer protocol és la versió basada en reticles d'un protocol ja existent i permet que el votant comprovi que el vot emès conté les opcions que havia seleccionat. El segon i el tercer protocol són el resultat de la recerca feta en el camp de les mix-nets basades en reticles. Es proposen dues construccions: la primera d'elles permet demostrar que un node de la mix-net ha barrejat i rexifrat una llista de xifrats RLWE sense modificar-los, però no es pot considerar totalment post-quàntica ja que la propietat de lligar de l'esquema de compromís utilitzat per construir la prova es basa en problemes computacionals clàssics. La segona construcció és totalment post-quàntica ja que tots els esquemes criptogràfics utilitzats en el seu disseny, és a dir, esquema de compromís i proves de coneixement nul, estan basats en reticles. Finalment, però no per això menys important, per aquesta segona proposta també es dóna una definició de seguretat i una prova de seguretat. L'última part de la tesi consisteix en construir un sistema de vot online post-quàntic, utilitzant com a components els protocols prèviament presentats i construccions ja existents basades en reticles. El sistema es considera segur en front atacs quàntics i ofereix privadesa a llarg plaç. També garanteix l'anonimat del vot, la seva autenticitat i integritat, verificabilitat individual i resistència a la coacció. Es descriuen en detall tant els algoritmes executats a cada fase com la interacció entre els seus participants. Com a part de la tesi no s'inclou cap implementació del sistema tot i que l'empresa està implementant un sistema de vot online basat en el que es presenta en aquesta tesi.
Protocoles avec Sécurité Inconditionnelle issus de Techniques de la Théorie des Codes Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc...