Agregação segura
Por que isso importa Um app de atividade física quer o total de passos dados numa cidade; um fabricante de teclados quer saber com que frequência uma palavra é digitada em todos os celulares. Em cada caso, a empresa precisa de um único número vindo de muitos dispositivos. A agregação segura deixa que ela descubra esse total sem nunca ver o valor de nenhuma pessoa, e é surpreendentemente simples.
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 truque do salário
Três amigos querem saber o salário médio deles sem que ninguém revele o próprio. A primeira soma um número aleatório grande ao salário dela e cochicha o resultado para o segundo. Ele soma o salário dele e passa o cochicho adiante. A terceira soma o dela e devolve. A primeira subtrai o número aleatório dela, e sai o total. Cada cochicho parecia um número aleatório para quem o ouviu.
Agregação segura: calcular o total (ou a média) dos valores de muitas pessoas de modo que nenhum valor individual seja revelado a ninguém, incluindo o servidor que os coleta.
Compartilhamento aditivo de segredo: cortar um número secreto em várias partes que parecem aleatórias sozinhas, mas somam o segredo. Qualquer parte sozinha, ou qualquer grupo em que falte pelo menos uma parte, não revela nada sobre o segredo.
Como as partes funcionam
Para dividir o número 7.350 em três partes, escolha dois números aleatórios e escolha o terceiro de modo que os três somem 7.350. Com a aritmética que dá a volta (módulo M, aqui 2 elevado a 32, um pouco mais de 4 bilhões), cada parte sozinha é um número aleatório uniforme:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
Por que dar a volta? Sem isso, uma parte às vezes seria negativa ou suspeitamente próxima do segredo. Com isso, todo valor de parte tem a mesma chance, seja qual for o segredo, então uma parte sozinha não carrega informação nenhuma.
Muitos dispositivos, vários servidores
Agora cada celular divide a sua contagem de passos em uma parte por servidor e envia a parte 1 ao servidor 1, a parte 2 ao servidor 2, e assim por diante. Cada servidor soma as partes que recebeu. O total de cada servidor ainda parece aleatório. Só quando os totais dos servidores são somados é que o total real da cidade aparece. Desde que os servidores não juntem as partes brutas de um celular, o valor de nenhum celular é visto.
A versão do mundo real
Os sistemas usados para treinar modelos em muitos celulares (o chamado aprendizado federado) usam uma variante mais esperta com um único servidor: pares de dispositivos combinam máscaras aleatórias que se cancelam quando tudo é somado, mais passos extras para lidar com celulares que ficam offline no meio. A ideia central é a que você vai construir: pedaços que parecem aleatórios e só fazem sentido juntos.
O que a agregação segura não faz
O total é revelado exatamente. Se só duas pessoas contribuíram e uma sabe o próprio valor, ela pode subtraí-lo e descobrir o da outra. Se o próprio total for sensível, adicione também ruído de privacidade diferencial a ele. As duas ferramentas funcionam bem juntas: a agregação esconde as entradas, a DP esconde o efeito de cada pessoa no resultado.
Em outras linguagens
Dividindo em JavaScript, usando a volta de 32 bits com >>> 0 e a fonte aleatória segura do navegador:
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;
}E em Rust, em que wrapping_sub num u32 faz a volta para você:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));Resumo
- A agregação segura revela um total, mas nenhuma contribuição individual.
- O compartilhamento aditivo de segredo divide um valor em partes que parecem aleatórias e somam o valor, usando aritmética que dá a volta.
- Cada servidor vê só partes que parecem aleatórias; só todos os totais dos servidores juntos dão a resposta.
- O próprio total é revelado exatamente, então combine-o com ruído de DP quando o total puder expor alguém.
Escreva três funções, usando M (2 elevado a 32) do mundo de prática. split(value, n, rng) retorna uma lista de n partes: as primeiras n - 1 vindas de rng.randrange(M), e a última igual a (value - sum(shares)) % M. combine(shares) retorna sum(shares) % M. aggregate(values, n_servers, rng) divide cada valor com split, soma a parte j em server_totals[j] (mod M) e retorna uma tupla (total, server_totals) em que total = combine(server_totals).
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.