A matemática de que você precisa
Por que isso importa As ferramentas de privacidade deste módulo, como encontrar clientes em comum sem trocar listas ou publicar estatísticas que protegem cada pessoa, se apoiam em três pequenos pedaços de matemática. Você não precisa de um diploma em matemática. Você precisa de aritmética de relógio, de uma noção de probabilidade e da ideia de que o ruído aleatório se cancela em grupos grandes. Esta lição dá exatamente isso, com Python para experimentar.
1. Aritmética de relógio
São 22:00. Que horas serão daqui a 5 horas? Não 27:00: o relógio dá a volta, então serão 03:00. Você fez 22 + 5 = 27 e ficou com o resto da divisão por 24.
Aritmética modular: aritmética em que os números dão a volta depois de chegar a um tamanho fixo, o módulo. "27 mod 24" é 3, o resto da divisão de 27 por 24. Em Python, o operador de resto é %: 27 % 24 é 3.
Dar a volta mantém os números de um tamanho fixo, por mais que você some ou multiplique, e é isso que a torna útil para a criptografia. O Python também tem uma função embutida rápida para "eleve a uma potência e depois dê a volta": pow(base, exponent, modulus).
print((22 + 5) % 24) # 3
print(pow(3, 4, 7)) # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23)) # instant, even though 5 to the 200 is huge
2. Fácil num sentido, difícil no outro
Misturar tinta amarela e azul para fazer verde é fácil. Desmisturar o verde de volta no amarelo e no azul exatos é praticamente impossível. Parte da matemática funciona do mesmo jeito.
Escolha um módulo primo grande P e um número h. Calcular pow(h, a, P) para um a secreto é instantâneo. Mas, tendo só a resposta, achar a de novo é tão lento, com números grandes o bastante, que ninguém consegue. Essa propriedade de mão única se chama problema do logaritmo discreto.
Mais um fato, e ele move os próximos laboratórios. Elevar a a e depois a b dá o mesmo resultado que elevar a b e depois a a, porque os dois são iguais a h elevado a a vezes b:
P = 1019 # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P)) # True
Como dois cadeados numa caixa, a ordem em que você os coloca não importa. Duas pessoas podem acrescentar cada uma o próprio segredo e chegar ao mesmo lugar sem nunca revelar os segredos.
3. Probabilidade em um parágrafo
Uma probabilidade é um número de 0 (nunca) a 1 (sempre). Uma moeda honesta cai em cara com probabilidade 0,5. Quando duas coisas são independentes, a chance das duas é o produto: duas caras seguidas é 0,5 × 0,5 = 0,25. O valor esperado é a média no longo prazo: jogue um dado honesto muitas vezes e a média se aproxima de 3,5.
4. O ruído se cancela numa multidão
Ruído: uma quantidade aleatória somada de propósito a um valor verdadeiro, para que o valor exato fique escondido. Se o ruído tem a mesma chance de ser para cima ou para baixo, ele dá zero em média ao longo de muitos valores.
Aqui está um truque clássico de pesquisa chamado resposta aleatorizada. Você quer saber quantas pessoas fizeram algo constrangedor. Cada pessoa joga uma moeda em segredo. Cara: responda a verdade. Coroa: jogue de novo e responda "sim" para cara e "não" para coroa. Qualquer "sim" pode ser só a moeda, então a resposta de ninguém prova nada sobre a pessoa.
Mesmo assim, o total da multidão continua útil. Se a fração verdadeira é p, a fração de respostas "sim" que você espera é 0.5 x p + 0.25. Então, se 35% dizem sim, p é mais ou menos (0.35 - 0.25) / 0.5 = 0.2, ou 20%. Quanto maior a multidão, mais perto a estimativa, porque o ruído aleatório encolhe em relação ao total conforme a multidão cresce.
import random
rng = random.Random(1) # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)] # 20% really did it
answers = []
for did_it in truth:
if rng.random() < 0.5:
answers.append(did_it) # heads: tell the truth
else:
answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3)) # close to 0.2
O ruído usado na privacidade diferencial, chamado ruído de Laplace, é uma versão suave da mesma ideia: normalmente pequeno, às vezes maior, com a mesma chance de ir para cima ou para baixo. A escala dele define o tamanho típico.
Em outras linguagens
O % do JavaScript funciona do mesmo jeito para números positivos, e os números grandes usam BigInt (escritos com um n). Não há uma potência modular embutida, então aqui está o laço padrão:
function powMod(base, exp, mod) {
let result = 1n;
base %= mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
console.log(powMod(3n, 4n, 7n)); // 4nEm Go, new(big.Int).Exp(base, exp, mod) de math/big faz o mesmo trabalho.
Um equívoco comum
"Adicionar ruído torna os dados inúteis." Para o valor de uma pessoa, sim, e é essa a ideia. Para um grupo grande, o ruído em grande parte se cancela, então totais e médias continuam úteis. A tecnologia de privacidade vive nessa diferença: borrada para os indivíduos, nítida para as multidões.
Resumo
- A aritmética modular faz os números darem a volta num módulo; o Python usa
%epow(b, e, m). - Elevar a uma potência secreta é fácil num sentido e praticamente impossível de desfazer, e a ordem de duas potências secretas não importa.
- Chances independentes se multiplicam; o valor esperado é a média no longo prazo.
- O ruído aleatório esconde os indivíduos, mas se cancela em grupos grandes, e é assim que a resposta aleatorizada funciona.
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.