Įspėjimas: šis algoritmas savaime sunaikins jį panaudojus

Įsivaizduokite du milijonierius – Alisą ir Bobą, kurie nori nuspręsti, kuris yra turtingesnis, bet neatskleidžia savo turtų. Kaip jie sprendžia savo mįslę? Tai Yao milijonieriaus problema, kurią 1982 m. sukūrė kompiuterių mokslininkas Andrew Yao.

Vienas iš galimų sprendimų yra vienkartinė kompiuterinė programa. Ši programa leidžia Alisa ir Bobui privačiai įvesti savo duomenis, vieną kartą apskaičiuoja, pateikia atsakymą ir tada sunaikina save. Taip užtikrinama, kad niekas negalės pasiekti pradinių duomenų ar būdo, kaip jie buvo apdoroti. Ir tai suteikia Alisa ir Bobui atsakymą nepakenkiant jų finansinėms detalėms.

Kompiuterių saugumo ekspertai teigia, kad vienkartinės programos yra labai svarbus kibernetinio saugumo įrankis. Arba jie būtų, jei kas galėtų juos pastatyti.

Pasirodo, neįmanoma sukurti idealios vienkartinės programos, kuri paleidžiama vieną kartą, o paskui save sunaikina. Klasikinis tokio tipo kompiuteris turėtų būti fiziškai sunaikintas, kad jo nebebūtų galima naudoti, ir nėra žinomo būdo tai užtikrinti.

Kvantinis kompiuteris gali pasiūlyti daugiau galimybių, nes kvantinė informacija lengvai sunaikinama ir jos neįmanoma nukopijuoti. Tačiau pasirodo, kad kvantinis kompiuteris negali duoti deterministinio atsakymo į vienkartinį skaičiavimą.

Taigi svajonė apie vienkartinę programą, kuri sunaikina save po vieno skaičiavimo, atrodo pasmerkta.

Įstojo Marie-Christine Roehsner iš Vienos universiteto ir Joshua Kettlewell iš Singapūro nacionalinio universiteto ir keli draugai. Šiandien jie sako radę būdą, kaip sukurti vienkartinę programą, ir pirmą kartą sukonstravo bei demonstravo principo įrodymo įrenginį.

Naujasis metodas remiasi kitokiu mąstymo būdu apie vienkartines programas, kurias atlieka kvantiniai kompiuteriai. Iki šiol saugumo ekspertai visada tikėjosi galutinio sprendimo: Bobo vertė yra didesnė arba mažesnė nei Alisos.

Tačiau kvantinė mechanika iš prigimties yra tikimybinis procesas, o tai reiškia, kad ji gali pateikti teisingą atsakymą tik tam tikrose tikimybės ribose, tarkime, 75 proc. Kol Alisa ir Bobas sutiks su klaidos galimybe skaičiuojant, tol galima garantuoti, kad jų informacija išliks saugi, kad programa paleidžiama tik vieną kartą, o paskui sunaikins save.

Mes sušvelniname vienkartinių programų apibrėžimą, kad išvestyje būtų tam tikra klaidų tikimybė ir parodytume, kad kvantinė mechanika suteikia saugumo pranašumų, palyginti su grynai klasikiniais ištekliais, sako mokslininkai.

Požiūris yra paprastas. Alisa slapta užkoduoja savo turtus kvantiniame kompiuteryje saugomų kubitų rinkinio būsenose. Šis kompiuteris užprogramuotas lyginti šį skaičių su Bobo įvestu skaičiumi ir pasakyti jam, ar jo turtas didesnis ar mažesnis nei Alisos.

Šis kvantinis apdorojimas pats savaime yra negrįžtamas procesas, ir tai neleidžia Bobui įvesti kitų skaičių, kad nustatytų Alisos turtą.

Tačiau aparatinė įranga yra fiksuota, o galimas šio metodo trūkumas yra tas, kad Bobas gali pakeisti programą, nustatydamas, kaip prijungti loginiai vartai.

Vis dėlto Roehsneris ir kiti turi gudrybę, kaip to išvengti. Nors jie negali paslėpti fizinių laidų, jie gali paslėpti tiesos lenteles, kurios valdo kiekvieno loginio vartelio elgesį. Taip yra todėl, kad mūsų požiūris yra užkoduoti atskirų vartų tiesos lentelę kaip vienkartinę programą, sako jie.

Tai leidžia užkoduoti Alisos informaciją tiksliai pasirenkant loginius vartus, o ne į ryšius tarp jų. Tokiu būdu jis lieka paslėptas nuo Bobo.

Roehsneris ir bendradarbiai išbandė šią idėją principo įrodymo eksperimente. Tai užkoduoja informaciją apie fotonų poliarizaciją ir apdoroja ją naudodama įvairius optinius loginius vartus. Vidutinė kiekvieno iš vartų sėkmės tikimybė yra 75 procentai, o tai, komandos teigimu, gerai sutampa su numatoma verte.

Tada komanda naudojo šią sąranką, kad išspręstų Yao milijonieriaus problemą skaičiams, sudarytiems iš keturių bitų, kurie skiriasi vienu bitu. Programa veikia lygindama kiekvieną bitą, kad nuspręstų, kuris yra didesnis.

Rezultatai leidžia įdomiai skaityti. Komanda teigia, kad sėkmės tikimybė didėja didėjant klaidų taisymui naudojamų bitų skaičiui, tačiau tai taip pat mažina sistemos saugumą. Taigi yra aiškus kompromisas tarp tikslumo ir saugumo. Nepaisant to, komanda teigia, kad saugumas yra geresnis, nei galima pasiekti naudojant vien klasikinį skaičiavimą.

Mūsų rezultatai rodo, kad kvantinė fizika leidžia pasiekti geresnių saugumo kompromisų atliekant tam tikras saugias skaičiavimo užduotis, nei įmanoma klasikiniame pasaulyje, net kai neįmanoma pasiekti tobulo saugumo, sako jie.

Be to, šis metodas tinka dabartinėms technologijoms, o palyginti nedidelė pažanga turėtų dar labiau padidinti saugumą.

Tai įdomus darbas, parodantis kvantinių technologijų potencialą žymiai padidinti saugumą naudojant šiandien prieinamas technologijas. Manome, kad pateiktame darbe stipriai užsimenama apie gausią kvantinių protokolų sritį, kad būtų padidintas klasikinio skaičiavimo saugumas, net prieš pradedant realizuoti didelio masto kvantinius kompiuterius, sako Roehsneris ir kt.

Bus įdomu pamatyti, kaip darbas bus priimtas.

Nuoroda: arxiv.org/abs/1709.09724 : Kvantinis pranašumas tikimybinėms vienkartinėms programoms

paslėpti