"L'objectiu d'aquest treball és conèixer a fons l'estat actual de la criptografia basada en aparellaments, fent ús de potents eines de la teoria de nombres i la geometria algebraica per a comprendre en profunditat la teoria matemàtica subjacent en cadascuna de les seves aplicacions. En primer lloc, fem una breu explicació d'algunes de les aplicacions criptogràfiques basades en aparellaments que més impacte han tingut en el desenvolupament d'aquest camp de recerca. Per altra banda, estudiem en detall la construcció i implementació dels aparellaments més utilitzats en corbes el.líptiques i hiperel.líptiques: l'aparellament de Weil i el de Tate. Finalment, resseguim l'evolució de l'aparellament de Tate-Lichtenbaum des de la seva definició original fins a una definició explícita i senzilla, i per tant totalment adaptada per al seu ús en criptografia.\n. El primer objectiu d'aquest projecte és conéixer l'estat actual de la criptografia basada en aparellaments en general, mantenint com a focus d'interés la criptografia basada\nen la identitat. En aquest sentit, per a nosaltres conéixer voldrà dir per una banda\ndominar la fonamentació matemàtica i per l'altre considerar les aplicacions presents\ni futures en l'àmbit de la criptografia de clau pública."
"L'objectiu d'aquest treball és conèixer a fons l'estat actual de la criptografia basada en aparellaments, fent ús de potents eines de la teoria de nombres i la geometria algebraica per a comprendre en profunditat la teoria matemàtica subjacent en cadascuna de les seves aplicacions. En primer lloc, fem una breu explicació d'algunes de les aplicacions criptogràfiques basades en aparellaments que més impacte han tingut en el desenvolupament d'aquest camp de recerca. Per altra banda, estudiem en detall la construcció i implementació dels aparellaments més utilitzats en corbes el.líptiques i hiperel.líptiques: l'aparellament de Weil i el de Tate. Finalment, resseguim l'evolució de l'aparellament de Tate-Lichtenbaum des de la seva definició original fins a una definició explícita i senzilla, i per tant totalment adaptada per al seu ús en criptografia.\n. El primer objectiu d'aquest projecte és conéixer l'estat actual de la criptografia basada en aparellaments en general, mantenint com a focus d'interés la criptografia basada\nen la identitat. En aquest sentit, per a nosaltres conéixer voldrà dir per una banda\ndominar la fonamentació matemàtica i per l'altre considerar les aplicacions presents\ni futures en l'àmbit de la criptografia de clau pública."
Els diversos avenços en el camp de la física quàntica dels darrers anys han fet que puguem tenir a l’abast, en un futur proper, els ordinadors quàntics. Aquests desenvolupaments tenen una enorme importància per a la criptografia. En aquest treball es dona una introducció a aquests temes: la computació clàssica i la quàntica, la criptografia i els efectes que la computació quàntica té en els seus algoritmes, i la nova criptografia quàntica. Es discuteix com els algoritmes clàssics de la criptografia estan en perill, i com d’altres basats en la física quàntica emergeixen amb un gran potencial per garantir la privacitat de les comunicacions. Paraules clau: física quàntica, comunicacions quàntiques, criptografia, criptografia quàntica,algoritme BB84.
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.
[CA] La computació quàntica pretén donar un gir a tota la computació tal i como la coneixem. En els últims anys s’han realitzat grans avanços que inclús han aconseguit el desenvolupament de llenguatges d’alt nivell per a aquestes revolucionàries computadores. Aquestes revolucionàries arquitectures faciliten la solució de determinats tipus de problemes com la factorització de nombres enters, el logaritme discret o el logaritme discret de curva elíptica, entre altres, que són la base dels algoritmes criptogràfics actuals. Llavors, a pesar de què encara no existeixen computadores quàntiques tan potents com per a trencar les claus generades pels algoritmes criptogràfics actuals, s’està treballant ja en la criptografia postquàntica per a assegurar que els futurs algoritmes criptogràfics siguen robustos per afrontar possibles atacs quàntics en el futur. D’altra banda, hi ha una forta postura que assegura que mai s’aconseguirà construir una computadora quàntica competent. No obstant, la major part del esforç dedicat a la computació quàntica s’invirteix en desenvolupar mètodes de tolerància quàntica a fallades. En aquest treball es donarà a conèixer les bases de la computació quàntica, es presentaran diversos llenguatges quàntics d’alt nivell i les plataformes de simul·lació existents, i es realitzaran experiments per a determinar la capacitat de les computadores quàntiques actuals per a trencar l’encriptació RSA mitjançant l’algoritme quàntic de factorització Shor, analitzant així quánt prop- o lluny -queda la revolució computacional en termes de seguretat, i debatint -en contraposició- si en volta de parlar de supremacia quàntica hauríem de parlar d’utopia quàntica.
Aquesta tesi estudia la verificació de sistemes quàntics en escenaris on l'accés a informació crucial és limitat. Mentre que en el control de qualitat clàssic els defectes poden, en principi, detectar-se de manera determinista, la naturalesa probabilística de la mecànica quàntica imposa limitacions inherents. Aquest fet planteja la pregunta: fins a quin punt és possible identificar de manera fiable defectes en estats i processos quàntics? Per respondre aquesta pregunta s'estudia la discriminació d'estats i canals quàntics en contextos universals, és a dir, quan no es coneix la forma específica de les hipòtesis. L'objectiu és establir rendiments de referència i dissenyar protocols òptims que continuïn sent vàlids sota condicions d'ignorància parcial. La manera d'abordar l'objectiu és mitjançant la combinació d'eines d'optimització convexa amb mètodes de teoria de representacions. La programació semidefinida ofereix el marc per formular els problemes de discriminació com a problemes d'optimització sobre operadors. Per la seva banda, la dualitat de Schur-Weyl i els esquemes d'associació permeten captar la simetria dels problemes estudiats, així com reduir de manera significativa la seva complexitat. Més enllà de la discriminació d'estats, l'isomorfisme de Choi-Jamiołkowski i el formalisme de xarxes quàntiques estenen aquestes tècniques a l'anàlisi de canals quàntics. La primera contribució se centra en el problema anomenat edge detection. Una seqüència de sistemes es divideix en dos dominis, cadascun preparat en un estat desconegut però diferent, i l'objectiu consisteix a identificar la frontera que els separa. Es presenta un protocol òptim per a aquest problema, juntament amb un càlcul eficient de la seva probabilitat d'èxit basat en la dualitat de Schur-Weyl i el formalisme de matrius de Gram. A més, s'explora un escenari mixt, en què els estats passen de ser coneguts a desconeguts, cosa que pot resultar útil per detectar defectes en processos de producció d'estats quàntics. La segona contribució introdueix la detecció quàntica d'anomalies múltiples, en què un conjunt de fonts ha de produir un estat de referència, encara que algunes poden fallar i generar estats anòmals. Es consideren dos casos. En el primer, tant l'estat de referència com els estats anòmals són coneguts; aquest problema es resol analíticament aprofitant l'estructura algebraica dels esquemes d'associació de Johnson, la qual cosa permet obtenir estratègies òptimes tant en el règim d'error mínim com en el d'identificació sense error (inequívoca). En el segon cas, ambdues classes d'estats són desconegudes, i es desenvolupa un protocol universal la optimalitat del qual s'estableix a través de la dualitat de Schur-Weyl. Finalment, la tercera contribució estén la detecció d'anomalies a l'àmbit dels canals quàntics. S'assumeix que els dispositius implementen una operació unitària donada, encara que un subconjunt d'aquests aplica en el seu lloc unitàries desconegudes. Es deriven protocols òptims sense error per identificar aquests dispositius defectuosos, emprant l'isomorfisme de Choi-Jamiołkowski i el formalisme de xarxes quàntiques. L'anàlisi mitjançant teoria de representació i la dualitat mixta de Schur-Weyl demostra que el rendiment òptim pot assolir-se amb estats d'entrada entrellaçats, sistemes auxiliars i estratègies paral·leles.
¿QUÉ ES LA CRIPTOGRAFÍA?Esta sección aborda el tema de la criptografía.La criptología incluye dos técnicas complementarias: la Criptografía y el criptoanálisis [Martorell 00].El criptoanálisis, es el estudio de técnicas matemáticas para tratar de vulnerar técnicas criptográficas, y en general, servicios de seguridad de la información [Menezes, Oorshot y Vanstone 96].La criptografía es: "... el estudio de técnicas matemáticas relacionadas con aspectos de la seguridad de la información tales como la confidencialidad, integridad de datos, autenticación de entidades, y autenticación de origen de los datos.La criptografía no es el único medio de proveer seguridad de la información, sino un conjunto de técnicas" [Menezes, Oorshot y Vanstone 96].Otra definición, un poco más precisa, es "Rama inicial de las Matemáticas y en la actualidad también de la Informática y la Telemática, que hace uso de métodos y técnicas con el objeto principal de cifrar, y por tanto proteger, un mensaje o archivo por medio de un algoritmo, usando una o más claves" [Ramió 06].Es importante mencionar que los esquemas de cifrado no son invulnerables.Por ejemplo, un espía, después de invertir un periodo de tiempo atacando el código, podría descifrar los datos.Este periodo de tiempo es importante porque la vida útil de la clave debe estar correlacionada con la vida útil de los datos que están siendo protegidos.En algunos casos un día es suficiente, mientras que en otros debería permanecer invulnerable de manera indefinida.El ataque más simple que puede realizar un atacante para saber cuál clave se está usando en una comunicación, es hacer una búsqueda exhaustiva o de
La darrera dècada ha estat testimoni d'una revolució tecnològica sense precedents, però els seus fruits encara trigaran a arribar al gran públic.Em refereixo al desenvolupament dels primers prototips d'ordinadors quàntics, la majoria dels quals han estat construïts per empreses privades nordamericanes, amb algunes poques excepcions a la Xina i Europa.Aquest nou tipus d'ordinador fa els càlculs utilitzant les lleis de la mecànica quàntica, és a dir, la teoria física que descriu el comportament de les partícules microscòpiques, com àtoms i molècules, que formen tota la matèria.Per aquest motiu es pensa que els ordinadors quàntics seran molt més potents que els clàssics i podran realitzar en una fracció de segon tasques que per a un ordinador normal requeririen milions d'anys.No obstant això, els ordinadors quàntics disponibles actualment són molt fràgils i de mida petita, per la qual cosa encara no han assolit tot el seu potencial.A Europa, hi ha poques empreses que hagin construït o que es trobin en condicions de construir ordinadors quàntics, i encara menys les universitats o institucions públiques que estan immerses en aquesta cursa.A Catalunya, s'ha anunciat recentment que el Centre de Supercomputació de Barcelona (BSC, segons les sigles en anglès) disposarà del primer ordinador quàntic del sud d'Europa.Això podria situar el nostre país a l'avantguarda de la recerca en aquest àmbit.En els darrers anys, la computació quàntica ha suscitat un gran interès tant per part del sector públic (universitats i institucions estatals de recerca) com del sector privat, i ha generat tot un ecosistema en què gegants tecnològics com Google o Amazon conviuen amb empreses de petit format o fins i tot start-ups que desenvolupen algoritmes i maquinari.Darrere d'aquest boom de la computació quàntica hi ha les grans expectatives que la societat ha posat en aquesta nova tecnologia.Per exemple, hi ha algoritmes que, si s'implementessin en un ordinador quàntic, permetrien descompondre nombres en nombres primers (vegeu la nota 1) en molt menys temps del que necessita un ordinador normal, inclosos els superordinadors més potents.Això pot semblar abstracte, però els sistemes de criptografia que utilitzen els bancs per protegir les transaccions entre comptes corrents es basen en la generació de nombres aleatoris molt grans per després descompondre'ls en factors primers.Un ordinador quàntic podria desxifrar ràpidament aquestes claus i finestra a l'actualitat