Kryptografer utvecklar ett tillvägagångssätt för total söksekretess | Quanta Magazine

Vi vet alla att vi ska vara försiktiga med detaljerna vi delar online, men informationen vi söker kan också vara avslöjande. Sök efter vägbeskrivningar och vår plats blir mycket lättare att gissa. Sök efter ett lösenord i en mängd komprometterad data, så riskerar vi att läcka det själva.

Dessa situationer ger upphov till en nyckelfråga inom kryptografi: Hur kan du hämta information från en offentlig databas utan att avslöja något om vad du har kommit åt? Det motsvarar att kolla in en bok från biblioteket utan att bibliotekarien vet vilken.

Att skapa en strategi som löser detta problem - känd som privat informationsinhämtning - är "en mycket användbar byggsten i ett antal integritetsbevarande applikationer", sa David Wu, en kryptograf vid University of Texas, Austin. Sedan 1990-talet har forskare slängt iväg frågan och förbättrat strategier för privat åtkomst till databaser. Ett stort mål, fortfarande omöjligt med stora databaser, är motsvarigheten till en privat Google-sökning, där du kan sålla igenom en hög med data anonymt utan att göra några tunga beräkningslyft.

Nu har tre forskare gjort det tillverkad en länge eftersökt version av privat informationshämtning och utökade den för att bygga en mer allmän sekretessstrategi. Verket, som fick en Pris för bästa papper i juni på den årliga Symposium om datorteori, välter en stor teoretisk barriär på vägen till en verkligt privat sökning.

"[Detta är] något inom kryptografi som jag antar att vi alla ville ha men som inte riktigt trodde att det existerade," sa Vinod Vaikuntanathan, en kryptograf vid Massachusetts Institute of Technology som inte var involverad i tidningen. "Det är ett landmärkeresultat."

Problemet med privat databasåtkomst tog form på 1990-talet. Först antog forskarna att den enda lösningen var att skanna hela databasen under varje sökning, vilket skulle vara som att låta en bibliotekarie leta igenom varje hylla innan han återvände med din bok. När allt kommer omkring, om sökningen hoppade över något avsnitt, skulle bibliotekarien veta att din bok inte finns i den delen av biblioteket.

Det tillvägagångssättet fungerar tillräckligt bra i mindre skalor, men när databasen växer, växer den tid som krävs för att skanna den åtminstone proportionellt. När du läser från större databaser – och internet är en ganska stor sådan – blir processen oöverkomligt ineffektiv.

I början av 2000-talet började forskare misstänka att de kunde undvika fullskanningsbarriären genom att "förbearbeta" databasen. Grovt sett skulle detta innebära att man kodar hela databasen som en speciell struktur, så att servern kan svara på en fråga genom att bara läsa en liten del av den strukturen. Noggrann nog förbearbetning skulle i teorin kunna innebära att en enda servervärdinformation bara går igenom processen en gång, av sig själv, vilket gör att alla framtida användare kan ta information privat utan mer ansträngning.

För Daniel Wichs, en kryptograf vid Northeastern University och en medförfattare till den nya tidningen, som verkade för bra för att vara sant. Runt 2011 började han försöka bevisa att den här typen av upplägg var omöjligt. "Jag var övertygad om att det inte finns något sätt att detta skulle kunna göras," sa han.

Men under 2017 två grupper av forskare publicerade resultat som ändrade hans uppfattning. De byggde de första programmen som kunde göra den här typen av privat informationshämtning, men de kunde inte visa att programmen var säkra. (Kryptografer demonstrerar ett systems säkerhet genom att visa att det är lika svårt att bryta det som att lösa något svårt problem. Forskarna kunde inte jämföra det med ett kanoniskt svårt problem.)

Så även med sitt hopp förnyat antog Wichs att varje version av dessa program som var säker fortfarande var långt borta. Istället, han och hans medförfattare - Wei-Kai Lin, nu vid University of Virginia, och Ethan Mook, också på Northeastern — arbetade med problem som de trodde skulle vara lättare, vilket involverade fall där flera servrar är värd för databasen.

I de metoder de studerat kan informationen i databasen omvandlas till ett matematiskt uttryck, som servrarna kan utvärdera för att extrahera informationen. Författarna tänkte att det kunde vara möjligt att göra den utvärderingsprocessen mer effektiv. De lekte med en idé från 2011, då andra forskare hade hittat ett sätt att snabbt utvärdera ett sådant uttryck genom att förbearbeta det, skapa speciella, kompakta värdetabeller som låter dig hoppa över de normala utvärderingsstegen.

Den metoden gav inga förbättringar, och gruppen var nära att ge upp - tills de undrade om det här verktyget faktiskt kunde fungera i det eftertraktade enserverfallet. Välj ett polynom tillräckligt noggrant, såg de, och en enda server kunde förbehandla det baserat på 2011 års resultat – vilket ger det säkra, effektiva uppslagsschemat som Wichs hade funderat på i flera år. Plötsligt hade de trots allt löst det svårare problemet.

Till en början trodde inte författarna på det. "Låt oss ta reda på vad som är fel med det här," mindes Wichs att han tänkte. "Vi fortsatte att försöka lista ut var det går sönder."

Men lösningen höll: De hade verkligen upptäckt ett säkert sätt att förbearbeta en databas med en enda server så att vem som helst kunde hämta information i hemlighet. "Det är verkligen bortom allt vi hade hoppats på," sa Yuval Ishai, en kryptograf vid Technion i Israel som inte var involverad i detta arbete. Det är ett resultat "vi var inte ens modiga nog att be om", sa han.

Efter att ha byggt sitt hemliga uppslagsschema vände sig författarna till det verkliga målet med en privat internetsökning, vilket är mer komplicerat än att hämta informationsbitar från en databas, sa Wichs. Det privata uppslagsschemat i sig tillåter visserligen en version av privat Google-liknande sökning, men det är extremt arbetskrävande: Du kör Googles algoritm själv och hämtar i hemlighet data från internet när det behövs. Wichs sa att en sann sökning, där du skickar en förfrågan och luta dig tillbaka medan servern samlar in resultaten, verkligen är ett mål för ett bredare tillvägagångssätt som kallas homomorf kryptering, som döljer data så att någon annan kan manipulera det utan att någonsin veta något om det .

Typiska homomorfa krypteringsstrategier skulle träffa samma problem som privat informationshämtning, och gå igenom allt innehåll på internet för varje sökning. Men genom att använda sin privata uppslagsmetod som byggnadsställningar, konstruerade författarna ett nytt schema som kör beräkningar som är mer som de program vi använder varje dag, drar information i hemlighet utan att sopa hela internet. Det skulle ge en effektivitetshöjning för internetsökningar och alla program som behöver snabb tillgång till data.

Även om homomorf kryptering är en användbar förlängning av det privata uppslagsschemat, sa Ishai, att han ser privat informationshämtning som det mer grundläggande problemet. Författarnas lösning är den "magiska byggstenen", och deras homomorfa krypteringsstrategi är en naturlig uppföljning.

För närvarande är ingetdera schemat praktiskt användbart: Förbearbetning hjälper för närvarande i ytterligheterna, när databasens storlek ballonger mot oändligheten. Men att faktiskt implementera det innebär att dessa besparingar inte kan realiseras, och processen skulle äta upp för mycket tid och lagringsutrymme.

Lyckligtvis, sa Vaikuntanathan, har kryptografer en lång historia av att optimera resultat som från början var opraktiska. Om framtida arbete kan effektivisera tillvägagångssättet tror han att privata uppslagningar från gigantiska databaser kan vara inom räckhåll. "Vi trodde alla att vi hade fastnat där," sa han. "Vad Daniels resultat ger är hopp."

Quanta genomför en serie undersökningar för att bättre betjäna vår publik. Ta vår datavetenskaplig läsarundersökning och du kommer att delta för att vinna gratis Quanta handelsvaror.