Private Set Intersection
Perché è importante Le aziende vogliono spesso sapere quali clienti hanno in comune, per un'offerta congiunta o per misurare se una pubblicità ha funzionato. Il modo facile è scambiarsi le liste dei clienti, il che significa che la tua email finisce nel database di un'altra azienda. La Private Set Intersection permette di trovare la sovrapposizione senza che nessuna delle due parti consegni la propria lista. Sapere come funziona ti permette di distinguere la vera privacy da "abbiamo condiviso solo email con hash".
Crittografia didattica, non sicura: i numeri nei laboratori di questo modulo sono abbastanza piccoli da leggere e la casualità usa un seme fisso così la correzione è ripetibile. I sistemi veri usano librerie verificate e numeri molto più grandi. Non copiare mai codice didattico in un prodotto.
Il problema
Un negozio e un'app hanno ciascuno una lista di email dei clienti. Vogliono le email presenti in entrambe le liste, e nient'altro: il negozio non deve scoprire gli altri utenti dell'app, e l'app non deve scoprire gli altri clienti del negozio.
Intersezione di insiemi: gli elementi che due liste hanno in comune. Private Set Intersection (PSI): un modo per due parti di calcolarla senza rivelare nient'altro delle proprie liste.
Perché "basta fare l'hash" non funziona
Hash: una funzione che trasforma un testo in un miscuglio di lunghezza fissa (SHA-256 è una delle più comuni). Lo stesso input dà sempre lo stesso output, e non puoi farla funzionare al contrario direttamente.
"Ci scambiamo email con hash, quindi nessuno vede quelle vere" sembra sicuro. Ma le email si possono indovinare. Chiunque abbia una lista di email probabili può fare l'hash di ogni ipotesi e cercare corrispondenze, come provare ogni chiave di un grosso mazzo. La tua funzione naive_reverse farà esattamente questo con le 200 email sintetiche del mondo di prova. L'hash nasconde i dati solo quando gli input non si possono indovinare, e email, numeri di telefono e nomi si possono indovinare.
Il trucco dei due lucchetti
Ricorda dalla lezione di matematica: mettere il segreto a e poi il segreto b dà lo stesso risultato di b e poi a. Immagina ogni email come una scatola. Alice mette il proprio lucchetto su ciascuna delle sue scatole e le manda a Bob. Bob aggiunge il suo lucchetto e le rimanda indietro. Bob chiude anche le proprie scatole con il suo lucchetto e le manda ad Alice, che aggiunge il suo. Ora ogni scatola ha entrambi i lucchetti, e due scatole con la stessa email dentro sembrano identiche, qualunque lucchetto sia stato messo per primo.
In numeri, con il gruppo di prova di watched.leg7a_privacy (P, hash_to_group, random_secret):
- Alice invia
blind(alice_items, a): ogni elemento trasformato con l'hash nel gruppo e poi elevato ada. - Bob li eleva a
b(reblind) e li rimanda nello stesso ordine. - Bob invia
blind(bob_items, b). - Alice eleva i valori di Bob ad
a. Ognuno dei suoi valori con doppio lucchetto che compare nell'insieme a doppio lucchetto di Bob è un elemento in comune. Siccome ha tenuto l'ordine, sa a quale dei suoi elementi corrisponde ciascuno.
Perché questo è sicuro dove l'hash falliva? Per verificare un'ipotesi ti servono entrambi i segreti, e ogni parte tiene il proprio. Bob vede sempre e solo i valori di Alice con il segreto di lei sopra, che sembrano numeri casuali.
PSI di Diffie-Hellman: il nome di questo protocollo, dall'idea di scambio di chiavi del 1976 che prende in prestito (due parti che combinano esponenti segreti). Le versioni vere usano curve ellittiche (un altro tipo di gruppo, con la stessa proprietà "l'ordine non conta" e numeri molto più corti) e un hash fatto con cura.
La risposta è già una rivelazione
Anche una PSI perfetta dice ad Alice che una certa persona è cliente di Bob. Se Bob è una clinica o un consulente per i debiti, è un'informazione delicata. Spesso a un'azienda serve solo quanti clienti sono in comune. Nella PSI cardinality Bob mescola la sua risposta al passo 2, così Alice può contare le corrispondenze ma non può dire a quali dei suoi elementi appartengono. Chiedi il minimo che risponde alla domanda.
In altri linguaggi
Il passo di oscuramento in JavaScript con BigInt (usando una funzione di supporto powMod come quella della lezione di matematica):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));E in Go con 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
}Per i prodotti veri, usa una libreria PSI verificata invece di scriverne una tua.
Riepilogo
- Le email con hash si invertono facilmente con una lista di ipotesi, quindi "abbiamo condiviso solo hash" non è privacy.
- La PSI di Diffie-Hellman mette un doppio lucchetto su ogni elemento con due segreti il cui ordine non conta, così le corrispondenze compaiono senza che nessuna lista venga rivelata.
- Tenere l'ordine rivela quali elementi corrispondono; mescolare (PSI cardinality) rivela solo quanti.
- L'intersezione è essa stessa un dato personale, quindi chiedi il minimo che risponde alla domanda.
Scrivi cinque funzioni. naive_reverse(hashes, candidates) restituisce la lista ordinata dei candidati il cui digest esadecimale SHA-256 (hashlib.sha256(c.encode()).hexdigest()) è in hashes. blind(items, secret) restituisce [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) eleva ogni valore a secret modulo P, mantenendo l'ordine. psi(alice_items, bob_items, a_secret, b_secret) segue i quattro passi della lezione usando blind e reblind, e restituisce la lista ordinata degli elementi di Alice che ha anche Bob. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) fa lo stesso ma mescola la risposta di Bob con rng.shuffle e restituisce solo il numero di elementi in comune.
Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione
Questo esercizio si apre presto
Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.
Questo browser blocca i cookie per learn.floati.life, quindi le lezioni che hai finito qui non si possono aprire in ordine. Consenti i cookie per questo sito e ricarica.