Advarsel: Denne algoritmen vil selvdestruere etter at den er brukt

Se for deg to millionærer – Alice og Bob – som ønsker å bestemme hvem som er rikest, men uten å avsløre rikdommen deres. Hvordan løser de gåten sin? Dette er Yaos millionærproblem, utviklet av informatikeren Andrew Yao i 1982.

En mulig løsning er et engangsdataprogram. Dette programmet lar Alice og Bob legge inn dataene sine privat, utfører beregningen én gang, gir svaret og ødelegger seg selv. Dette sikrer at ingen får tilgang til de originale dataene eller måten de ble behandlet på. Og det gir Alice og Bob svaret deres uten at det går på bekostning av deres økonomiske detaljer.

Datasikkerhetseksperter sier at engangsprogrammer er et enormt viktig verktøy innen cybersikkerhet. Eller de ville vært det hvis noen kunne bygge dem.

Det viser seg at det er umulig å bygge et ideelt engangsprogram som kjører en gang og deretter ødelegger seg selv. En klassisk datamaskin av denne typen må ødelegges fysisk for å sikre at den ikke kan brukes igjen, og det er ingen kjent måte å garantere dette på.

En kvantedatamaskin kan se ut til å tilby mer potensial, siden kvanteinformasjon lett blir ødelagt og umulig å kopiere. Men det viser seg at en kvantedatamaskin ikke kan gi et deterministisk svar på en engangsregning.

Så drømmen om et engangsprogram som ødelegger seg selv etter en enkelt utregning virker dødsdømt.

Gå inn Marie-Christine Roehsner ved Universitetet i Wien og Joshua Kettlewell ved National University of Singapore og noen få venner. I dag sier de at de har funnet en måte å bygge et engangsprogram på, og at de har bygget og demonstrert en proof-of-princip-enhet for første gang.

Den nye metoden er avhengig av en annen måte å tenke på engangsprogrammer utført av kvantedatamaskiner. Til nå har sikkerhetseksperter alltid forventet en definitiv løsning: Bobs verdi er enten mer eller mindre enn Alices.

Men kvantemekanikk er en iboende sannsynlighetsprosess, og det betyr at den bare kan gi det riktige svaret innenfor visse sannsynlighetsgrenser, si 75 prosent av tiden. Så lenge Alice og Bob er villige til å akseptere muligheten for en feil i beregningen, så er det mulig å garantere at informasjonen deres forblir sikker, at programmet kjører én gang og deretter ødelegger seg selv.

Vi slapper av definisjonen av engangsprogrammer for å tillate en viss sannsynlighet for feil i produksjonen og viser at kvantemekanikk gir sikkerhetsfordeler fremfor rent klassiske ressurser, sier forskerne.

Tilnærmingen er grei. Alice koder i hemmelighet for rikdommen hennes i statene til et sett med qubits lagret i en kvantedatamaskin. Denne datamaskinen er programmert til å sammenligne dette tallet med et som er skrevet inn av Bob og fortelle ham om formuen hans er større eller mindre enn Alices.

Denne kvanteprosesseringen er i seg selv en irreversibel prosess, og dette hindrer Bob i å skrive inn andre tall for å bestemme Alices formue.

Men maskinvaren er fikset og en potensiell svakhet ved denne tilnærmingen er at Bob kan reversere programmet ved å finne ut hvordan de logiske portene er kablet.

Roehsner og co har et triks for å forhindre dette. Selv om de ikke kan skjule de fysiske ledningene, kan de skjule sannhetstabellene som styrer oppførselen til hver logikkport. Dette er fordi vår tilnærming er å kode sannhetstabellen for individuelle porter som et engangsprogram i seg selv, sier de.

Dette gjør at Alices informasjon kan kodes i det nøyaktige valget av logiske porter og ikke i forbindelsene mellom dem. På denne måten forblir den skjult for Bob.

Roehsner og co har testet denne ideen i et proof-of-princip-eksperiment. Dette koder for informasjon i polariseringen av fotoner og behandler den ved hjelp av ulike typer optiske logiske porter. Gjennomsnittlig sannsynlighet for suksess for hver av portene er 75 prosent, noe teamet sier er i god overensstemmelse med forventet verdi.

Teamet brukte deretter dette oppsettet for å løse Yaos Millionaire-problem for tall som består av fire biter som avviker med en enkelt bit. Programmet fungerer ved å sammenligne hver bit for å avgjøre hvilken som er størst.

Resultatene gir interessant lesning. Teamet sier at sannsynligheten for suksess øker med antall biter som brukes til feilretting, men dette reduserer også sikkerheten til systemet. Så det er en klar avveining mellom nøyaktighet og sikkerhet. Likevel sier teamet at sikkerheten er bedre enn det som kan oppnås med klassisk databehandling alene.

Resultatene våre viser at kvantefysikk gir bedre sikkerhetsavveininger for visse sikre dataoppgaver enn det som er mulig i den klassiske verden, selv når perfekt sikkerhet ikke kan oppnås, sier de.

Dessuten er metoden brukbar med dagens teknologi, og relativt beskjedne fremskritt bør øke sikkerheten ytterligere.

Det er interessant arbeid som viser potensialet til kvanteteknologier for å dramatisk øke sikkerheten ved å bruke teknologi som er tilgjengelig i dag. Vi mener at det presenterte arbeidet peker sterkt på et rikt område av kvanteprotokoller for å øke sikkerheten til klassisk beregning, selv før storskala kvantedatamaskiner kan realiseres, sier Roehsner og co.

Det blir spennende å se hvordan arbeidet blir mottatt.

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

gjemme seg