Problema de los millonarios

El problema de los millonarios es un problema de computación segura multipartita introducido en 1982 por Andrew C. Yao. El problema se enuncia de la siguiente forma:

Dos millonarios A y B tienen respectivamente una riqueza ${\displaystyle a}$ y ${\displaystyle b}$. Ambos millonarios quieren saber cual de ellos es más rico sin revelarse entre ellos la cantidad de dinero que tiene cada uno. Es decir, lo que se quiere es un protocolo que permite a A y B saber si la condición ${\displaystyle a<b}$ es cierta, pero sin que se tenga que revelar entre ellos el valor de su riqueza respectiva.

Notar que si ${\displaystyle a}$ y ${\displaystyle b}$ son representaciones binarias de los dos número y ${\displaystyle a_{i}}$ y ${\displaystyle b_{i}}$ son los i-ésimos digits empezando por la derecha, la función de 'más grande que' puede ser reformulada de la siguiente forma:^[1]​

${\displaystyle [a>b]\Leftrightarrow \bigvee _{j=1}^{k}(a_{j}\land \neg b_{j}\land \bigwedge _{d=j+1}^{k}(\neg (a_{d}\oplus b_{d}))}$

donde k es el tamaño en bits del mayor número.

La primera solución fue presentada por Andrew C. Yao^[2]​ pero el protocolo tenía tiempo y espacio exponencial-

Posteriormente ha habido varias propuestas. Por ejemplo:

• En 2003 Ioannis Ioannidis y Ananth Grama, usando una variante de transferencia inconsciente llamada transferencia inconsciente 1-2, consigue complejidad ${\displaystyle O(d^{2})}$.^[3]​
• En 2005 Hsiao-Ying Lin and Wen-Guey Tzeng proponen una solución basada en cifrado homomórfico.^[4]​
• En 2005 Felix Brandt propone otro protocolo basándose en el algoritmo de Cifrado ElGamal, el cual es un cifrado homomórfico.^[5]​

La resolución de este problema tiene múltiples aplicaciones.