Varning: Denna algoritm kommer att förstöra sig själv efter att den har använts

Föreställ dig två miljonärer – Alice och Bob – som vill bestämma vem som är rikare men utan att avslöja sin rikedom. Hur går de tillväga för att lösa sin gåta? Detta är Yaos Millionaire Problem, utarbetat av datavetaren Andrew Yao 1982.

En möjlig lösning är ett engångsdatorprogram. Detta program låter Alice och Bob ange sina data privat, utför beräkningen en gång, ger svaret och förstör sedan sig själv. Detta säkerställer att ingen kan komma åt originaldata eller hur de behandlades. Och det ger Alice och Bob deras svar utan att kompromissa med deras ekonomiska detaljer.

Datasäkerhetsexperter säger att engångsprogram är ett oerhört viktigt verktyg inom cybersäkerhet. Eller så skulle de vara det, om någon kunde bygga dem.

Det visar sig att det är omöjligt att bygga ett idealiskt engångsprogram som körs en gång och sedan förstör sig själv. En klassisk dator av detta slag skulle behöva förstöras fysiskt för att säkerställa att den inte kan användas igen, och det finns inget känt sätt att garantera detta.

En kvantdator kan tyckas erbjuda mer potential, eftersom kvantinformation lätt förstörs och omöjlig att kopiera. Men det visar sig att en kvantdator inte kan ge ett deterministiskt svar på en engångsberäkning.

Så drömmen om ett engångsprogram som förstör sig själv efter en enda beräkning verkar dödsdömd.

Ange Marie-Christine Roehsner vid universitetet i Wien och Joshua Kettlewell vid National University of Singapore och några kompisar. Idag säger de att de har hittat ett sätt att bygga ett engångsprogram och att de har byggt och demonstrerat en proof-of-principe-enhet för första gången.

Den nya metoden bygger på ett annat sätt att tänka på engångsprogram som utförs av kvantdatorer. Fram till nu har säkerhetsexperter alltid förväntat sig en definitiv lösning: Bobs värde är antingen mer eller mindre än Alices.

Men kvantmekaniken är en i sig sannolikhetsprocess, och det betyder att den bara kan ge det rätta svaret inom vissa sannolikhetsgränser, säg 75 procent av tiden. Så länge Alice och Bob är villiga att acceptera möjligheten av ett fel i beräkningen, då är det möjligt att garantera att deras information förblir säker, att programmet körs en gång och sedan förstör sig själv.

Vi lättar på definitionen av engångsprogram för att tillåta viss sannolikhet för fel i produktionen och visar att kvantmekaniken erbjuder säkerhetsfördelar jämfört med rent klassiska resurser, säger forskarna.

Tillvägagångssättet är okomplicerat. Alice kodar i hemlighet sin rikedom i delstaterna för en uppsättning qubits lagrade i en kvantdator. Den här datorn är programmerad att jämföra detta nummer med ett som Bob angett och tala om för honom om hans rikedom är större eller mindre än Alices.

Denna kvantbearbetning är i sig en oåterkallelig process, och detta hindrar Bob från att ange andra siffror för att bestämma Alices rikedom.

Men hårdvaran är fixad och en potentiell svaghet med detta tillvägagångssätt är att Bob kan reverse-engineera programmet genom att ta reda på hur de logiska grindarna är kopplade.

Roehsner och co har dock ett knep för att förhindra detta. Även om de inte kan dölja de fysiska ledningarna, kan de dölja sanningstabellerna som styr beteendet för varje logisk grind. Detta beror på att vårt tillvägagångssätt är att koda sanningstabellen för enskilda grindar som ett engångsprogram i sig, säger de.

Detta gör att Alices information kan kodas i det exakta valet av logiska grindar och inte i anslutningarna mellan dem. På så sätt förblir den dold för Bob.

Roehsner och co har testat denna idé i ett proof-of-principe-experiment. Detta kodar information i polariseringen av fotoner och bearbetar den med hjälp av olika typer av optiska logiska grindar. Den genomsnittliga sannolikheten för framgång för var och en av portarna är 75 procent, vilket teamet säger stämmer väl överens med det förväntade värdet.

Teamet använde sedan denna uppsättning för att lösa Yaos miljonärsproblem för siffror som består av fyra bitar som skiljer sig med en enda bit. Programmet fungerar genom att jämföra varje bit för att avgöra vilken som är större.

Resultaten ger intressant läsning. Teamet säger att sannolikheten för framgång ökar med antalet bitar som används för felkorrigering, men detta minskar också säkerheten i systemet. Så det finns en tydlig avvägning mellan noggrannhet och säkerhet. Ändå säger teamet att säkerheten är bättre än vad som kan uppnås med enbart klassisk datoranvändning.

Våra resultat visar att kvantfysiken möjliggör bättre säkerhetsavvägningar för vissa säkra datoruppgifter än vad som är möjligt i den klassiska världen, även när perfekt säkerhet inte kan uppnås, säger de.

Dessutom är metoden användbar med nuvarande teknik, och relativt blygsamma framsteg borde öka säkerheten ytterligare.

Det är intressant arbete som visar potentialen hos kvantteknologier för att dramatiskt öka säkerheten med teknik som är tillgänglig idag. Vi tror att det presenterade arbetet ger en stark antydan om ett rikt område av kvantprotokoll för att förbättra säkerheten för klassisk beräkning, även innan storskaliga kvantdatorer kan realiseras, säger Roehsner och co.

Det ska bli intressant att se hur arbetet tas emot.

Ref: arxiv.org/abs/1709.09724 : Quantum Advantage för probabilistiska engångsprogram

Dölj