Programma Les 136 van 156 · Privacytechnologie verder dan blokkeren
Privacytechnologie verder dan blokkeren

Veilige aggregatie

Waarom dit ertoe doet Een fitness app wil het totaal aantal stappen in een stad; een toetsenbordmaker wil weten hoe vaak een woord wordt getypt op alle telefoons. In elk geval heeft het bedrijf één getal nodig van veel apparaten. Secure aggregation laat het dat totaal leren zonder ooit de waarde van een individu te zien, en het is verrassend simpel.

Onderwijs over crypto, niet veilig: de getallen in de labs van deze module zijn klein genoeg om te lezen en de willekeur is gezaaid zodat het nakijken herhaalbaar is. Reële systemen gebruiken gecontroleerde bibliotheken en veel grotere getallen. Kopieer nooit onderwijscode naar een product.

De salaris-truc

Drie vrienden willen hun gemiddelde salaris weten zonder dat iemand zijn eigen salaris onthult. De eerste voegt een groot willekeurig getal toe aan haar salaris en fluistert het resultaat naar de tweede. Hij voegt zijn salaris toe en fluistert verder. De derde voegt haar salaris toe en geeft het terug. De eerste trekt haar willekeurige getal af en het totaal komt eruit. Elk gefluister leek op een willekeurig getal voor wie het hoorde.

Secure aggregation: het berekenen van een totaal (of gemiddelde) van de waarden van veel mensen zodat geen enkele waarde aan iemand wordt onthuld, inclusief de server die ze verzamelt.

Additieve geheime deling: het opdelen van een geheim getal in verschillende shares die er op zichzelf willekeurig uitzien maar samen het geheim vormen. Elke losse share, of elke groep die minstens één share mist, onthult niets over het geheim.

Hoe shares werken

Om het getal 7,350 in drie delen te splitsen, kies je twee willekeurige getallen en kies je het derde zodat alle drie samen 7,350 zijn. Met wrap-round rekenkunde (modulus M, hier 2 tot de macht 32, iets meer dan 4 miljard), is elk deel een gelijkmatig willekeurig getal op zichzelf:

M = 2 ** 32
s1, s2 = 3919211450, 120775123           # random
s3 = (7350 - s1 - s2) % M                # whatever makes it add up
print((s1 + s2 + s3) % M)                # 7350

Waarom afgerond maken? Zonder dit zou een deel soms negatief zijn of verdacht dicht bij het geheim. Met dit is elke deelwaarde even waarschijnlijk wat het geheim ook is, dus een enkel deel bevat geen informatie.

Veel apparaten, verschillende servers

Nu splitst elke telefoon zijn stapenaantal in één deel per server en stuurt deel 1 naar server 1, deel 2 naar server 2, enzovoort. Elke server telt de delen die het heeft ontvangen bij elkaar op. Het totaal van elke server ziet er nog steeds willekeurig uit. Pas wanneer de totalen van de servers bij elkaar worden opgeteld, verschijnt het echte totaal van de stad. Zolang de servers de ruwe delen van één telefoon niet samenvoegen, wordt de waarde van geen enkele telefoon ooit gezien.

De versie uit de echte wereld

Systemen voor het trainen van modellen op veel telefoons (bekend als federated learning) gebruiken een slimmere variant met één server: paren van apparaten spreken af over willekeurige maskers die elkaar opheffen wanneer alles wordt bijgeteld, plus extra stappen om om te gaan met telefoons die halverwege offline gaan. De kern van het idee is het ene dat je zult bouwen: willekeurig uitziende stukken die alleen samen zin hebben.

Wat secure aggregation niet doet

Het totaal wordt exact onthuld. Als slechts twee mensen hebben bijgedragen en één de eigen waarde kent, kunnen ze deze aftrekken en de waarde van de ander leren. Als het totaal zelf gevoelig is, voeg dan ook differential privacy noise toe. De twee tools werken goed samen: aggregatie verbergt de inputs, DP verbergt de invloed van elke persoon op de output.

In andere talen

Splitting in JavaScript, gebruik van 32-bit wrap-round met >>> 0 en de secure random source van de browser:

function split(value, n) {
  const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
  const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
  shares.push((value - sum) >>> 0);
  return shares;
}

En in Rust, waar wrapping_sub op een u32 de wrap-round voor je doet:

let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));

Samenvatting

  • Secure aggregation onthult een totaal maar geen enkele bijdrage.
  • Additive secret sharing splitst een waarde in willekeurig uitziende delen die samen de waarde vormen, met behulp van wrap-round rekenkunde.
  • Elke server ziet alleen willekeurig uitziende delen; alleen de totalen van alle servers samen geven het antwoord.
  • Het totaal zelf wordt precies onthuld, dus combineer het met DP noise wanneer het totaal iemand zou kunnen blootstellen.
Jij bent aan de beurt

Schrijf drie functies, gebruikmakend van M (2 to the 32) uit de praktijkwereld. split(value, n, rng) geeft een lijst van n shares terug: de eerste n - 1 van rng.randrange(M), de laatste gelijk aan (value - sum(shares)) % M. combine(shares) geeft sum(shares) % M terug. aggregate(values, n_servers, rng) splitst elke waarde met split, voegt share j toe aan server_totals[j] (mod M), en geeft een tuple (total, server_totals) terug waar total = combine(server_totals).

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.