Advarsel: Denne algoritme vil selvdestruere efter den er brugt

Forestil dig to millionærer – Alice og Bob – som ønsker at bestemme, hvem der er den rigere, men uden at afsløre deres rigdom. Hvordan løser de deres gåde? Dette er Yaos millionærproblem, udtænkt af datalogen Andrew Yao i 1982.

En mulig løsning er et engangscomputerprogram. Dette program giver Alice og Bob mulighed for at indtaste deres data privat, udfører beregningen én gang, giver svaret og ødelægger derefter sig selv. Dette sikrer, at ingen kan få adgang til de originale data eller den måde, de blev behandlet på. Og det giver Alice og Bob deres svar uden at gå på kompromis med deres økonomiske detaljer.

Computersikkerhedseksperter siger, at engangsprogrammer er et enormt vigtigt værktøj inden for cybersikkerhed. Eller det ville de være, hvis nogen kunne bygge dem.

Det viser sig, at det er umuligt at bygge et ideelt engangsprogram, der kører én gang og derefter ødelægger sig selv. En klassisk computer af denne art skal destrueres fysisk for at sikre, at den ikke kan bruges igen, og der er ingen kendt måde at garantere dette på.

En kvantecomputer kan synes at tilbyde mere potentiale, da kvanteinformation let ødelægges og umulig at kopiere. Men det viser sig, at en kvantecomputer ikke kan give et deterministisk svar på en engangsregning.

Så drømmen om et engangsprogram, der ødelægger sig selv efter en enkelt beregning, virker dødsdømt.

Indtast Marie-Christine Roehsner på universitetet i Wien og Joshua Kettlewell på National University of Singapore og et par venner. I dag siger de, at de har fundet en måde at bygge et engangsprogram på og har bygget og demonstreret en proof-of-principle enhed for første gang.

Den nye metode bygger på en anden måde at tænke engangsprogrammer på udført af kvantecomputere. Indtil nu har sikkerhedseksperter altid forventet en endelig løsning: Bobs værd er enten mere eller mindre end Alices.

Men kvantemekanik er en iboende probabilistisk proces, og det betyder, at den kun kan give det rigtige svar inden for visse sandsynlighedsgrænser, f.eks. 75 procent af tiden. Så længe Alice og Bob er villige til at acceptere muligheden for en fejl i beregningen, så er det muligt at garantere, at deres oplysninger forbliver sikre, at programmet kun kører én gang og derefter ødelægger sig selv.

Vi slækker på definitionen af ​​engangsprogrammer for at tillade en vis sandsynlighed for fejl i outputtet og viser, at kvantemekanik tilbyder sikkerhedsfordele i forhold til rent klassiske ressourcer, siger forskerne.

Fremgangsmåden er ligetil. Alice koder i hemmelighed sin rigdom i staterne af et sæt qubits gemt i en kvantecomputer. Denne computer er programmeret til at sammenligne dette tal med et indtastet af Bob og til at fortælle ham, om hans rigdom er større eller mindre end Alices.

Denne kvantebehandling er i sig selv en irreversibel proces, og dette forhindrer Bob i at indtaste andre tal for at bestemme Alices rigdom.

Men hardwaren er fikset, og en potentiel svaghed ved denne tilgang er, at Bob kan omdanne programmet ved at finde ud af, hvordan de logiske porte er forbundet.

Roehsner og co har dog et trick for at forhindre dette. Selvom de ikke kan skjule de fysiske ledninger, kan de skjule de sandhedstabeller, der styrer adfærden for hver logikport. Dette skyldes, at vores tilgang er at indkode sandhedstabellen for individuelle porte som et engangsprogram i sig selv, siger de.

Dette gør det muligt at kode Alices information i det præcise valg af logiske porte og ikke på forbindelserne mellem dem. På denne måde forbliver det skjult for Bob.

Roehsner og co har testet denne idé i et proof-of-principle eksperiment. Dette koder information i polariseringen af ​​fotoner og behandler det ved hjælp af forskellige slags optiske logiske porte. Den gennemsnitlige sandsynlighed for succes for hver af portene er 75 procent, hvilket teamet siger er i god overensstemmelse med den forventede værdi.

Holdet brugte derefter dette opsætning til at løse Yaos Millionær-problem for tal bestående af fire bits, der adskiller sig med en enkelt bit. Programmet fungerer ved at sammenligne hver bit for at afgøre, hvilken der er størst.

Resultaterne giver interessant læsning. Holdet siger, at sandsynligheden for succes stiger med antallet af bits, der bruges til fejlkorrektion, men dette reducerer også systemets sikkerhed. Så der er en klar afvejning mellem nøjagtighed og sikkerhed. Ikke desto mindre siger teamet, at sikkerheden er bedre, end der kan opnås med klassisk databehandling alene.

Vores resultater viser, at kvantefysik giver mulighed for bedre sikkerhedsafvejninger for visse sikre computeropgaver, end det er muligt i den klassiske verden, selv når perfekt sikkerhed ikke kan opnås, siger de.

Desuden er metoden brugbar med den nuværende teknologi, og relativt beskedne fremskridt burde øge sikkerheden yderligere.

Det er interessant arbejde, der viser potentialet i kvanteteknologier til dramatisk at øge sikkerheden ved hjælp af teknologi, der er tilgængelig i dag. Vi mener, at det præsenterede arbejde antyder et rigt område af kvanteprotokoller for at øge sikkerheden ved klassisk beregning, selv før storskala kvantecomputere kan realiseres, siger Roehsner og co.

Det bliver spændende at se, hvordan arbejdet bliver modtaget.

Ref: arxiv.org/abs/1709.09724 : Quantum Advantage for probabilistiske engangsprogrammer

skjule