Privaat Stel-snit
Waarom dit saak maak Maatskappye wil dikwels weet watter kliënte hulle deel, vir 'n gesamentlike aanbod of om te meet of 'n advertensie gewerk het. Die maklike manier is om kliënte-lyste te ruil, wat beteken jou e-pos beland in 'n ander maatskappy se databasis. Private Set Intersection laat hulle die oorklapping vind sonder dat enige kant hul lys oorhandig. Om te weet hoe dit werk laat jou die verskil tussen ware privaatheid en "ons het net gehashede e-posse gedeel" sien.
Onderrig kriptografie, nie veilig: die nommers in hierdie module se laboratoriums is klein genoeg om te lees en die willeke is gesaai sodat gradering herhaalbaar is. Ware stelsels gebruik getoets biblioteke en veel groter nommers. Kopieer nooit onderrigkode na 'n produk nie.
Die probleem
A winkel en 'n toepassing het elk 'n lys van kliënte-e-posse. Hulle wil die e-posse op both lyste hê, en niks anders nie: die winkel moet nie die toepassing se ander gebruikers leer nie, en die toepassing moet nie die winkel se ander kliënte leer nie.
Sêksem van snitte: die items wat twee lysse gemeen het. Privê Sêksem van Snitte (PSI): 'n manier vir twee partye om dit te bereken terwyl hulle niks anders oor hul lysse verklik nie.
Waarom "net hash dit" faal
Hash: 'n funksie wat teks in 'n vaste lengte-menging verander (SHA-256 is 'n algemene een). Dieselfde input gee altyd dieselfde uitvoer, en jy kan dit nie direk terugwerk nie.
"Ons ruil gehashede e-posse, sodat niemand die regte een sien nie" klink veilig. Maar e-posse is raambaar. Enige iemand met 'n lys van waarskynlike e-posse kan elke raai hash en soek na ooreenkomste, soos om elke sleutel op 'n groot sleutelring te probeer. Jou naive_reverse funksie sal presies dit doen met die praktykwêreld se 200 sintetiese e-posse. Hashing verberg data net wanneer die insets nie geraai kan word nie, en e-posse, telefoonnommers en name kan wel.
Die twee-sluitings-trukie
Onthou van die wiskundeles: om geheime a te sit, en dan geheime b, gee dieselfde as b en dan a. Dink aan elke e-pos as 'n boks. Alice sit haar eie slot op elk van haar bokse en stuur hulle na Bob. Bob voeg sy slot by en stuur hulle terug. Bob sluit ook sy eie bokse en stuur hulle na Alice, wat haar slot byvoeg. Nou het elke boks beide slotte, en twee bokse met dieselfde e-pos binnein lyk identies, ongeag watter slot eerste opgegooi is.
in syfers, met die oefengroep van watched.leg7a_privacy (P, hash_to_group, random_secret):
- Alice stuur
blind(alice_items, a): elke item word na die groep gehash en dan totaverhef. - Bob verhoog daardie items na
b(reblind) en stuur hulle terug in dieselfde volgorde. - Bob stuur
blind(bob_items, b). - Alice verhoog Bob se waardes tot
a. Enige van haar dubbel-besluitelose waardes wat in Bob se dubbel-besluitelose stel verskyn, is 'n gedeelde item. Omdat sy die volgorde behou het, weet sy watter van haar items elk een is.
Waarom is dit veilig waar hashing gefaal het? Om 'n raai te toets, het jy beide geheime nodig, en elke kant hou sy eie. Bob sien net Alice se waardes met haar geheim aan, wat soos willekeurige nommers lyk.
Diffie-Hellman PSI: hierdie protokol se naam, na die 1976 sleuteluitwisseling-idee wat dit leen (twee partye wat geheime eksponente kombineer). Regte weersies gebruik elliptiese kurwes ('n ander soort groep, met dieselfde "orde maak nie saak nie" eienskap en baie korter getalle) en versigtige hashing.
Die antwoord is self 'n bekendstelling
Sewen perfekte PSI vertel vir Alice dat 'n spesifieke persoon Bob se kliënt is. As Bob 'n kliniek of 'n skuldadviseur is, is dit sensitief. Dikwels het 'n maatskappy net hoeveel kliënte gedeel nodig. In PSI cardinality skuif Bob sy antwoord in stap 2, sodat Alice ooreenkomste kan tel maar nie kan sien aan watter van haar items hulle behoort nie. Vra vir die minste wat die vraag beantwoord.
In ander tale
Die verblindende stap in JavaScript met BigInt (gebruik 'n powMod helper soos die een in die wiskunde-les):
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
}Vir regte produkte, gebruik 'n geouditeerde PSI-biblioteek eerder as om jou eie te skryf.
Opsomming
- Hashed e-posse is maklik om met 'n lys van rasels te herstel, so "ons het net hashes gedeel" is nie privaatheid nie.
- Diffie-Hellman PSI dubbel-sluit elke item met twee geheime wat se volgorde nie saak maak nie, sodat ooreenkomste verskyn sonder dat enige lys geopenbaar word.
- Om die volgorde te behou wys watter items ooreenstem; deur te skuif (PSI cardinality) wys dit net hoeveel.
- Die snit is self persoonlike data, so vra vir die minste wat die vraag beantwoord.
Skryf vyf funksies. naive_reverse(hashes, candidates) gee die gesorteerde lys van kandidate wie se SHA-256 hex digest (hashlib.sha256(c.encode()).hexdigest()) in hashes is. blind(items, secret) gee [pow(hash_to_group(x), secret, P) for x in items] terug. reblind(values, secret) verhoog elke waarde tot secret modulo P en behou die volgorde. psi(alice_items, bob_items, a_secret, b_secret) volg die vier stappe van die les met blind en reblind en gee die gesorteerde lys van Alice se items wat Bob ook het terug. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) doen dieselfde maar skuif Bob se antwoord met rng.shuffle en gee net die aantal gedeelde items terug.
Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les
Hierdie oefening open binnekort
Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.
Hierdie blutser blokkeer koekies vir learn.floati.life, so lesse wat jy hier voltooi het kan nie in volgorde oopgaan nie. Laat koekies vir hierdie webwerf toe en laai nuut.