Temario Lección 133 de 156 · Tecnología de privacidad más allá del bloqueo
Tecnología de privacidad más allá del bloqueo

Las matemáticas que necesitas

Por qué importa Las herramientas de privacidad de este módulo, como encontrar clientes compartidos sin intercambiar listas o publicar estadísticas que protegen a cada persona, se apoyan en tres pequeñas piezas de matemáticas. No necesitas una carrera de matemáticas. Necesitas la aritmética del reloj, una intuición del azar y la idea de que el ruido aleatorio se compensa en los grupos grandes. Esta lección te da justo eso, con Python para probarlo.

1. La aritmética del reloj

Son las 22:00. ¿Qué hora es 5 horas después? No las 27:00: el reloj da la vuelta, así que son las 03:00. Hiciste 22 + 5 = 27 y te quedaste con el resto de dividir entre 24.

Aritmética modular: aritmética en la que los números dan la vuelta al llegar a un tamaño fijo, el módulo. "27 mod 24" es 3, el resto de dividir 27 entre 24. En Python el operador del resto es %: 27 % 24 es 3.

Dar la vuelta mantiene los números con un tamaño fijo por mucho que sumes o multipliques, y eso es lo que la hace útil para la criptografía. Python también tiene una función integrada rápida para "elevar a una potencia y luego dar la vuelta": 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 en un sentido, difícil en el otro

Mezclar pintura amarilla y azul para obtener verde es fácil. Separar el verde en el amarillo y el azul exactos es prácticamente imposible. Algunas matemáticas funcionan igual.

Elige un módulo primo grande P y un número h. Calcular pow(h, a, P) para un secreto a es instantáneo. Pero si solo tienes la respuesta, volver a encontrar a es tan lento con números lo bastante grandes que nadie puede hacerlo. Esta propiedad de un solo sentido se llama el problema del logaritmo discreto.

Un dato más, que mueve los próximos laboratorios. Elevar a a y luego a b da el mismo resultado que elevar a b y luego a a, porque los dos son iguales a h elevado a a por 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 dos candados en una misma caja, el orden en que los pones no importa. Dos personas pueden añadir cada una su propio secreto y llegar al mismo sitio sin revelar nunca sus secretos.

3. La probabilidad en un párrafo

Una probabilidad es un número de 0 (nunca) a 1 (siempre). Una moneda justa sale cara con probabilidad 0.5. Cuando dos cosas son independientes, la probabilidad de las dos es el producto: dos caras seguidas es 0.5 x 0.5 = 0.25. El valor esperado es la media a largo plazo: lanza un dado justo muchas veces y la media se acerca a 3.5.

4. El ruido se compensa en una multitud

Ruido: una cantidad aleatoria que se añade a propósito a un valor real, para ocultar el valor exacto. Si el ruido tiene la misma probabilidad de ir hacia arriba que hacia abajo, en muchos valores su media es cero.

Aquí tienes un truco clásico de encuestas llamado respuesta aleatorizada. Quieres saber cuánta gente ha hecho algo vergonzoso. Cada persona lanza una moneda en secreto. Cara: responde la verdad. Cruz: lanza otra vez y responde "sí" si sale cara y "no" si sale cruz. Cualquier "sí" podría ser solo cosa de la moneda, así que la respuesta de nadie demuestra nada sobre esa persona.

Y aun así el total de la multitud sigue siendo útil. Si la fracción real es p, la fracción de respuestas "sí" que esperas es 0.5 x p + 0.25. Así que si el 35 % dice que sí, p es más o menos (0.35 - 0.25) / 0.5 = 0.2, o un 20 %. Cuanto más grande es la multitud, más se acerca la estimación, porque el ruido aleatorio se hace pequeño en comparación con el total a medida que crece la multitud.

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

El ruido que se usa en la privacidad diferencial, llamado ruido de Laplace, es una versión suave de la misma idea: normalmente pequeño, de vez en cuando más grande, con la misma probabilidad hacia arriba que hacia abajo. Su escala fija lo grande que suele ser.

En otros lenguajes

El % de JavaScript funciona igual con números positivos, y los números grandes usan BigInt (que se escribe con una n). No hay una potencia modular integrada, así que aquí tienes el bucle estándar:

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));   // 4n

En Go, new(big.Int).Exp(base, exp, mod) de math/big hace el mismo trabajo.

Una idea equivocada muy común

"Añadir ruido hace inútiles los datos." Para el valor de una persona, sí, y esa es la idea. Para un grupo grande, el ruido se compensa en gran parte, así que los totales y las medias siguen siendo útiles. La tecnología de privacidad vive en ese hueco: borrosa para los individuos, nítida para las multitudes.

Resumen

  • La aritmética modular da la vuelta a los números alrededor de un módulo; Python usa % y pow(b, e, m).
  • Elevar a una potencia secreta es fácil en un sentido y prácticamente imposible de deshacer, y el orden de dos potencias secretas no importa.
  • Las probabilidades independientes se multiplican; el valor esperado es la media a largo plazo.
  • El ruido aleatorio oculta a los individuos pero se compensa en los grupos grandes, que es como funciona la respuesta aleatorizada.

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.