Huijia Lin bewees dat een meesterlijk hulpmiddel voor cryptografie mogelijk is

Een lang gezochte “heilige graal” in cryptografie staat klaar om de manier waarop we gevoelige informatie beschermen te veranderen.

De standaardencryptieschema’s van tegenwoordig hebben een alles-of-niets-benadering. Eenmaal versleuteld, worden uw gegevens ontoegankelijk voor iedereen zonder de geheime sleutel.

Dit heeft gezorgd voor veilige e-mailcommunicatie, de wildgroei aan online transacties en digitale handtekeningen. Hiermee kunnen belasting- en medische dossiers met gevoelige persoonlijke informatie veiliger via internet worden doorgegeven. Maar als je iemand de geheime sleutel geeft om toegang te krijgen tot een van de gegevens, worden alle gegevens kwetsbaar.

Wat als u in plaats daarvan specifieke mensen toegang zou kunnen geven om zeer specifieke dingen met uw gegevens te doen? Iemand kan de informatie krijgen die ze nodig hebben (de informatie die u wilt dat ze hebben) zonder alle originele gegevens te ontgrendelen. Bankgegevens, creditcardnummers, accountwachtwoorden – alles zou verborgen blijven. Die geheel andere benadering zou Netflix ook in staat kunnen stellen om show-aanbevelingen te doen zonder bijvoorbeeld je volledige kijkgeschiedenis te zien. Google kan uw e-mails sorteren zonder te weten wat erin staat. En medische onderzoekers kunnen gegevens analyseren om risicofactoren voor een ziekte te identificeren zonder toegang te hebben tot de gezondheidsinformatie van een persoon.

Deze en andere cryptografische wonderen lijken nu mogelijk te zijn door middel van een mastertool genaamd indistinguishability obfuscation.

“Het is een nieuw hulpmiddel – een zeer krachtig hulpmiddel”, zegt cryptograaf Huijia (Rachel) Lin van de Universiteit van Washington in Seattle, die liet in 2020 met collega’s zien hoe de tool te bouwen. “Als je eenmaal deze supersterke kracht hebt, dan zijn veel van de andere taken of speciale gevallen ervan, of je kunt dit gemakkelijk gebruiken om te realiseren [those tasks].”

Vinod Vaikuntanathan, een computerwetenschapper aan het MIT die met Lin aan eerder onderzoek heeft gewerkt, vergelijkt ononderscheidbaarheidsverduistering, of iO, met een grootse theorie in de natuurkunde die zwaartekracht en kwantummechanica zou verenigen. “iO geeft je een manier om een ​​grootse unificatie van cryptografie te doen, in die zin dat je veel van wat cryptografie doet op een heel eenvoudige manier kunt uitleggen.”

Opvallend onderzoek

Ononderscheidbaarheidsverduistering is een vorm van programmaverduistering, een benadering die de innerlijke werking van een computerprogramma probeert te verbergen, niet alleen het bericht of de gegevens zelf. Hoewel voorgesteld in 1976 in een paper dat de basis legde voor moderne cryptografie, bleek programmaverduistering moeilijk te bereiken. Jarenlang dachten mensen dat het misschien niet mogelijk was.

En in 2001 toonden onderzoekers aan dat volledige verduistering van programma’s – black-box-verduistering genoemd, waarbij invoer- en uitvoergegevens bekend zijn maar niets anders over een programma kan worden ontdekt – onmogelijk is. Maar verduistering van niet-onderscheidbaarheid, die tegelijkertijd wordt voorgesteld en als ongelooflijk krachtig blijkt te zijn, vereist niet dat alles over een programma blijven verborgen. Het behandelt in plaats daarvan twee programma’s die dezelfde functie uitvoeren. Als de innerlijke werking van die twee programma’s voldoende kan worden verborgen dat de twee niet van elkaar kunnen worden onderscheiden, is ononderscheidbaarheid verduistering bereikt. Door de geheime sleutel in het programma zelf te verbergen, maakt iO het delegeren van specifieke gegevens en gegevenstaken aan specifieke mensen mogelijk.

Toch bleek voorstel na voorstel om iO te laten werken breekbaar. Onderzoekers konden er niet achter komen hoe ze het konden beschermen tegen de aanvallen van een tegenstander. Lin zegt dat de benaderingen die werden gebruikt haar niet aanspraken. Onderzoekers leunden op wat “goed genoeg” manieren leken om het probleem aan te pakken die niet werden ondersteund door rigoureuze wiskundige bewijzen.

Lin wilde in plaats daarvan het probleem opsplitsen, zodat ze elk onderdeel kon begrijpen en hoe ze samenwerkten. Ze wilde het probleem benaderen als een klok, met tandwielen en bouten en moeren, in plaats van verward als ‘een kom spaghetti’.

Door deze strategie, Lin, samen met Amit Sahai van UCLA en Aayush Jain, een Ph.D. destijds student aan UCLA, toonde aan dat iO haalbaar is. Het zou veilig zijn op basis van standaardaannames in het veld, zo bewees het team, en hernieuwde hoop in de tool.

“Natuurlijk, [Huijia] is briljant,” zegt Vaikuntanathan, eraan toevoegend dat haar doorzettingsvermogen haar echt onderscheidt. “Er is wat lef voor nodig om door te gaan met een aanpak terwijl in wezen de hele rest van de wereld denkt dat het niet gaat werken.”

achtergrondverhaal

Lin zegt dat ze niet op jonge leeftijd is opgegroeid met computers of verliefd is geworden op computerprogrammering. Als student was ze geïnteresseerd in natuurkunde en streefde ze ernaar overal goed in te zijn. Ze begon met informatica op de universiteit; een klasse in cryptografie als Ph.D. student aan de Cornell University “was echt geestverruimend”, zegt ze. Haar inleiding tot wat bekend staat als nul-kennis bewijzen staat in haar herinnering.

Een zero-knowledge proof zegt dat een persoon iemand anders kan overtuigen dat hij een geheim kent zonder het geheim of enige details erover te onthullen. Stel dat u bijvoorbeeld wist dat een getal het product is van twee priemgetallen. Kun je iemand ervan overtuigen dat het waar is zonder te onthullen wat de priemgetallen zijn? Hoe te bewijzen dat zo’n taak mogelijk is, fascineerde Lin.

Cryptografie bevat veel van deze schijnbare paradoxen die mogelijk blijken te zijn. Ononderscheidbaarheidsverduistering is nog een ander voorbeeld – en Lin werkt aan andere, waaronder beveiligde multiparty-berekening, waarmee een computertaak de gegevens van meerdere mensen kan doorlopen zonder dat iemand zijn gegevens aan iemand in de groep of aan een derde hoeft te onthullen.

“Ik voel me erg aangetrokken tot deze magische concepten”, zegt Lin. “Het leuke ervan is om dit concept te realiseren.”

Ononderscheidbaarheid verduistering is nog verre van real-world implementatie. Maar Vaikuntanathan zegt dat het niet ongebruikelijk is dat de eerste constructies van wat belangrijke benaderingen zullen worden in eerste instantie onpraktisch zijn. “Wacht een decennium”, zegt hij.

Wil je iemand nomineren voor de volgende SN 10 lijst? Stuur hun naam, affiliatie en een paar zinnen over hen en hun werk naar sn10@sciencenews.org.