Postkvantkrüptograafia

Postkvantkrüptograafia (ka post-kvantkrüptograafia) on termin, mida kasutatakse selliste krüptograafiliste algoritmide kirjeldamiseks, mis suudavad vastu pidada kvantarvutite rünnakutele. 2018. aasta seisuga ei kuulu enamik populaarseid avaliku võtmega algoritme postkvantkrüptograafiliste algoritmide hulka, kuna neid on võimalik edukalt murda piisavalt võimsa hüpoteetilise kvantarvuti abiga. Praeguste krüptograafiliste algoritmide probleemiks on see, et need põhinevad keerulistel matemaatilistel ülesannetel, nagu näiteks täisarvu faktoriseerimine või diskreetse logaritmi arvutamine. Kõiki selliseid probleeme on võimalik lihtsasti lahendada piisavalt võimsa kvantarvuti abiga, kasutades Shori algoritmi.
Kuigi praegu teadaolevad eksperimentaalsed kvantarvutid ei ole piisavalt suure protsessori võimsusega, et murda ühtegi kasutuselolevat krüptograafilist algoritmi, hakatakse aina enam kavandama uusi algoritme, mis peaks vastu ka siis, kui kvantarvutid on jõudnud piisava võimsuseni.
2016. aastal algatas NIST (National Institute of Standards and Technology) projekti, mille eesmärgiks on määrata uued postkvantkrüptograafilised krüpteerimisstandardid. Esimeseks tähajaks, 30. november 2017, esitati 23 digitaalallkirjastamise (ehk signeerimise) skeemi ning 59 andmete krüpteerimise skeemi, millest 69 kiideti heaks. Tulevaste krüpteerimisstandardite visandid peaksid valmima aastatel 2022–2024.

Koodipõhised algoritmid

Üks tuntumaid koodipõhiseid krütposüsteeme on McEliece'i krüptosüsteem, mille pakkus 1978. aastal välja Robert McEliece. McEliece’i krüptosüsteem põhineb üldise lineaarse koodi dekodeerimisprobleemil (lähima koodsõna probleem). Lähima koodsõna probleemi lahendamine seisneb valitud vektorist vähima Hammingi kaugusega koodsõna leidmises ehk valitud vektorile lähima koodsõna leidmises. On tõestatud, et see ülesanne on kindlatel tingimustel NP-raske, mis teeb ta sobivaks postkvantkrüptograafiliste algoritmide jaoks. McEliece’i krüptosüsteem on väga tõhus nii võtme genereerimise, krüpteerimise kui ka dekrüpteerimise kiiruse mõttes, suurimaks puuduseks on aga väga suur avalik võti.

Võrepõhised algoritmid

Võre-põhine krüptograafia kogub aina enam populaarsust tänu oma halvima juhu turvagarantiile ning potentsiaalile vastu pidada kvantarvuti rünnakutele. Võreks nimetatakse eukleidilise ruumi vektorite diskreetset alamhulka, mis on kinnine vektorite liitmise ja lahutamise suhtes. Krüptograafias saab kasutada võredega seotud raskeid kombinatoorikaprobleeme, nagu näiteks lühima vektori probleemi (võre lühima vektori leidmine) ning lähima vektori probleem (võrele lähima vektori leidmine, mis ei ühti võre endaga). Need ülesanded on sobilikud postkvantkrüptograafiliste algoritmide loomiseks, kuna teatud tingimuste ja enamiku baaside juures on nad raskesti lahenduvad.

Räsipõhised algoritmid

Postkvantkrüptograafias on väga levinud ka räsifunktsioonidel põhinevad skeemid. Ennekõike kasutatakse neid signeerimisel – Ralph Merkle ja Leslie Lamport pakkusid välja räsifunktsioonidel põhinevaid sigantuuriskeeme juba 1970ndate lõpus. Räsipõhiseid signeerimisskeemide tugevuseks on see, et nende turvalisus sõltub kasutatava räsifunktsiooni turvalisusest, mis tagab paindlikkuse ja kohandatavuse. Selliste skeemide põhiline puudujääk on võimalike signatuuride piiratud arv. Selle tõttu vähenes huvi räsifunktsioonide vastu krüptograafias, kuni neid hakati jälle uurima nende potentsiaali tõttu pidada vastu kvantarvutite rünnakutele.