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

Intersección privada de conjuntos

Por qué importa Las empresas a menudo quieren saber qué clientes comparten, para una oferta conjunta o para medir si un anuncio funcionó. La forma fácil es intercambiar listas de clientes, lo que significa que tu correo acaba en la base de datos de otra empresa. La intersección privada de conjuntos les permite encontrar la coincidencia sin que ninguna de las dos partes entregue su lista. Saber cómo funciona te permite distinguir la privacidad real de "solo compartimos correos con hash".

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 problema

Una tienda y una aplicación tienen cada una una lista de correos de clientes. Quieren los correos que están en las dos listas, y nada más: la tienda no debe conocer a los demás usuarios de la aplicación, y la aplicación no debe conocer a los demás clientes de la tienda.

Intersección de conjuntos: los elementos que tienen en común dos listas. Intersección privada de conjuntos (PSI): una forma de que dos partes la calculen sin revelar nada más sobre sus listas.

Por qué falla "basta con calcular el hash"

Hash: una función que convierte un texto en un revoltijo de longitud fija (SHA-256 es una muy común). La misma entrada siempre da la misma salida, y no puedes ejecutarla al revés directamente.

"Intercambiamos correos con hash, así que nadie ve los reales" suena seguro. Pero los correos se pueden adivinar. Cualquiera con una lista de correos probables puede calcular el hash de cada intento y buscar coincidencias, como probar todas las llaves de un gran llavero. Tu función naive_reverse hará justo eso con los 200 correos sintéticos del mundo de práctica. El hash solo oculta los datos cuando las entradas no se pueden adivinar, y los correos, los números de teléfono y los nombres sí se pueden.

El truco de los dos candados

Recuerda la lección de matemáticas: poner el secreto a y luego el secreto b da lo mismo que b y luego a. Imagina cada correo como una caja. Alice pone su propio candado en cada una de sus cajas y se las envía a Bob. Bob añade su candado y se las devuelve. Bob también cierra sus propias cajas y se las envía a Alice, que añade su candado. Ahora cada caja tiene los dos candados, y dos cajas con el mismo correo dentro parecen idénticas, se pusiera primero el candado que se pusiera.

En números, con el grupo de práctica de watched.leg7a_privacy (P, hash_to_group, random_secret):

  1. Alice envía blind(alice_items, a): cada elemento pasado al grupo con un hash y luego elevado a a.
  2. Bob eleva esos valores a b (reblind) y los devuelve en el mismo orden.
  3. Bob envía blind(bob_items, b).
  4. Alice eleva los valores de Bob a a. Cualquiera de sus valores con doble candado que aparezca en el conjunto con doble candado de Bob es un elemento compartido. Como conservó el orden, sabe a cuál de sus elementos corresponde cada uno.

¿Por qué esto es seguro donde el hash fallaba? Para probar un intento necesitas los dos secretos, y cada parte guarda el suyo. Bob solo ve los valores de Alice con el secreto de ella puesto, y parecen números aleatorios.

PSI de Diffie-Hellman: el nombre de este protocolo, por la idea de intercambio de claves de 1976 que toma prestada (dos partes que combinan exponentes secretos). Las versiones reales usan curvas elípticas (otro tipo de grupo, con la misma propiedad de "el orden no importa" y números mucho más cortos) y un hash cuidadoso.

La respuesta ya es una revelación

Incluso una PSI perfecta le dice a Alice que una persona concreta es cliente de Bob. Si Bob es una clínica o un asesor de deudas, eso es delicado. A menudo a una empresa solo le hace falta saber cuántos clientes se comparten. En la cardinalidad PSI (PSI cardinality), Bob baraja su respuesta en el paso 2, así que Alice puede contar las coincidencias pero no puede saber a cuáles de sus elementos pertenecen. Pide lo mínimo que responda a la pregunta.

En otros lenguajes

El paso de cegado en JavaScript con BigInt (usando una función auxiliar powMod como la de la lección de matemáticas):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

Y en Go con math/big:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

Para productos reales, usa una biblioteca de PSI auditada en lugar de escribir la tuya.

Resumen

  • Los correos con hash son fáciles de revertir con una lista de intentos, así que "solo compartimos hashes" no es privacidad.
  • La PSI de Diffie-Hellman pone doble candado a cada elemento con dos secretos cuyo orden no importa, así que las coincidencias aparecen sin revelar ninguna de las listas.
  • Conservar el orden revela qué elementos coinciden; barajar (cardinalidad PSI) solo revela cuántos.
  • La intersección ya es en sí un dato personal, así que pide lo mínimo que responda a la pregunta.
Tu turno

Escribe cinco funciones. naive_reverse(hashes, candidates) devuelve la lista ordenada de los candidatos cuyo resumen hexadecimal SHA-256 (hashlib.sha256(c.encode()).hexdigest()) está en hashes. blind(items, secret) devuelve [pow(hash_to_group(x), secret, P) for x in items]. reblind(values, secret) eleva cada valor a secret módulo P, conservando el orden. psi(alice_items, bob_items, a_secret, b_secret) sigue los cuatro pasos de la lección usando blind y reblind, y devuelve la lista ordenada de los elementos de Alice que Bob también tiene. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) hace lo mismo pero baraja la respuesta de Bob con rng.shuffle y devuelve solo el número de elementos compartidos.

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