Problema de los millonarios

De Wikipedia, la enciclopedia libre

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:[1]

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

Soluciones[editar]

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:

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

Referencias[editar]

  1. Cryptographically Secure Multiparty Computation and Distributed Auctions Using Homomorphic Encryption. Anunay Kulshrestha et al. 2017
  2. Protocols for secure computations Andrew C. Yao. 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982
  3. An Efficient Protocol for Yao's Millionaires' Problem. Ioannis Ioannidis et al. Purdue University 2003
  4. 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
  5. Efficient Cryptographic Protocol Design Based on Distributed El Gamal Encryption Archivado el 8 de febrero de 2018 en Wayback Machine.. Felix Brandt. Information Security and Cryptology - ICISC 2005. Springer Verlag 2005