211service.com
Waarschuwing: dit algoritme vernietigt zichzelf nadat het is gebruikt
Stel je twee miljonairs voor - Alice en Bob - die willen beslissen wie de rijker is, maar zonder hun rijkdom te onthullen. Hoe lossen ze hun raadsel op? Dit is Yao's Millionaire Problem, bedacht door de computerwetenschapper Andrew Yao in 1982.
Een mogelijke oplossing is een eenmalig computerprogramma. Met dit programma kunnen Alice en Bob hun gegevens privé invoeren, de berekening eenmaal uitvoeren, het antwoord geven en zichzelf vervolgens vernietigen. Dit zorgt ervoor dat niemand toegang heeft tot de originele gegevens of de manier waarop deze zijn verwerkt. En het geeft Alice en Bob hun antwoord zonder hun financiële gegevens in gevaar te brengen.
Computerbeveiligingsexperts zeggen dat eenmalige programma's een enorm belangrijk hulpmiddel zijn in cyberbeveiliging. Of dat zouden ze zijn, als iemand ze zou kunnen bouwen.
Het blijkt dat het onmogelijk is om een ideaal eenmalig programma te bouwen dat één keer draait en zichzelf vervolgens vernietigt. Een dergelijke klassieke computer zou fysiek vernietigd moeten worden om ervoor te zorgen dat hij niet opnieuw kan worden gebruikt, en er is geen bekende manier om dit te garanderen.
Een kwantumcomputer lijkt misschien meer potentieel te bieden, omdat kwantuminformatie gemakkelijk wordt vernietigd en onmogelijk te kopiëren is. Maar het blijkt dat een kwantumcomputer geen deterministisch antwoord kan geven op een eenmalige berekening.
Dus de droom van een eenmalig programma dat zichzelf vernietigt na een enkele berekening lijkt gedoemd te mislukken.
Voer Marie-Christine Roehsner aan de Universiteit van Wenen en Joshua Kettlewell aan de Nationale Universiteit van Singapore en een paar vrienden in. Vandaag zeggen ze dat ze een manier hebben gevonden om een eenmalig programma te bouwen en voor het eerst een proof-of-principle-apparaat hebben gebouwd en gedemonstreerd.
De nieuwe methode is gebaseerd op een andere manier van denken over eenmalige programma's die worden uitgevoerd door kwantumcomputers. Tot nu toe hebben beveiligingsexperts altijd een definitieve oplossing verwacht: de waarde van Bob is meer of minder dan die van Alice.
Maar kwantummechanica is een inherent probabilistisch proces, en dat betekent dat het alleen het juiste antwoord kan geven binnen bepaalde grenzen van waarschijnlijkheid, zeg 75 procent van de tijd. Zolang Alice en Bob bereid zijn om de mogelijkheid van een fout in de berekening te accepteren, is het mogelijk om te garanderen dat hun informatie veilig blijft, dat het programma eenmalig draait en zichzelf vervolgens vernietigt.
We versoepelen de definitie van eenmalige programma's om enige kans op fouten in de uitvoer toe te staan en laten zien dat kwantummechanica beveiligingsvoordelen biedt ten opzichte van puur klassieke bronnen, aldus de onderzoekers.
De aanpak is rechttoe rechtaan. Alice codeert in het geheim haar rijkdom in de toestanden van een reeks qubits die zijn opgeslagen in een kwantumcomputer. Deze computer is geprogrammeerd om dit getal te vergelijken met het getal dat Bob heeft ingevoerd en om hem te vertellen of zijn vermogen groter of kleiner is dan dat van Alice.
Deze kwantumverwerking is zelf een onomkeerbaar proces en dit voorkomt dat Bob andere getallen invoert om de rijkdom van Alice te bepalen.
Maar de hardware is gerepareerd en een mogelijke zwakte van deze aanpak is dat Bob het programma kan reverse-engineeren door uit te zoeken hoe de logische poorten zijn aangesloten.
Roehsner en co hebben echter een truc om dit te voorkomen. Hoewel ze de fysieke bedrading niet kunnen verbergen, kunnen ze de waarheidstabellen verbergen die het gedrag van elke logische poort bepalen. Dit komt omdat onze benadering is om de waarheidstabel voor individuele poorten te coderen als een eenmalig programma op zich, zeggen ze.
Hierdoor kan de informatie van Alice worden gecodeerd in de precieze keuze van logische poorten en niet in de verbindingen daartussen. Zo blijft het verborgen voor Bob.
Roehsner en co hebben dit idee getest in een proof-of-principle-experiment. Dit codeert informatie in de polarisatie van fotonen en verwerkt deze met behulp van verschillende soorten optische logische poorten. De gemiddelde kans op succes voor elk van de poorten is 75 procent, wat volgens het team goed overeenkomt met de verwachte waarde.
Het team gebruikte deze opstelling vervolgens om het miljonairsprobleem van Yao op te lossen voor getallen die uit vier bits bestaan die een enkel bit verschillen. Het programma werkt door elk bit te vergelijken om te beslissen welke groter is.
De resultaten zorgen voor interessante lectuur. Het team zegt dat de kans op succes toeneemt met het aantal bits dat wordt gebruikt voor foutcorrectie, maar dit vermindert ook de veiligheid van het systeem. Er is dus een duidelijke afweging tussen nauwkeurigheid en veiligheid. Desalniettemin zegt het team dat de beveiliging beter is dan alleen met klassiek computergebruik kan worden bereikt.
Onze resultaten tonen aan dat de kwantumfysica betere compromissen op het gebied van beveiliging mogelijk maakt voor bepaalde veilige computertaken dan mogelijk is in de klassieke wereld, zelfs wanneer perfecte beveiliging niet kan worden bereikt, zeggen ze.
Bovendien is de methode werkbaar met de huidige technologie, en relatief bescheiden vooruitgang zou de veiligheid verder moeten vergroten.
Dat is interessant werk dat het potentieel van kwantumtechnologieën laat zien om de beveiliging drastisch te verhogen met behulp van technologie die vandaag beschikbaar is. We zijn van mening dat het gepresenteerde werk een sterke aanwijzing is voor een rijk gebied van kwantumprotocollen om de beveiliging van klassieke berekeningen te verbeteren, zelfs voordat grootschalige kwantumcomputers kunnen worden gerealiseerd, zeggen Roehsner en co.
Het zal interessant zijn om te zien hoe het werk wordt ontvangen.
Referentie: arxiv.org/abs/1709.09724 : Kwantumvoordeel voor probabilistische eenmalige programma's