Brīdinājums: šis algoritms pašiznīcināsies pēc tā izmantošanas

Iedomājieties divus miljonārus — Alisi un Bobu —, kuri vēlas izlemt, kurš ir bagātāks, bet neatklāj savu bagātību. Kā viņi risina savu mīklu? Šī ir Jao miljonāra problēma, ko 1982. gadā izstrādāja datorzinātnieks Endrjū Jao.

Viens no iespējamiem risinājumiem ir vienreizēja datorprogramma. Šī programma ļauj Alisei un Bobam privāti ievadīt savus datus, vienreiz veic aprēķinu, sniedz atbildi un pēc tam iznīcina sevi. Tas nodrošina, ka neviens nevar piekļūt sākotnējiem datiem vai veidam, kā tie tika apstrādāti. Un tas sniedz Alisei un Bobam atbildi, neapdraudot viņu finanšu informāciju.

Datoru drošības eksperti saka, ka vienreizējās programmas ir ļoti svarīgs kiberdrošības instruments. Vai arī tie būtu, ja kāds varētu tos uzbūvēt.

Izrādās, ka nav iespējams izveidot ideālu vienreizēju programmu, kas vienreiz palaistu un pēc tam pati sevi iznīcina. Šāda veida klasiskais dators būtu fiziski jāiznīcina, lai to vairs nevarētu izmantot, un nav zināms veids, kā to garantēt.

Šķiet, ka kvantu dators piedāvā lielāku potenciālu, jo kvantu informācija ir viegli iznīcināma un to nav iespējams kopēt. Bet izrādās, ka kvantu dators nevar sniegt deterministisku atbildi uz vienreizēju aprēķinu.

Tāpēc sapnis par vienreizēju programmu, kas pati sevi iznīcina pēc viena aprēķina, šķiet lemts.

Ienāciet Marija Kristīne Roehsnere Vīnes Universitātē un Džošua Ketlvela Singapūras Nacionālajā universitātē un daži draugi. Šodien viņi saka, ka ir atraduši veidu, kā izveidot vienreizēju programmu, un pirmo reizi ir izveidojuši un demonstrējuši principiālu ierīci.

Jaunā metode balstās uz atšķirīgu domāšanas veidu par vienreizējām programmām, ko veic kvantu datori. Līdz šim drošības eksperti vienmēr ir gaidījuši galīgu risinājumu: Boba vērtība ir lielāka vai mazāka nekā Alise.

Bet kvantu mehānika pēc būtības ir varbūtības process, un tas nozīmē, ka tā var sniegt pareizo atbildi tikai noteiktās varbūtības robežās, piemēram, 75 procentos gadījumu. Kamēr Alise un Bobs ir gatavi pieņemt kļūdas iespējamību aprēķinos, tad ir iespējams garantēt, ka viņu informācija paliks drošībā, ka programma darbosies tikai vienu reizi un pēc tam iznīcinās pati sevi.

Mēs atvieglojam vienreizējo programmu definīciju, lai pieļaujam zināmu kļūdu iespējamību izvadē un parādītu, ka kvantu mehānika piedāvā drošības priekšrocības salīdzinājumā ar tīri klasiskajiem resursiem, saka pētnieki.

Pieeja ir vienkārša. Alise slepeni iekodē savu bagātību kvantu datorā saglabāto kubitu kopas stāvokļos. Šis dators ir ieprogrammēts, lai salīdzinātu šo skaitli ar Boba ievadīto skaitli un pateiktu viņam, vai viņa bagātība ir lielāka vai mazāka par Alises bagātību.

Šī kvantu apstrāde pati par sevi ir neatgriezenisks process, un tas neļauj Bobam ievadīt citus skaitļus, lai noteiktu Alises bagātību.

Taču aparatūra ir fiksēta, un šīs pieejas iespējamā vājā puse ir tāda, ka Bobs var mainīt programmu, izstrādājot loģisko vārtu savienojuma veidu.

Tomēr Roehsneram un citiem ir kāds triks, kā to novērst. Lai gan tie nevar paslēpt fizisko vadu, tie var paslēpt patiesības tabulas, kas nosaka katra loģikas vārtu darbību. Tas ir tāpēc, ka mūsu pieeja ir iekodēt patiesības tabulu atsevišķiem vārtiem kā vienreizēju programmu, viņi saka.

Tas ļauj kodēt Alises informāciju precīzā loģisko vārtu izvēlē, nevis savienojumos starp tiem. Tādā veidā tas paliek paslēpts no Boba.

Roehsner un citi ir pārbaudījuši šo ideju principa pierādījuma eksperimentā. Tas kodē informāciju fotonu polarizācijā un apstrādā to, izmantojot dažāda veida optiskās loģikas vārtus. Vidējā veiksmes iespējamība katram no vārtiem ir 75 procenti, kas, pēc komandas domām, labi saskan ar paredzamo vērtību.

Pēc tam komanda izmantoja šo iestatījumu, lai atrisinātu Yao's Millionaire problēmu skaitļiem, kas sastāv no četriem bitiem, kas atšķiras par vienu bitu. Programma darbojas, salīdzinot katru bitu, lai izlemtu, kurš ir lielāks.

Rezultāti rada interesantu lasīšanu. Komanda saka, ka panākumu iespējamība palielinās līdz ar kļūdu labošanai izmantoto bitu skaitu, taču tas arī samazina sistēmas drošību. Tātad pastāv skaidrs kompromiss starp precizitāti un drošību. Tomēr komanda saka, ka drošība ir labāka, nekā to var panākt tikai ar klasisko skaitļošanu.

Mūsu rezultāti parāda, ka kvantu fizika nodrošina labākus drošības kompromisus noteiktiem drošiem skaitļošanas uzdevumiem, nekā tas ir iespējams klasiskajā pasaulē, pat ja nav iespējams sasniegt perfektu drošību, viņi saka.

Turklāt šī metode ir izmantojama ar pašreizējām tehnoloģijām, un salīdzinoši nelielam progresam vajadzētu vēl vairāk palielināt drošību.

Tas ir interesants darbs, kas parāda kvantu tehnoloģiju potenciālu dramatiski palielināt drošību, izmantojot šodien pieejamo tehnoloģiju. Mēs uzskatām, ka iesniegtais darbs stingri norāda uz bagātīgu kvantu protokolu jomu, lai uzlabotu klasisko aprēķinu drošību, pat pirms liela mēroga kvantu datori var tikt realizēti, saka Roehsner un co.

Būs interesanti redzēt, kā darbs tiks uztverts.

Atsauce: arxiv.org/abs/1709.09724 : Quantum Advantage varbūtības vienreizējām programmām

paslēpties