Conteúdo do curso Lição 136 de 156 · Tecnologia de privacidade além do bloqueio
Tecnologia de privacidade além do bloqueio

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.
Sua vez

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.