# Criptografia postquàntica

La criptografia postquàntica (PQC), de vegades anomenada a prova quàntica, segura al quàntic o resistent al quàntic, és el desenvolupament d'algorismes criptogràfics (generalment algorismes de clau pública) que es creu que són segurs contra un atac criptoanalític per part d'un ordinador quàntic. El problema dels algorismes populars que s'utilitzen actualment al mercat és que la seva seguretat es basa en un dels tres problemes matemàtics durs: el problema de factorització de nombres enters, el problema de logaritme discret o el problema de logaritme discret de corba el·líptica. Tots aquests problemes es podrien resoldre fàcilment en un ordinador quàntic prou potent que utilitzi l'algoritme de Shor o fins i tot alternatives més ràpides i menys exigents (en termes de nombre de qubits necessaris).
Tot i que a partir del 2023, els ordinadors quàntics no tenen el poder de processament per trencar algorismes criptogràfics àmpliament utilitzats, els criptògrafs estan dissenyant nous algorismes per preparar-se per al Q-Day, el dia en què els algorismes actuals seran vulnerables als atacs de computació quàntica. El seu treball ha cridat l'atenció dels acadèmics i de la indústria a través de la sèrie de conferències PQCrypto organitzada des de 2006, diversos tallers sobre criptografia segura quàntica organitzats per l'Institut Europeu d'Estàndards de Telecomunicacions (ETSI) i l'Institut de Computació Quàntica. La rumorejada de l'existència d'una collita generalitzada ara, desxifrar programes posteriors també s'ha vist com una motivació per a la introducció primerenca d'algoritmes postquàntics, ja que les dades registrades ara encara poden romandre sensibles molts anys en el futur.
En contrast amb l'amenaça que suposa la informàtica quàntica per als algorismes de clau pública actuals, la majoria dels algorismes criptogràfics simètrics i les funcions hash actuals es consideren relativament segurs contra els atacs dels ordinadors quàntics. Tot i que l'algoritme de Grover quàntic accelera els atacs contra xifrats simètrics, duplicar la mida de la clau pot bloquejar eficaçment aquests atacs. Per tant, la criptografia simètrica postquàntica no ha de diferir significativament de la criptografia simètrica actual.

## Algorismes

La investigació de la criptografia postquàntica se centra principalment en sis enfocaments diferents:

### Criptografia basada en gelosia

Aquest enfocament inclou sistemes criptogràfics com l'aprenentatge amb errors, l'aprenentatge en anell amb errors (ring-LWE), l'aprenentatge en anell amb intercanvi de claus d'errors i l'aprenentatge en anell amb signatura d'errors, l'antiga NTRU o GGH. esquemes de xifratge i les noves signatures NTRU i BLISS. Alguns d'aquests esquemes com el xifratge NTRU s'han estudiat durant molts anys sense que ningú trobés un atac factible. Altres com els algorismes d'anell-LWE tenen proves que la seva seguretat es redueix a un problema en el pitjor dels casos. El Grup d'Estudi de Criptografia PostQuàntica patrocinat per la Comissió Europea va suggerir que s'estudiés la variant Stehle-Steinfeld de NTRU per a l'estandardització en lloc de l'algorisme NTRU. En aquell moment, NTRU encara estava patentat. Els estudis han indicat que NTRU pot tenir propietats més segures que altres algorismes basats en gelosia.

### Criptografia multivariant

Això inclou sistemes criptogràfics com ara signatures Lamport, l'esquema de signatura Merkle, XMSS, els esquemes SPHINCS, i els esquemes WOTS. Les signatures digitals basades en hash van ser inventades a finals de la dècada de 1970 per Ralph Merkle i des de llavors s'han estudiat com una alternativa interessant a les signatures digitals teòriques de nombres com RSA i DSA. El seu principal inconvenient és que per a qualsevol clau pública basada en hash, hi ha un límit en el nombre de signatures que es poden signar mitjançant el conjunt de claus privades corresponent. Aquest fet havia reduït l'interès per aquestes signatures fins que l'interès es va revifar a causa del desig d'una criptografia resistent als atacs dels ordinadors quàntics. Sembla que no hi ha patents sobre l'esquema de signatura Merkle i hi ha moltes funcions hash no patentades que es podrien utilitzar amb aquests esquemes. L'esquema de signatura basat en hash XMSS desenvolupat per un equip d'investigadors sota la direcció de Johannes Buchmann es descriu a RFC 8391.

### Criptografia basada en codi

Això inclou sistemes criptogràfics que es basen en codis de correcció d'errors, com ara els algorismes de xifratge McEliece i Niederreiter i l'esquema de signatura de Courtois, Finiasz i Sendrier relacionat. La signatura original de McEliece que utilitza codis Goppa aleatoris ha resistit l'escrutini durant més de 40 anys. Tanmateix, s'ha demostrat que moltes variants de l'esquema McEliece, que pretenen introduir més estructura en el codi utilitzat per reduir la mida de les claus, són insegures. El Grup d'Estudi de Criptografia PostQuàntica patrocinat per la Comissió Europea ha recomanat el sistema de xifratge de clau pública McEliece com a candidat per a la protecció a llarg termini contra els atacs dels ordinadors quàntics.

### Criptografia basada en la isogènia

Aquests sistemes criptogràfics es basen en les propietats dels gràfics d'isogènia de corbes el·líptiques (i varietats abelianes de dimensions superiors) sobre camps finits, en particular els gràfics d'isogènia supersingulars, per crear sistemes criptogràfics. Entre els representants més coneguts d'aquest camp es troben el CSIDH d'intercanvi de claus semblant a Diffie-Hellman, que pot servir com a reemplaçament senzill resistent al quàntic per als mètodes d'intercanvi de claus Diffie-Hellman i la corba el·líptica Diffie-Hellman que estan molt estès. s'utilitza avui, i l'esquema de signatura SQISign que es basa en l'equivalència categòrica entre corbes el·líptiques supersingulars i ordres màxims en tipus particulars d'àlgebres de quaternions. Una altra construcció molt notòria, SIDH/SIKE, es va trencar de manera espectacular el 2022. Tanmateix, l'atac és específic de la família d'esquemes SIDH/SIKE i no es generalitza a altres construccions basades en isogènia.

### Resistència quàntica de clau simètrica

Sempre que s'utilitzin mides de clau prou grans, els sistemes criptogràfics de clau simètrica com AES i SNOW 3G ja són resistents als atacs d'un ordinador quàntic. A més, els sistemes i protocols de gestió de claus que utilitzen criptografia de clau simètrica en lloc de criptografia de clau pública, com Kerberos i l'estructura d'autenticació de la xarxa mòbil 3GPP, també són inherentment segurs contra l'atac d'un ordinador quàntic. Donat el seu desplegament generalitzat al món ja, alguns investigadors recomanen l'ús ampliat de la gestió de claus simètriques semblant a Kerberos com una forma eficient d'aconseguir la criptografia postquàntica avui.

## Referències

* ↑ Shor, Peter W. SIAM Journal on Computing, 26, 5, 1997, pàg. 1484–1509. arXiv: quant-ph/9508027. Bibcode: 1995quant.ph..8027S. DOI: 10.1137/S0097539795293172.
* ↑ Bernstein, Daniel J. «Introduction to post-quantum cryptography». A: Post-Quantum Cryptography (en anglès), 2009.
* ↑ Kramer, Anna Science, 381, 6664, 2023, pàg. 1270. DOI: 10.1126/science.adk9443. PMID: 37733849.
* ↑ «New qubit control bodes well for future of quantum computing» (en anglès). phys.org.
* ↑ «ETSI Quantum Safe Cryptography Workshop» (en anglès). ETSI Quantum Safe Cryptography Workshop. ETSI, 01-10-2014. Arxivat de l'original el 17 agost 2016. [Consulta: 24 febrer 2015].
* ↑ Townsend, Kevin. «Solving the Quantum Decryption 'Harvest Now, Decrypt Later' Problem» (en anglès americà). SecurityWeek, 16-02-2022. [Consulta: 9 abril 2023].
* ↑ «Quantum-Safe Secure Communications» (en anglès). UK National Quantum Technologies Programme, 01-10-2021. [Consulta: 9 abril 2023].
* ↑ Bernstein, Daniel J. «Introduction to post-quantum cryptography». A: Post-Quantum Cryptography (en anglès), 2009.
* ↑ Error: hi ha arxiuurl o arxiudata, però calen tots dos paràmetres.Daniel J. Bernstein. «[Daniel J. Bernstein Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?]» (en anglès), 17-05-2009.
* ↑ Error: hi ha arxiuurl o arxiudata, però calen tots dos paràmetres.Daniel J. Bernstein. «[Daniel J. Bernstein Grover vs. McEliece]» (en anglès), 03-03-2010.
* ↑ Bernstein, Daniel J. «Introduction to post-quantum cryptography». A: Post-Quantum Cryptography (en anglès), 2009.
* ↑ Peikert, Chris. «Lattice Cryptography for the Internet» (en anglès). IACR. Arxivat de l'original el 12 maig 2014. [Consulta: 10 maig 2014].
* ↑ Güneysu, Tim. «Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems» (en anglès). INRIA. [Consulta: 12 maig 2014].
* ↑ Zhang, jiang. «Authenticated Key Exchange from Ideal Lattices» (en anglès). iacr.org. IACR. Arxivat de l'original el 7 setembre 2014. [Consulta: 7 setembre 2014].
* ↑ Ducas, Léo; Durmus, Alain; Lepoint, Tancrède; Lyubashevsky, Vadim Cryptology ePrint Archive, 2013 [Consulta: 18 abril 2015].
* ↑ Lyubashevsky, Vadim. «On Ideal Lattices and Learning with Errors Over Rings». IACR. Arxivat de l'original el 31 gener 2014. [Consulta: 14 maig 2013].
* ↑ Augot, Daniel. «Initial recommendations of long-term secure post-quantum systems». PQCRYPTO, 07-09-2015. [Consulta: 13 setembre 2015].
* ↑ Stehlé, Damien; Steinfeld, Ron Cryptology ePrint Archive, 01-01-2013.
* ↑ Easttom, Chuck. «An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitives». A: 2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC) (en anglès), 2019-02-01, p. 0811–0818. DOI 10.1109/CCWC.2019.8666459. ISBN 978-1-7281-0554-3.
* ↑ Bernstein, Daniel J. «SPHINCS: Practical Stateless Hash-Based Signatures». A: Oswald. Advances in Cryptology -- EUROCRYPT 2015 (en anglès). 9056. Springer Berlin Heidelberg, 2015, p. 368–397 (Lecture Notes in Computer Science). DOI 10.1007/978-3-662-46800-5_15. ISBN 9783662467992.
* ↑ Overbeck, Raphael. «Code-based cryptography». A: Bernstein. Post-Quantum Cryptography (en anglès), 2009, p. 95–145. DOI 10.1007/978-3-540-88702-7_4. ISBN 978-3-540-88701-0.
* ↑ Augot, Daniel. «Initial recommendations of long-term secure post-quantum systems» (en anglès). PQCRYPTO, 07-09-2015. [Consulta: 13 setembre 2015].
* ↑ Castryck, Wouter. «CSIDH: An Efficient Post-Quantum Commutative Group Action». A: Peyrin. Advances in Cryptology – ASIACRYPT 2018 (en anglès). 11274. Cham: Springer International Publishing, 2018, p. 395–427 (Lecture Notes in Computer Science). DOI 10.1007/978-3-030-03332-3_15. ISBN 978-3-030-03332-3.
* ↑ De Feo, Luca. «SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies». A: Moriai. Advances in Cryptology – ASIACRYPT 2020 (en anglès). 12491. Cham: Springer International Publishing, 2020, p. 64–93 (Lecture Notes in Computer Science). DOI 10.1007/978-3-030-64837-4_3. ISBN 978-3-030-64837-4.
* ↑ «Is SIKE broken yet?» (en anglès). [Consulta: 23 juny 2023].
* ↑ Campagna, Matt. «Kerberos Revisited Quantum-Safe Authentication» (en anglès). ETSI.