1978. gads Kriptosistēma pretojas kvantu uzbrukumam

Neviens nav izveidojis daudz jaudīgāku kvantu datoru par kabatas kalkulatoru, taču tas nav atturējis cilvēkus uztraukties par postkvantu skaitļošanas pasaules sekām. Visvairāk noraizējušies ir cilvēki, kuri paļaujas uz kriptogrāfiskiem kodiem, lai aizsargātu sensitīvu informāciju. Kad tiek ieslēgts pirmais pienācīga izmēra kvantu dators, iepriekš drošie kodi, piemēram, parasti izmantotais RSA algoritms, kļūs uzreiz uzlaužami.

Tāpēc kriptogrāfi steidzas meklēt kodus, kas būtu droši postkvantu pasaulē. Šodien Hang Dinhs Konektikutas Universitātē un pāris draugi liecina, ka kriptogrāfi visu laiku ir skatījušies uz vienu. Viņi saka, ka maz lietots kods, ko 1978. gadā izstrādāja CalTech matemātiķis Roberts Makeliece, var pretoties visiem zināmajiem kvantu datoru uzbrukumiem.

Pirmkārt, nošķirsim simetriskos un asimetriskos kodus. Simetriskos kodos ziņojuma šifrēšanai un atšifrēšanai tiek izmantotas identiskas atslēgas. Kvantu datori var ievērojami paātrināt uzbrukumu šāda veida kodiem. Tomēr simetriskiem kodiem ir zināma aizsardzība. Atslēgas izmēra dubultošana novērš šo paātrinājumu. Tātad koda veidotāji vismaz teorētiski var palikt priekšā lauzējiem. (Lai gan praksē drošā nauda būtu plēsējam šajā kaķa un peles spēlē.)

Asimetriski kodi ziņojumu šifrēšanai un atšifrēšanai izmanto dažādas atslēgas. Tā sauktajās publiskās atslēgas šifrēšanas sistēmās, piemēram, populārajā RSA algoritmā, publiskā atslēga ir pieejama ikvienam, kurš to var izmantot, lai šifrētu ziņojumu. Bet tikai tie, kuriem ir privāta atslēga, var atšifrēt ziņojumus, un tas, protams, tiek turēts noslēpumā.

Šo sistēmu drošība balstās uz tā sauktajām slazddurvju funkcijām: matemātiskām darbībām, kuras ir viegli veikt vienā virzienā, bet grūti izdarīt otrā virzienā. Slavenākais piemērs ir reizināšana. Ir viegli reizināt divus skaitļus kopā, lai iegūtu trešo, bet grūti sākt ar trešo skaitli un noteikt, kuri divi to ģenerēja. Šo procesu sauc par faktorizēšanu.

Taču 1994. gadā matemātiķis Pīters Šors izgudroja kvantu algoritmu, kas varētu faktorizēt daudz ātrāk nekā jebkurš klasiskais līdzinieks. Šāds algoritms, kas darbojas pieklājīgā kvantu datorā, varētu izjaukt visas zināmās publiskās atslēgas šifrēšanas sistēmas, piemēram, 4 gadus vecs, kurš skraida amoks Legolendā.

Šeit ir sajūta, kā tas darbojas. Faktorizācijas problēma ir atrast skaitli, kas precīzi sadalās citā. Matemātiķi to dara, izmantojot periodiskuma ideju: matemātiskam objektam ar precīzi pareizo periodiskumu ir jāsadala skaitlis precīzi, bet citiem to nedarīs.

Viens veids, kā izpētīt periodiskumu klasiskajā pasaulē, ir izmantot Furjē analīzi, kas var sadalīt signālu tā komponentu viļņos. Kvantu analogs tam ir kvantu Furjē izlase, un Šora triumfs bija atrast veidu, kā izmantot šo ideju, lai atrastu matemātiskā objekta periodiskumu, kas atklāj faktorus.

Pateicoties Shor, jebkuru kodu, kas balstās uz šāda veida asimetriju (ti, gandrīz visas populārās publiskās atslēgas šifrēšanas sistēmas), var uzlauzt, izmantojot kvantu Furjē uzbrukumu.

McEliese kriptosistēma ir atšķirīga. Arī tas ir asimetrisks, taču tā drošība nav balstīta uz faktorizāciju, bet gan uz mīklas versiju, ko matemātiķi sauc par slēpto apakšgrupas problēmu. Dins un draugi ir parādījuši, ka šo problēmu nevar atrisināt, izmantojot kvantu Furjē analīzi. Citiem vārdiem sakot, tas ir imūns pret Šora algoritma uzbrukumu. Faktiski tas ir imūns pret jebkādiem uzbrukumiem, kuru pamatā ir kvantu Furjē paraugu ņemšana.

Tas ir liels darījums. Tas nozīmē, ka viss, kas ir kodēts šādā veidā, būs drošs, kad nākamās paaudzes kvantu datori sāks meklēt tradicionālākas publiskās atslēgas kriptosistēmas. Viena no šādām sistēmām ir Entropy, vienādranga sakaru tīkls, kas paredzēts, lai pretotos cenzūrai, kuras pamatā ir McEliese kriptosistēma.

Bet Entropy tiek izmantots maz, un ir labi iemesli, kāpēc citi ir pretojušies McEliese šifrēšanas sistēmai. Galvenā problēma ir tā, ka gan publiskā, gan privātā atslēga ir nedaudz smagnēja: standarta publiskā atslēga ir liela matrica, ko raksturo ne mazāk kā 2^19 biti.

Tagad tā var šķist mazāka problēma. Iespējams, ka McEleise sistēma pēkšņi nonāks daudz lielākas uzmanības centrā vairāk nekā 30 gadus pēc tās izgudrošanas.

Tomēr ir vērts norādīt, ka, lai gan jaunais darbs garantē drošību pret visiem zināmajiem kvantu uzbrukumiem, tas neko nedara turpmākajiem kvantu uzbrukumiem. Pilnīgi iespējams, ka kāds izstrādās kvantu algoritmu, kas to sadalīs tikpat viegli, kā to var Šors, izmantojot RSA algoritmu. Mūsu rezultāti neizslēdz citus kvantu (vai klasiskos) uzbrukumus, saka Dinh un co.

Tāpēc turpmākajiem pētījumiem visticamākais scenārijs ir tāds, ka kriptogrāfi atjaunos savus centienus vienā no vairākiem citiem auglīgiem virzieniem, piemēram, uz režģiem balstītos algoritmos un daudzfaktoru kriptogrāfijā.

Jebkurā gadījumā sagaidiet, ka dzirdēsiet daudz vairāk par postkvantu kriptogrāfiju, ja vien to atļauj.

Atsauce: arxiv.org/abs/1008.2390 : McEliece kriptosistēma pretojas kvantu Furjē paraugu ņemšanas uzbrukumiem

paslēpties