El problema de los millonarios de Yao

---

El problema de los millonarios de Yao es un problema de computación multiparte seguro introducido en 1982 por el científico informático y teórico computacional Andrew Yao . El problema trata sobre dos millonarios, Alice y Bob, que están interesados ​​en saber cuál de ellos es más rico sin revelar su riqueza real.

Este problema es análogo a un problema más general donde hay dos números y y el objetivo es determinar si la desigualdad es verdadera o falsa sin revelar los valores reales de y .${\ estilo de visualización a}$${\ estilo de visualización b}$${\ estilo de visualización a \ geq b}$${\ estilo de visualización a}$${\ estilo de visualización b}$

El problema de los millonarios es un problema importante en criptografía , cuya solución se utiliza en el comercio electrónico y la minería de datos . Las aplicaciones comerciales a veces tienen que comparar números que son confidenciales y cuya seguridad es importante.

Se han introducido muchas soluciones para el problema. La primera solución, presentada por Yao, es exponencial en el tiempo y el espacio. ^[1]

Sea una cadena binaria de longitud n .${\displaystyle s=s_{n}s_{n-1}\ldots s_{1}\in \{0,1\}^{n}}$

Indicar codificación 0 de s como y codificación 1 de s como${\displaystyle S_{s}^{0}=\{s_{n}s_{n-1}\ldots s_{i+1}1\mid s_{i}=0;1\leq i\leq n\ }}$${\displaystyle S_{s}^{1}=\{s_{n}s_{n-1}\ldots s_{i}\mid s_{i}=1;1\leq i\leq n\}.}$

---