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

Agregación segura

Por qué importa Una aplicación de actividad física quiere el total de pasos caminados en una ciudad; un fabricante de teclados quiere saber con qué frecuencia se escribe una palabra en todos los teléfonos. En cada caso la empresa necesita un número a partir de muchos dispositivos. La agregación segura le permite conocer ese total sin ver nunca el valor de ninguna persona, y es sorprendentemente sencilla.

Criptografía didáctica, no segura: los números de los laboratorios de este módulo son lo bastante pequeños para leerlos y el azar lleva semilla para que la corrección se pueda repetir. Los sistemas reales usan bibliotecas revisadas y números muchísimo más grandes. Nunca copies código didáctico en un producto.

El truco del salario

Tres amigos quieren saber su salario medio sin que nadie revele el suyo. La primera suma un número aleatorio grande a su salario y le susurra el resultado al segundo. Él suma su salario y lo pasa en voz baja. La tercera suma el suyo y lo devuelve. La primera resta su número aleatorio, y sale el total. Cada susurro parecía un número aleatorio a quien lo oía.

Agregación segura: calcular un total (o una media) de los valores de muchas personas de forma que ningún valor individual se revele a nadie, incluido el servidor que los recoge.

Reparto aditivo de secretos: cortar un número secreto en varias partes (shares) que por sí solas parecen aleatorias pero que suman el secreto. Una sola parte, o cualquier grupo al que le falte al menos una parte, no revela nada del secreto.

Cómo funcionan las partes

Para dividir el número 7350 en tres partes, elige dos números aleatorios y escoge el tercero de forma que los tres sumen 7350. Con aritmética que da la vuelta (módulo M, aquí 2 elevado a 32, algo más de 4000 millones), cada parte es por sí sola un número aleatorio 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 qué dar la vuelta? Sin ello, una parte a veces sería negativa o sospechosamente cercana al secreto. Con ello, cada valor de una parte es igual de probable sea cual sea el secreto, así que una sola parte no lleva información.

Muchos dispositivos, varios servidores

Ahora cada teléfono divide su recuento de pasos en una parte por servidor y envía la parte 1 al servidor 1, la parte 2 al servidor 2, y así sucesivamente. Cada servidor suma las partes que recibió. El total de cada servidor sigue pareciendo aleatorio. Solo cuando se suman los totales de los servidores aparece el total real de la ciudad. Mientras los servidores no junten las partes en bruto de un mismo teléfono, nunca se ve el valor de ningún teléfono.

La versión del mundo real

Los sistemas que se usan para entrenar modelos en muchos teléfonos (lo que se llama aprendizaje federado) usan una variante más ingeniosa con un solo servidor: parejas de dispositivos acuerdan máscaras aleatorias que se anulan al sumarlo todo, más pasos extra para afrontar los teléfonos que se desconectan a mitad. La idea central es la que vas a construir: piezas de aspecto aleatorio que solo tienen sentido juntas.

Lo que no hace la agregación segura

El total se revela exactamente. Si solo contribuyeron dos personas y una conoce su propio valor, puede restarlo y conocer el de la otra. Si el total en sí es delicado, añádele también ruido de privacidad diferencial. Las dos herramientas funcionan bien juntas: la agregación oculta las entradas, la DP oculta el efecto de cada persona en el resultado.

En otros lenguajes

Dividir en JavaScript, con la vuelta de 32 bits de >>> 0 y la fuente de azar segura del 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;
}

Y en Rust, donde wrapping_sub sobre un u32 da la vuelta por ti:

let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));

Resumen

  • La agregación segura revela un total pero ninguna contribución individual.
  • El reparto aditivo de secretos divide un valor en partes de aspecto aleatorio que lo suman, usando aritmética que da la vuelta.
  • Cada servidor solo ve partes de aspecto aleatorio; solo todos los totales de los servidores juntos dan la respuesta.
  • El total en sí se revela exactamente, así que combínalo con ruido de DP cuando el total pueda exponer a alguien.
Tu turno

Escribe tres funciones, usando M (2 elevado a 32) del mundo de práctica. split(value, n, rng) devuelve una lista de n partes: las primeras n - 1 salen de rng.randrange(M), y la última es igual a (value - sum(shares)) % M. combine(shares) devuelve sum(shares) % M. aggregate(values, n_servers, rng) divide cada valor con split, suma la parte j a server_totals[j] (mod M) y devuelve una tupla (total, server_totals) donde total = combine(server_totals).

¿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.