Cuando te das de alta en una nueva red social, como WhatsApp, se te suele preguntar si quieres averiguar quiénes de entre tus contactos ya forman parte de dicha red social (contact discovery). Pero si tú no quieres proporcionar tu lista completa de contactos, ¿cómo saber si alguno está en la red social sin compartir tu agenda?

Los países de medio mundo están desarrollando apps de seguimiento de contagios de la COVID-19. En España, por ejemplo, se puso en marcha el piloto Radar COVID en la isla de La Gomera a finales de junio. Estas apps despiertan muchos recelos en cuanto a la privacidad. ¿Sería posible descubrir si has estado en contacto con alguna persona contagiada sin que ni tú ni el servidor sepáis quién es exactamente?

O imagina que un laboratorio ha descubierto un fármaco contra la COVID-19 que funciona solamente con las personas que poseen unos determinados genes. ¿Cómo puede saber el laboratorio si posees esos genes sin que tú le reveles todo tu genoma ni el laboratorio te revele cuáles son esos genes específicos?

¿Qué está pasando?

El Big Data y la computación en la nube están dando origen a multitud de situaciones en las que dos partes poseen cada una un conjunto de datos que desea compartir con la otra para encontrar la intersección entre ambos conjuntos. Eso sí, sólo revelando los datos en común. Se trata de un viejo problema de la criptografía conocido como Intersección Privada de Conjuntos (Private Set Intersection, PSI) que está experimentando un fuerte resurgimiento. Además de los tres escenarios ya mencionados, existen muchos otros casos de uso:

• Una empresa desarrolla una app de diagnóstico remoto de la COVID-19 con una precisión extraordinaria a partir de una lista de síntomas proporcionada por el paciente. El paciente no desea revelar sus síntomas a la empresa ni la empresa desea revelar a nadie qué síntomas usa para el diagnóstico.
• La misma persona recibe atención médica en distintas localidades. Las distintas administraciones desean saber qué pacientes han visitado centros de salud de otras comunidades sin revelar una a otra su lista de pacientes.
• Con el fin de llevar a cabo una operación internacional, varios organismos de ciberseguridad nacionales desean encontrar la intersección entre sus bases de datos de IPs delictivas sin revelarse unos a otros sus listas completas de IPs.
• Una agencia de publicidad envía un anuncio online a un grupo de usuarios. Algunos de estos usuarios posteriormente compran el producto en una tienda física. La agencia desea encontrar la intersección entre el conjunto de los usuarios que vieron el anuncio del producto y los que lo compraron en tiendas físicas (online-to-offline ad conversions).
• Una empresa de comida sana sirve comidas a muchos empleados de otra empresa, la cual les realiza pruebas médicas dos veces al año. La empresa de restauración desea saber si los empleados que han bajado el colesterol en el último año consumieron su comida, pero la otra empresa no quiere (ni debe) revelar los datos de salud de sus empleados. 

Cuanta más tracción ganan la nube y el Big Data, más casos de uso nuevos surgen cada día: detección de botnets, identificación de tramposos en juegos online, compartición de ubicaciones, descubrimiento de credenciales comprometidas, etc.

La necesidad de realizar esta intersección de conjuntos de forma privada ha quedado clara, pero la cuestión es: ¿cómo lograrlo? La criptografía ofreció numerosas técnicas de PSI, desde la solución naive con funciones de hash a los protocolos con terceras partes semiconfiables y los protocolos que sólo involucran a dos partes. Veamos someramente cómo funcionan.

La solución naive con funciones de hash

Consiste en comparar los hashes de cada elemento de ambos conjuntos. Si dos hashes coinciden, entonces se ha producido un ajuste. Este enfoque, que fue usado por WhatsApp en su día, es sencillo y rápido, pero no es seguro porque con un conjunto de datos pequeño o con una baja entropía, como por ejemplo números de teléfono, es perfectamente factible realizar un ataque de fuerza bruta, calculando los hashes de todos los posibles elementos. De esta forma, armado con la lista de hashes de todos los teléfonos, WhastApp no sólo sabría los contactos que compartís, ¡sino los números de teléfono de todos tus contactos!

Igualmente, este enfoque tampoco sirve para comparar DNIs, identificadores sencillos, nombres, etc. Sólo aporta seguridad cuando los datos a comparar son aleatorios o poseen una alta entropía.

PSI basado en terceras partes semiconfiables

Otro enfoque más robusto consiste en hacer pasar cada uno de los elementos de los conjuntos por la misma función HMAC con una clave secreta que las dos partes, Alice y Bob, han acordado previamente. Envían sus datos aleatorizados a la tercera parte, Trent, quien les devuelve a cada uno el conjunto intersección. Como Alice y Bob han conservado cada uno una tabla privada con las salidas de la función HMAC para cada dato de sus conjuntos respectivos, pueden buscar en esta tabla los ajustes y determinar qué elementos comparten.

La máxima información filtrada a Trent es la cardinalidad del conjunto intersección, es decir, cuántos elementos poseen en común Alice y Bob; y la cardinalidad de los conjuntos de Alice y Bob, ya que Trent sabrá si alice tiene más elementos en su conjunto que Bob o viceversa. Por supuesto, Trent podría resultar ser malicioso e intentar engañar a Alice y Bob, por ejemplo, devolviendo un conjunto intersección diferente al real. Por fortuna, existen sencillos ajustes a este protocolo para evitar este tipo de manipulaciones por parte de Trent. Lo que nunca descubrirá son los datos de Alice y Bob.

PSI basado en dos partes

¿Qué pasa si no quieres depender de una tercera parte? No hay problema. Existen multitud de enfoques alternativos en los cuales sólo interactúan las dos partes implicadas que quieren encontrar la intersección entre sus conjuntos.

Uno de los primeros enfoques propuestos y conceptualmente más sencillos se basa en las premisas criptográficas del famoso protocolo de Diffie-Hellman para acordar claves de sesión entre dos partes a través de un canal inseguro. En este caso, Alice y Bob aplican el protocolo DH para compartir una clave de sesión por cada dato en sus respectivos conjuntos. Cualquier clave compartida que se encuentre en ambos conjuntos indica que el elemento correspondiente es un miembro de los conjuntos originales de ambas partes. Veamos con más detalle su funcionamiento:

1. Alice y Bob acuerdan un número primo de gran tamaño, p, usando un canal público.
2. Alice genera al azar una clave privada, a.
3. Alice calcula el hash, g_i, de cada uno de los valores de su conjunto original. En realidad, este paso es algo más complicado, ya que hay que repetir el hash hasta que g sea una raíz primitiva módulo p, pero no entraremos en los pormenores matemáticos.
4. Para cada uno de estos valores g_i, Alice calcula el valor g_i^a mod p.
5. Alice envía estos valores a Bob.
6. Bob genera aleatoriamente una clave privada, b.
7. Bob calcula repetidamente el hash, h_i, de cada uno de los valores de su conjunto original, hasta que sean raíces primitivas módulo p.
8. Para cada uno de estos valores de hash, Bob calcula h_i^b mod p.
9. Bob calcula las claves compartidas correspondientes a cada elemento del conjunto original de Alice, elevando los valores recibidos de Alice a la potencia de su clave privada, es decir, g_i^ab mod p.
10. Bob envía sus valores calculados, h_i^b mod p, a Alice, así como las claves compartidas calculadas correspondientes a los elementos del conjunto original de Alice, g_i^ab mod p.
11. Alice calcula las claves compartidas correspondientes a cada elemento del conjunto original de Bob elevando los valores recibidos de Bob a la potencia de su clave privada, es decir, h_i^ba = h_i^ab mod p, para cada uno de los valores recibidos de Bob.
12. Alice compara las claves compartidas calculadas a partir de los elementos de su propio conjunto original, g_i^ab, con las claves compartidas calculadas con los elementos de Bob, h_i^ab. La intersección consiste en aquellos elementos del conjunto original de Alice cuya clave compartida también se puede encontrar en el conjunto de claves compartidas calculadas a partir de los elementos del conjunto original de Bob, g_i^ab = h_i^ab.

Desde la publicación de este protocolo han aparecido docenas de alternativas que utilizan primitivas criptográficas cada vez más sofisticadas. Se han propuesto protocolos muy elaborados basados en otros algoritmos de clave pública, como operaciones con RSA ciego; basados en filtros de Bloom; en cifrado totalmente homomórfico; en la transferencia inconsciente (OT) para transmitir los datos de los conjuntos; o en variantes del Circuito Confuso de Yao, capaz de simular cualquier función matemática con un circuito booleano utilizando exclusivamente puertas lógicas AND y XOR.

Retos de seguridad y escalabilidad de PSI

Los retos de seguridad y escalabilidad a los que se enfrentan todos estos protocolos para calcular la intersección privada de conjuntos son muy variados:

• Los protocolos más eficientes funcionan para conjuntos pequeños de unos pocos cientos o miles de elementos. Sin embargo, en muchas aplicaciones reales se necesitan comparar conjuntos de miles de millones de datos, lo que exige encontrar alternativas más rápidas.
• Además de exigir pocas operaciones para su funcionamiento, es importante minimizar las comunicaciones para intercambio de datos entre las partes.
• No todos los agentes implicados van a jugar según las normas. En computación segura multipartita se consideran dos tipos de adversario: semihonesto (o pasivo) y malicioso (o activo). El adversario semihonesto trata de obtener la mayor cantidad de información posible de la ejecución de un determinado protocolo, sin desviarse de los pasos del protocolo. Más peligroso y realista es el adversario malicioso, porque se desvía arbitrariamente de los pasos del protocolo para jugar con ventaja y obtener más información que los demás. Los protocolos PSI robustos ante adversarios maliciosos son considerablemente más pesados y menos eficientes que los protocolos resistentes a adversarios semihonestos.
• Los enfoques de PSI más sencillos filtran información: como mínimo, el número de elementos en cada conjunto y el número de elementos en el conjunto intersección. En las aplicaciones en las que ni siquiera es aceptable filtrar esta información, se requieren protocolos más seguros, que por desgracia requieren mayor número de operaciones y mayor ancho de banda.

Cuanto más avancen la nube y el Big Data, mayor será la demanda de PSI

A medida que las leyes y normativas de protección de datos evolucionan en un esfuerzo por salvaguardar la esfera privada de la vida de los ciudadanos, la intersección privada de conjuntos hará posible que las organizaciones públicas y privadas continúen generando conocimientos a partir del Big Data que beneficien al ciudadano, a la vez que se satisfacen las regulaciones de privacidad.

En junio de 2019 Google anunció una herramienta para realizar operaciones sobre la intersección de conjuntos bautizada como Private Join and Compute. Según la nota de prensa:

«Utilizando este protocolo criptográfico, dos partes pueden cifrar sus identificadores y datos asociados y luego unirlos en una consulta. Pueden entonces hacer ciertos tipos de cálculos sobre el conjunto de datos solapados para obtener información útil de ambos conjuntos de datos en conjunto. Todas las entradas (identificadores y sus datos asociados) permanecen totalmente cifradas y son ilegibles durante todo el proceso. Ninguna de las partes revela nunca sus datos en bruto, pero pueden seguir respondiendo a las preguntas que se les plantean utilizando la salida del cálculo. Este resultado final es lo único que se descifra y se comparte en forma de estadísticas agregadas como, por ejemplo, un recuento, una suma o un promedio de los datos de ambos conjuntos.

Private Join and Compute combina la intersección privada de conjuntos con el cifrado totalmente homomórfico para proteger los datos individuales. El siguiente vídeo ofrece una idea de su funcionamiento:

PSI supone la intersección entre la voracidad de datos de las grandes organizaciones y el derecho a la privacidad de los ciudadanos. Gigantes tecnológicos como Google, Microsoft o Baidu están invirtiendo enormes sumas de dinero y de neuronas criptográficas en estas tecnologías. En los próximos meses veremos hacia donde viran las aplicaciones de análisis masivo de datos, si a favorecer al ciudadano con mejores servicios o a erosionar aún más su maltrecha privacidad. Porque, como sentenció el criptógrafo Phil Rogaway:

La vigilancia que preserva la privacidad no deja de ser vigilancia.