Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

Stel je voor dat je een bibliothecaris bent die een geheim boek met namen beheert. Je wilt interessante statistieken delen over de mensen in dat boek — zoals de gemiddelde lengte of de meest voorkomende lievelingskleur — zonder ooit te onthullen wie er specifiek in het boek staat. Dit is de wereld van differentieel privacy, een wiskundig schild dat ons in staat stelt om te leren van gegevens terwijl de individuele geheimen beschermd blijven. Denk aan het als een "ruismachine" die net genoeg statische ruis aan de antwoorden toevoegt, zodat als iemand probeert de gegevens terug te herleiden om een specifiek persoon te vinden, de statische ruis het onmogelijk maakt.

Er zijn twee belangrijke manieren om dit schild te bouwen. De ene is het "benaderende" schild, dat een piepkleine, bijna onzichtbare kans op een lek toelaat (zoals een deur die voor 99,9% op slot zit). De andere is het "zuivere" schild, dat een 100% garantie biedt dat geen enkel geheim ooit gekraakt kan worden, hoe hard iemand ook probeert. Lange tijd wisten wiskundigen dat het "zuivere" schild veel moeilijker te gebruiken was. Wanneer je tegelijkertijd veel vragen stelde, waren de oude methoden voor het zuivere schild onhandig en traag, waardoor de antwoorden erg wazig waren. Het was alsovergelijkbaar met het proberen te schilderen van een gedetailleerd portret met alleen een dikke, klodderige kwast. Een grote vraag bleef in de lucht hangen: Zouden we een zuiver schild kunnen bouwen dat even scherp en precies is als het benaderende een?

Dit artikel zegt: "Ja, dat kunnen we." De auteurs, onder leiding van Jack Fitzsimons, hebben een nieuwe wiskundige machine geconstrueerd die antwoorden geeft op veel vragen over een private database, terwijl ze de strikte "zuivere" privacygarantie handhaven. Ze hebben bewezen dat deze machine een nauwkeurigheidsniveau kan bereiken dat voorheen slechts een gok was. Specifiek hebben ze aangetoond dat de fout in de antwoorden krimpt met een snelheid die gerelateerd is aan de vierkantswortel van het aantal mensen in de database, in plaats van de tragere derdemachtswortel-snelheid waar oudere methoden mee vastzaten. Het is alsof je die klodderige kwast vervangt door een fijn penseel, waardoor je zelfs een helder beeld krijgt wanneer de regels het strengst zijn.

Het verhaal van de "Privacy-envelop"

Om te begrijpen hoe ze het deden, stel je voor dat je probeert de gemiddelde lengte van een groep mensen te raden, maar dat je alleen vragen kunt stellen zoals: "Is deze persoon langer dan 1,50 meter?" De standaardmethode om dit privaat te doen, wordt Multiplicative Weights (PMW) genoemd. Denk aan PMW als een detective die een lijst met "verdachten" (mogelijke datadistributies) bijhoudt en zijn overtuigingen bijwerkt elke keer dat hij een vraag stelt.

In het verleden, wanneer de detective probeerde de strikte "zuivere" privacyregels te gebruiken, moest hij zo voorzichtig zijn dat hij te veel informatie wegwierp, waardoor zijn gissingen wazig werden. De oude methode was als een detective die, om veilig te zijn, alleen naar de data kijkt door een dik, beslagen raam. De mist (de privacyruis) was te zwaar en de detective kon de details niet duidelijk zien.

De auteurs realiseerden zich dat de "beslagen ruit" van de detective het probleem was. Ze hadden een manier nodig om het scherpe zicht van de detective te behouden en toch aan de strikte privacyregels te voldoen. Hun oplossing was het bouwen van een Privacy-envelop.

Stel je de lijst met verdachten van de detective voor als een kaart. De oude methode zei: "We kunnen de kaart alleen vertrouwen als we 100% zeker weten dat de data helemaal niet is veranderd." De nieuwe methode zegt: "Laten we naar de kaart kijken, maar laten we ook naar alle kaarten kijken die bijna hetzelfde zijn, met slechts een paar kleine veranderingen."

Hier is de slimme truc: De auteurs creëerden een "waarschijnlijkheidsenvelop". Voor elk mogelijk antwoord dat de detective zou kunnen geven, vroegen ze: "Hoe waarschijnlijk is dit antwoord als de data iets anders was?" Ze namen vervolgens het meest waarschijnlijke antwoord over al die licht verschillende versies van de data, maar ze pasten een "korting" toe op basis van hoe verschillend de data was. Als de data slechts één persoon verschilde, was de korting klein. Als de data totaal anders was, was de korting enorm.

Dit is als een spelletje van "Warm of Koud". Als je dicht bij de waarheid bent, zegt het spelletje "Warm" (hoge waarschijnlijkheid). Als je ver weg bent, zegt het "Koud" (lage waarschijnlijkheid). De envelop van de auteurs neemt het "warmste" punt uit alle nabijgelegen mogelijkheden en gebruikt dat als het definitieve antwoord. Omdat ze wiskundig hebben bewezen dat dit "warmste punt" nooit te ver van de echte waarheid kan liggen, konden ze de privacy garanderen zonder de nauwkeurigheid te verliezen.

De magie van "Blocking"

Er was nog één laatste hindernis. Wanneer je al deze "nabijgelegen" mogelijkheden bij elkaar optelt, kan de wiskunde rommelig worden. Als je probeert elke enkele kleine stap van verschil te tellen, stapelen de fouten zich op en verpesten ze het antwoord. Het is alsof je probeert elk korreltje zand op een strand één voor één te tellen; je zult er een paar missen, of je zult moe worden en een fout maken.

De auteurs losten dit op door de korrels zand te groeperen in "blokken". In plaats van elke enkele stap van afstand tussen datasets te tellen, groepeerden ze deze in brokken. Ze bewezen dat binnen elk brokstuk de fouten elkaar opheffen of klein genoeg blijven om genegeerd te worden. Deze "blocking"-techniek stelde hen in staat om een enorme straf te vermijden die de antwoorden anders onbruikbaar zou hebben gemaakt. Het is als het meten van het strand in emmers zand in plaats van korrels; je krijgt een veel nauwkeuriger totaal aantal zonder overweldigd te worden door de details.

Het resultaat

Het artikel bewijst dat deze nieuwe methode werkt voor elke grootte van een database en voor elk aantal vragen. De fout in de antwoorden volgt een specifieke formule: het wordt kleiner naarmate de database groter wordt, en krimpt met een snelheid van ongeveer de vierkantswortel van het aantal mensen. Dit komt overeen met de beste prestatie die wiskundigen theoretisch mogelijk achtten, waardoor de kloof tussen wat we dachten dat we konden doen en wat we daadwerkelijk kunnen doen, eindelijk is gedicht.

De auteurs hebben niet alleen gegokt; ze hebben een rigoureus wiskundig bewijs opgesteld om aan te tonen dat het werkt. Ze hebben zelfs een computerprogramma genaamd Lean gebruikt om hun werk te controleren, om te verzekeren dat elke stap van hun logica standhoudt. Hoewel de methode momenteel een theoretisch blauwdruk is (een "wiskundig recept" in plaats van een direct bruikbare app), lost het een decennia oud puzzel op. Het laat zien dat we niet hoeven te kiezen tussen strikte privacy en nauwkeurige antwoorden; met de juiste "envelop" kunnen we beide hebben.

Dus, de volgende keer dat je hoort dat je gegevens worden gebruikt om een AI te trainen of statistieken te berekenen, onthoud dan dit: dankzij deze nieuwe "envelop"-truc is het mogelijk om zeer precieze antwoorden te krijgen zonder dat je je ooit zorgen hoeft te maken dat jouw specifieke geheim is gelekt. De mist is opgetrokken, en het beeld is eindelijk helder.