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 y . 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 es cierta, pero sin que se tenga que revelar entre ellos el valor de su riqueza respectiva.
Notar que si y son representaciones binarias de los dos número y y son los i-ésimos digits empezando por la derecha, la función de 'más grande que' puede ser reformulada de la siguiente forma:Cryptographically Secure Multiparty Computation and Distributed Auctions Using Homomorphic Encryption. Anunay Kulshrestha et al. 2017
donde k es el tamaño en bits del mayor número.
Soluciones La primera solución fue presentada por Andrew C. YaoProtocols for secure computations Andrew C. Yao. 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982 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 .An Efficient Protocol for Yao's Millionaires' Problem. Ioannis Ioannidis et al. Purdue University 2003 En 2005 Hsiao-Ying Lin and Wen-Guey Tzeng proponen una solución basada en cifrado homomórfico.An Efficient Solution to The Millionaires’ Problem Based on Homomorphic Encryption. Hsiao-Ying Lin et al. ACNS'05 Proceedings of the Third international conference on Applied Cryptography and Network Security. Springer-Verlag 2005 En 2005 Felix Brandt propone otro protocolo basándose en el algoritmo de Cifrado ElGamal, el cual es un cifrado homomórfico.Efficient Cryptographic Protocol Design Based on Distributed El Gamal Encryption . Felix Brandt. Information Security and Cryptology - ICISC 2005. Springer Verlag 2005
La resolución de este problema tiene múltiples aplicaciones.
Referencias
Categoría:Protocolos criptográficos