Private Set Intersection
Por que isso importa As empresas muitas vezes querem saber quais clientes elas têm em comum, para uma oferta conjunta ou para medir se um anúncio funcionou. O jeito fácil é trocar listas de clientes, o que significa que o seu e-mail vai parar no banco de dados de outra empresa. A Private Set Intersection deixa que elas encontrem a sobreposição sem que nenhum lado entregue a própria lista. Saber como ela funciona permite diferenciar privacidade de verdade de "nós só compartilhamos e-mails com hash".
Criptografia didática, não segura: os números dos laboratórios deste módulo são pequenos o bastante para serem lidos, e a aleatoriedade tem semente para que a avaliação seja repetível. Sistemas reais usam bibliotecas verificadas e números muito maiores. Nunca copie código didático para um produto.
O problema
Uma loja e um app têm cada um uma lista de e-mails de clientes. Eles querem os e-mails que estão nas duas listas, e nada mais: a loja não pode descobrir os outros usuários do app, e o app não pode descobrir os outros clientes da loja.
Interseção de conjuntos: os itens que duas listas têm em comum. Private Set Intersection (PSI): um jeito de duas partes calcularem isso sem revelar mais nada sobre as próprias listas.
Por que "é só fazer o hash" falha
Hash: uma função que transforma um texto num embaralhado de tamanho fixo (SHA-256 é uma comum). A mesma entrada sempre dá a mesma saída, e você não consegue rodá-la de trás para frente diretamente.
"Nós trocamos e-mails com hash, então ninguém vê os verdadeiros" parece seguro. Mas os e-mails são adivinháveis. Qualquer um com uma lista de e-mails prováveis pode fazer o hash de cada palpite e procurar correspondências, como testar cada chave de um molho grande. A sua função naive_reverse vai fazer exatamente isso com os 200 e-mails sintéticos do mundo de prática. O hash só esconde dados quando as entradas não podem ser adivinhadas, e e-mails, números de telefone e nomes podem.
O truque dos dois cadeados
Lembre da lição de matemática: colocar o segredo a e depois o segredo b dá o mesmo que b e depois a. Imagine cada e-mail como uma caixa. Alice coloca o próprio cadeado em cada uma das caixas dela e as envia a Bob. Bob acrescenta o cadeado dele e as devolve. Bob também tranca as próprias caixas e as envia a Alice, que acrescenta o cadeado dela. Agora toda caixa tem os dois cadeados, e duas caixas com o mesmo e-mail dentro parecem idênticas, seja qual for o cadeado que entrou primeiro.
Em números, com o grupo de prática de watched.leg7a_privacy (P, hash_to_group, random_secret):
- Alice envia
blind(alice_items, a): cada item passado para o grupo por hash e depois elevado aa. - Bob eleva esses valores a
b(reblind) e os devolve na mesma ordem. - Bob envia
blind(bob_items, b). - Alice eleva os valores de Bob a
a. Qualquer valor dela com os dois cadeados que aparecer no conjunto de valores de Bob com os dois cadeados é um item em comum. Como ela manteve a ordem, ela sabe a qual dos itens dela cada um corresponde.
Por que isso é seguro onde o hash falhou? Para testar um palpite, você precisa dos dois segredos, e cada lado guarda o seu. Bob só vê os valores de Alice com o segredo dela aplicado, que parecem números aleatórios.
PSI de Diffie-Hellman: o nome deste protocolo, por causa da ideia de troca de chaves de 1976 que ele pega emprestada (duas partes combinando expoentes secretos). Versões reais usam curvas elípticas (outro tipo de grupo, com a mesma propriedade de "a ordem não importa" e números bem mais curtos) e um hash cuidadoso.
A própria resposta já é uma revelação
Mesmo uma PSI perfeita diz a Alice que uma determinada pessoa é cliente de Bob. Se Bob é uma clínica ou um consultor de dívidas, isso é sensível. Muitas vezes uma empresa só precisa saber quantos clientes são compartilhados. Na PSI de cardinalidade, Bob embaralha a resposta dele no passo 2, então Alice consegue contar as correspondências, mas não consegue dizer a quais dos itens dela elas pertencem. Peça o mínimo que responda à pergunta.
Em outras linguagens
O passo de cegamento em JavaScript com BigInt (usando uma função auxiliar powMod como a da lição de matemática):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));E em Go com 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
}Em produtos reais, use uma biblioteca de PSI auditada em vez de escrever a sua.
Resumo
- E-mails com hash são fáceis de reverter com uma lista de palpites, então "nós só compartilhamos hashes" não é privacidade.
- A PSI de Diffie-Hellman tranca cada item duas vezes com dois segredos cuja ordem não importa, então as correspondências aparecem sem que nenhuma das listas seja revelada.
- Manter a ordem revela quais itens correspondem; embaralhar (PSI de cardinalidade) revela só quantos.
- A própria interseção é um dado pessoal, então peça o mínimo que responda à pergunta.
Escreva cinco funções. naive_reverse(hashes, candidates) retorna a lista ordenada de candidatos cujo digest SHA-256 em hexadecimal (hashlib.sha256(c.encode()).hexdigest()) está em hashes. blind(items, secret) retorna [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) eleva cada valor a secret módulo P, mantendo a ordem. psi(alice_items, bob_items, a_secret, b_secret) segue os quatro passos da lição usando blind e reblind, e retorna a lista ordenada dos itens de Alice que Bob também tem. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) faz o mesmo, mas embaralha a resposta de Bob com rng.shuffle e retorna só o número de itens em comum.
Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição
Este exercício abre em breve
Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.
Este navegador está bloqueando cookies para learn.floati.life, então as lições que você terminou aqui não podem abrir em ordem. Permita cookies para este site e recarregue.