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.
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.
[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.
Aprofundir en els coneixements de computació quàntica, tant des del vessant de la física com des del vessant de la teoria de la computació, que em situïn en un punt de "pre-recerca".\nTenir un mapa de les diferents aproximacions a llenguatges de programació quàntica que s'han fet en els últims anys. Distingir els pros/contres i limitacions d'aquestes aproximacions.\nInvestigar els avenços recents relacionats amb complexitat de la CQ i els seus límits des del punt de vista de la teoria de la computació.\nInvestigar les diferents propostes de simulació de CQ en ordinadors actuals.
"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."
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.
¿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