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

Private Set Intersection

Waarom dit ertoe doet Bedrijven willen vaak weten welke klanten ze delen, voor een gezamenlijk aanbod of om te meten of een advertentie werkte. De makkelijke manier is om klantlijsten uit te wisselen, wat betekent dat je e-mail in de database van een ander bedrijf terechtkomt. Private Set Intersection laat hen de overlap vinden zonder dat een van beide zijden zijn lijst overhandigt. Weten hoe het werkt laat je echt privacy onderscheiden van "we hebben alleen gehashte e-mails gedeeld".

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.

Het probleem

A winkel en een app hebben elk een lijst van klant-e-mails. Ze willen de e-mails op both lijsten, en niets anders: de winkel mag de andere gebruikers van de app niet leren, en de app mag de andere klanten van de winkel niet leren.

Doorsnede van verzamelingen: de items die twee lijsten gemeen hebben. Private Set Intersection (PSI): een manier voor twee partijen om dit te berekenen terwijl ze niets anders over hun lijsten onthullen.

Waarom "gewoon hashen" faalt

Hash: een functie die tekst omzet in een willekeurige reeks met een vaste lengte (SHA-256 is een veelgebruikte). Dezelfde input geeft altijd dezelfde output, en je kunt het niet direct terugdraaien.

"We swapen gehashte e-mails, zodat niemand de echte ziet" klinkt veilig. Maar e-mails zijn te raden. Iemand met een lijst van waarschijnlijke e-mails kan elke gok hashen en zoeken naar overeenkomsten, zoals het proberen van elke sleutel op een grote sleutelbos. Je naive_reverse functie zal precies dat doen met de 200 synthetische e-mails van de praktijkwereld. Hashen verbergt data alleen als de inputs niet te raden zijn, en e-mails, telefoonnummers en namen kunnen dat wel.

De truc met de twee sloten

Onthoud uit de les wiskunde: het plaatsen van geheim a, en dan geheim b, geeft hetzelfde als b en dan a. Stel je elke e-mail voor als een doos. Alice zet haar eigen slot op elke doos en stuurt deze naar Bob. Bob voegt zijn slot toe en stuurt ze terug. Bob vergrendelt ook zijn eigen dozen en stuurt deze naar Alice, die haar slot toevoegt. Nu heeft elke doos beide sloten, en twee dozen met dezelfde e-mail erin zien er identiek uit, ongeacht welk slot als eerste werd geplaatst.

In getallen, met de praktijkgroep van watched.leg7a_privacy (P, hash_to_group, random_secret):

  1. Alice stuurt blind(alice_items, a): elk item gehasht naar de groep en dan verhoogd naar a.
  2. Bob verhoogt deze naar b (reblind) en stuurt ze terug in dezelfde volgorde.
  3. Bob stuurt blind(bob_items, b).
  4. Alice verhoogt de waarden van Bob naar a. Elk van haar dubbel vergrendelde waarden die in de dubbel vergrendelde set van Bob verschijnen is een gedeeld item. Omdat ze de volgorde behield, weet ze welke van haar items elk item is.

Waarom is dit veilig waar hashing faalde? Om een gok te testen, heb je beide geheimen nodig, en elke kant houdt zijn eigen geheim vast. Bob ziet alleen de waarden van Alice met haar geheim aan, die eruitzien als willekeurige getallen.

Diffie-Hellman PSI: de naam van dit protocol, naar het idee voor sleuteluitwisseling uit 1976 waar het van leent (twee partijen die geheime exponenten combineren). echte versies gebruiken elliptische curven (een ander soort groep, met dezelfde "volgorde doet er niet toe" eigenschap en veel kortere getallen) en zorgvuldige hashing.

Het antwoord is zelf een onthulling

Zeven perfecte PSI vertellen Alice dat een bepaalde persoon een klant van Bob is. Als Bob een kliniek of een schuldadviseur is, is dat gevoelig. Vaak heeft een bedrijf alleen hoeveel klanten nodig die gedeeld worden. In PSI cardinality schudt Bob zijn antwoord in stap 2, zodat Alice de overeenkomsten kan tellen maar niet kan zien tot welke van haar items ze behoren. Vraag naar het minimum dat de vraag beantwoordt.

In andere talen

De verblindende stap in JavaScript met BigInt (met een powMod helper zoals die in de wiskundeles):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

En in Go met math/big:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

Gebruik voor echte producten een gecontroleerde PSI-bibliotheek in plaats van zelf een te schrijven.

Samenvatting

  • Hashed e-mails zijn makkelijk om te keren met een lijst van gokken, dus "we deelden alleen hashes" is geen privacy.
  • Diffie-Hellman PSI vergrendelt elk item dubbel met twee geheimen waarvan de volgorde niet uitmaakt, zodat overeenkomsten verschijnen zonder dat een van de lijst wordt onthuld.
  • De volgorde behouden onthult welke items overeenkomen; schudden (PSI cardinaliteit) onthult alleen hoeveel.
  • De doorsnede is zelf persoonlijke gegevens, dus vraag om het minste dat de vraag beantwoordt.
Jij bent aan de beurt

Schrijf vijf functies. naive_reverse(hashes, candidates) geeft de gesorteerde lijst van kandidaten terug waarvan de SHA-256 hex digest (hashlib.sha256(c.encode()).hexdigest()) in hashes staat. blind(items, secret) geeft [pow(hash_to_group(x), secret, P) for x in items] terug. reblind(values, secret) verheft elke waarde tot secret modulo P en behoudt de volgorde. psi(alice_items, bob_items, a_secret, b_secret) volgt de vier stappen van de les met blind en reblind en geeft de gesorteerde lijst van items van Alice terug die Bob ook heeft. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) doet hetzelfde maar husselt het antwoord van Bob met rng.shuffle en geeft alleen het aantal gedeelde items terug.

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.