Supongamos que dos personas, Mabel y Javier, desean saber si cobran la misma cantidad de dinero, pero ninguno de ellos está dispuesto a revelar su cifra exacta.

Ni siquiera a un intermediario.

¿Cómo pueden comprobarlo sin sacrificar su privacidad?

La respuesta la encontramos en uno de los problemas clásicos y más elegantes de la criptografía moderna: el Problema del Millonario Socialista.

Para entenderlo con claridad, utilizaremos un ejemplo basado en cajas y llaves, sencillo pero profundamente efectivo.

En las explicaciones tradicionales de criptografía, es habitual encontrarse con los personajes de Alice y Bob. Son como los actores de reparto de toda historia de cifrado: Alice envía, Bob recibe, y mientras tanto, alguien malintencionado (generalmente Eve) intenta escuchar a escondidas.

Sin embargo, en esta explicación utilizaremos a Mabel y Javier como protagonistas. Porque, sinceramente, después de cientos de ejemplos con Alice y Bob, ya era hora de darles vacaciones.

Respecto al nombre del problema, «socialista» tiene su propia ironía:
aunque hablamos de millonarios, el objetivo aquí no es ostentar ni competir, sino asegurar que ambas partes están en igualdad de condiciones, sin necesidad de revelar ni una sola cifra.
Una actitud sorprendentemente altruista para quienes acumulan fortunas, lo cual no deja de ser un pequeño homenaje sarcástico a las buenas intenciones en el mundo de la criptografía.

Un acto casi utópico en el mundo real, donde la idea de comparar fortunas sin envidia ni ostentación parece sacada directamente de un manifiesto de buenas intenciones.

Millonarios sí, pero socialistas de corazón… al menos en este protocolo.

El protocolo paso a paso para todos los públicos

Paso 1: Preparación de las cajas

Mabel va a una tienda de artículos de oficina y compra cuatro cajas con cerradura, cada una etiquetada con un salario diferente:
10 €, 20 €, 30 € y 40 € por hora.

Cada caja está cerrada y, originalmente, Mabel tiene las llaves de todas ellas.

Paso 2: Selección de la llave correspondiente

Mabel descarta todas las llaves excepto la de la caja que corresponde a su propio salario.
Por ejemplo, si Mabel gana 20 € por hora, únicamente conserva la llave de la caja etiquetada como 20 €.

El resto de las llaves son destruidas o descartadas, asegurando que no podrá abrir las demás cajas en el futuro.

Paso 3: Entrega de las cajas a Javier

Mabel entrega las cuatro cajas cerradas a Javier.

Ahora, Javier tiene en su poder las cajas correspondientes a todos los valores posibles, pero todas siguen cerradas.

Paso 4: Introducción de los mensajes

En privado, Javier introduce un papelito en cada caja:

En la caja que representa su salario real, coloca un papel con la palabra «sí«.
En todas las demás cajas, coloca un papel con la palabra «no«.

Por ejemplo, si Javier gana 30 € por hora, pondrá «sí» en la caja de 30 € y «no» en las demás.

Después, cierra nuevamente todas las cajas.

Paso 5: Devolución de las cajas

Javier devuelve las cajas cerradas a Mabel.

Ahora, Mabel tiene de nuevo las cajas, pero sigue sin conocer el contenido de ninguna salvo de aquella cuya llave ha conservado.

Paso 6: Apertura selectiva

Mabel utiliza la única llave que posee (en nuestro ejemplo, la de 20 €) para abrir solo la caja correspondiente a su salario.

Al abrirla, encuentra un papel con un mensaje:

Si el papel dice «sí«, sabrá que Javier gana exactamente lo mismo que él.
Si el papel dice «no«, sabrá que sus salarios son diferentes.

Importante: Mabel no puede abrir ninguna otra caja ni conocer el salario real de Javier si no coincide con el suyo.

Y Javier , por su parte, tampoco sabe el salario exacto de Mabel, ya que desconoce qué llave ha conservado.

¿Qué está ocurriendo realmente?

Aunque en nuestro ejemplo hemos utilizado cajas físicas y llaves, en la práctica real el proceso se implementa mediante técnicas criptográficas avanzadas.

Concretamente, este tipo de protocolo corresponde a una Transferencia Ajena (Oblivious Transfer):
un método en el que una parte transfiere múltiples mensajes posibles a otra parte, pero desconoce cuál de ellos ha sido efectivamente recibido.

En nuestro caso:

Javier envió una respuesta para cada cantidad posible de dinero.
Mabel solo recibió la respuesta correspondiente a su propio salario.
Javier no sabe cuál de los mensajes fue realmente leído.

Este tipo de construcciones criptográficas tienen aplicaciones fundamentales, entre otras en:

Protocolos de comparación privada.
Computación multipartita segura.
Situaciones donde la privacidad de la elección es tan importante como el propio contenido transmitido.

Esta explicación sigue la línea conceptual del artículo original en que se inspira este ejemplo.
En aquel texto, se indica que el proceso de Alice y Bob corresponde técnicamente a una transferencia inconsciente:
Alice transfiere muchos mensajes, pero permanece ignorante de cuál de ellos Bob ha leído.

Sin embargo, conviene señalar que cierto nivel de confianza es necesario para que el protocolo funcione correctamente en el modelo físico:

Si Mabel mintiera sobre su salario y fingiera conservar una llave diferente, Javier no tendría forma inmediata de detectarlo.
Del mismo modo, Mabel podría manipular la apertura o la devolución de las cajas.

Estas posibilidades de trampa son propias del modelo físico y pueden mitigarse, en su mayoría, mediante mejoras en el protocolo:
por ejemplo, Mabel podría mostrar a Javier el contenido extraído como prueba, o diseñarse mecanismos de auditoría más robustos.

No obstante, en implementaciones informáticas modernas, donde se emplea criptografía de clave pública en lugar de objetos físicos, muchos de estos problemas desaparecen:
los protocolos se vuelven más rigurosos, difíciles de manipular, y se pueden garantizar propiedades como la imparcialidad y la no-revelación mediante construcciones matemáticas formales.

Así, aunque el ejemplo de las cajas ayuda a entender la mecánica general, en un sistema real la robustez y la seguridad se fundamentan en algoritmos criptográficos diseñados específicamente para evitar fraudes o desviaciones en el proceso.

Protocolo Problema Millonario Socialista

Durante la realización del Máster de Ciberseguridad y Privacidad en la Universitat Oberta de Catalunya (UOC), en la asignatura de Privacidad, hemos trabajado sobre el protocolo de comparación segura conocido como el Problema del Millonario Socialista.

En el material docente proporcionado —concretamente en el documento titulado «Protocolos criptográficos que preservan la privacidad» elaborado por Jordi Herrera Joancomartí y Cristina Pérez Solà— se presenta un esquema de ejecución resumido, utilizando como protagonistas a los personajes clásicos de Alice y Bob.

Con el objetivo de facilitar la comprensión y la implementación práctica de este protocolo, en este artículo voy a presentar una adaptación del procedimiento original, respetando su estructura fundamental pero añadiendo aclaraciones que considero relevantes.

Durante el análisis detallado y la puesta en práctica del protocolo, he detectado algunos aspectos que pueden inducir a confusión, particularmente cuando se intenta trasladarlo directamente al código.

Uno de los puntos más críticos es el cálculo presentado en el paso 12:
en el material original no se especifica de forma explícita que debe aplicarse la operación mod p al resultado.
Esta omisión, aparentemente menor, puede derivar en dos problemas graves:

Funcionamiento incorrecto del protocolo: si no se reduce mod p, los resultados intermedios no se mantienen en el grupo seguro definido por el sistema criptográfico.
Errores de ejecución: cuando se utilizan valores grandes (como ocurre habitualmente en criptografía de clave pública), las operaciones de potenciación y multiplicación pueden provocar desbordamientos o fallos en la ejecución del programa.

Por estos motivos, en la adaptación que presento a continuación se especifica de manera explícita el uso de la operación modular en todos los pasos donde es necesaria, además de realizar pequeñas mejoras en la organización y descripción de los intercambios de mensajes para evitar ambigüedades.

La intención no es alterar el protocolo original, sino reforzar su claridad y facilitar su correcta implementación en entornos reales.

Antes de presentar el protocolo, es fundamental definir los principales elementos utilizados:

p: es un número primo grande que define el módulo del sistema.
Todas las operaciones del protocolo se realizan en el grupo de enteros módulo p(??).
h: es un generador de un subgrupo de p(??) (el conjunto de los elementos invertibles módulo p).
Debe ser un valor elegido adecuadamente para garantizar la seguridad del protocolo.
x: es el valor secreto que representa la fortuna de Alice.
y: es el valor secreto que representa la fortuna de Bob.

El objetivo principal del protocolo es permitir a Alice y Bob comparar sus fortunas sin revelar el valor exacto de xni de y.

Paso	Acción de Alice	Acción de Bob
1	Elige dos valores aleatorios a1 y a2 tales que a1, a2 ∈? ??	Elige dos valores aleatorios b1 y b2 tales que b1, b2 ∈? ??
2	Calcula: ha1 = h^a1 (mod p) ha2 = h^a2 (mod p)	Calcula: hb1 = h^b1 (mod p) hb2 = h^b2 (mod p)
3	Envía ha1 y ha2 a Bob →
4		← Envía hb1 y hb2 a Alice
5	Verifica que: hb1 ≠ 1 (mod p) hb2 ≠ 1 (mod p)	Verifica que: ha1 ≠ 1 (mod p) ha2 ≠ 1 (mod p)
6	Calcula: g = (hb1)^a1 (mod p) f = (hb2)^a2 (mod p)	Calcula: g = (ha1)^b1 (mod p) f = (ha2)^b2 (mod p)
7	Elige r ∈? ??	Elige s ∈? ??
8	Calcula: P_a = f^r (mod p) Q_a = h^r g^x (mod p)	Calcula: P_b = f^s (mod p) Q_b = h^s g^y (mod p)
9	Envía (P_a, Q_a) a Bob →
10		← Envía (P_b, Q_b) a Alice
11	Comprueba que: P_a ≠ P_b (mod p) Q_a ≠ Q_b (mod p)	Comprueba que: P_a ≠ P_b (mod p) Q_a ≠ Q_b (mod p)
12	Calcula: D_a = (Q_a × Q_b^-1)^a2 (mod p)	Calcula: D_b = (Q_a × Q_b^-1)^b2 (mod p)
13	Envía (D_a) a Bob →
14		← Envía (D_b) a Alice
15	Calcula: c = (D_b)^a2 (mod p)	Calcula: c = (D_a)^b2 (mod p)
16	Comprueba que: c = (P_a × P_b^-1) (mod p)	Comprueba que: c = (P_a × P_b^-1) (mod p)

Al concluir la ejecución del protocolo, si la última comprobación sobre el valor ccc resulta correcta,
tanto Alice como Bob pueden estar convencidos de que sus fortunas son iguales,
sin que ninguno haya revelado su cantidad al otro.

El diseño del procedimiento asegura que:

Si los valores son iguales, las comprobaciones serán consistentes y el protocolo finalizará de forma satisfactoria.
Si los valores son diferentes, el protocolo detectará la discrepancia y no validará la igualdad.

Así, el Problema del Millonario Socialista permite alcanzar una conclusión segura y privada, respetando plenamente el principio de mínima revelación de información en el proceso de comparación.

Fuentes

https://web.archive.org/web/20221225214935/http://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation
Protocolos criptográficos que preservan la privacidad – Jordi Herrera Joancomartí y Cristina Pérez Solà
https://es.wikipedia.org/wiki/Problema_de_los_millonarios

Entendiendo el Problema del Millonario Socialista sin complicaciones