En 1982, Andrew C. Yao planteó el problema de los millonarios, consistente en determinar, sin utilizar un notario, la persona más rica entre un conjunto de participantes manteniendo como privado el montante de cada fortuna. El problema de los millonarios representa una clase de problemas de computación distribuida que han de resolverse en condiciones de privacidad y ausencia de infraestructura, por ejemplo entre un conjunto de dispositivos móviles interconectados en una red ad-hoc. El problema se denomina genéricamente Multi-party Secure Computation, SMC (computación distribuida segura) y es de aplicación en pujas, votaciones, redes vehiculares, etc. Un ejemplo ilustrativo reciente es la utilización de SMC para evitar el riesgo de colisión entre satélites artificiales sin que cada agencia tenga que revelar las órbitas de sus satélites.
En esta charla introducimos el problema y un método de resolución de SMC, y lo aplicamos para resolver una votación secreta sin la necesidad de confiar el recuento de los votos a una autoridad.
Conferencia impartida en la Euskal Encounter 24, celebrada en el BEC del 22 al 25 de julio.
Podcast: Reproducir en una nueva ventana | Descargar