El problema de los millonarios de Yao

Problema en matemáticas

El problema de los millonarios de Yao es un problema de computación multipartita seguro introducido en 1982 por el científico informático y teórico computacional Andrew Yao . El problema trata de 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 . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\geq b}$ ${\displaystyle a}$ ${\displaystyle 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, incluidas soluciones físicas basadas en tarjetas. ^[1] La primera solución, presentada por Yao, es exponencial en el tiempo y el espacio. ^[2]

Protocolos y pruebas

El protocolo de Hsiao-Ying Lin y Wen-Guey Tzeng

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

Denote la codificación 0 de s como y la 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\}.}$

Entonces, el protocolo ^[3] se basa en la siguiente afirmación:

Supongamos que a y b son cadenas binarias de longitud n bits.

Entonces, si los conjuntos y tienen un elemento común (donde a y b son las codificaciones binarias de los números enteros correspondientes). ${\displaystyle a>b}$ ${\displaystyle S_{a}^{1}}$ ${\displaystyle S_{b}^{0}}$

El protocolo aprovecha esta idea para crear una solución práctica al problema de los millonarios de Yao realizando una intersección de conjuntos privados entre y . ${\displaystyle S_{a}^{1}}$ ${\displaystyle S_{b}^{0}}$

El protocolo de Ioannidis y Ananth

El protocolo ^[4] utiliza una variante de transferencia ignorante , llamada transferencia ignorante 1-2. En esa transferencia, se transfiere un bit de la siguiente manera: un emisor tiene dos bits y . El receptor elige , y el emisor envía con el protocolo de transferencia ignorante de tal manera que ${\displaystyle S_{0}}$ ${\displaystyle S_{1}}$ ${\displaystyle i\in \{0,1\}}$ ${\displaystyle S_{i}}$

1. El receptor no recibe ninguna información sobre , ${\displaystyle S_{(1-i)}}$
2. El valor de no está expuesto al remitente. ${\displaystyle i}$

Para describir el protocolo, el número de Alice se indica como , el número de Bob como , y se supone que la longitud de su representación binaria es menor que para algunos . El protocolo sigue los siguientes pasos. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle d\in \mathbb {N} }$

1. Alice crea una matriz de tamaño de números de bits, donde es la longitud de la clave en el protocolo de transferencia inconsciente. Además, elige dos números aleatorios y , donde y . ${\displaystyle K}$ ${\displaystyle d\times 2}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle 0\leq u<2k}$ ${\displaystyle v\leq k}$
2. ${\displaystyle K_{ijl}}$será el bit -ésimo del número que aparece en la celda (donde indica el bit menos significativo ). Además, se denota como el bit -ésimo del número de Alice . Para cada , Alice realiza las siguientes acciones. ${\displaystyle l}$ ${\displaystyle K_{ij}}$ ${\displaystyle l=0}$ ${\displaystyle a_{i}}$ ${\displaystyle i}$ ${\displaystyle a}$ ${\displaystyle i}$ ${\displaystyle 1\leq i\leq d}$
   1. Por cada bit que ella establece y bits aleatorios. ${\displaystyle j\geq v}$ ${\displaystyle K_{i1j}}$ ${\displaystyle K_{i2j}}$
   2. Si , sea , en caso contrario sea y para cada conjunto en un bit aleatorio. ${\displaystyle a_{i}=1}$ ${\displaystyle l=1}$ ${\displaystyle l=2}$ ${\displaystyle j,\ 0\leq j\leq 2\cdot i-1}$ ${\displaystyle K_{ilj}}$
   3. Para establecer y para . ${\displaystyle m=2\cdot i}$ ${\displaystyle K_{il(m+1)}=1}$ ${\displaystyle K_{ilm}}$ ${\displaystyle a_{i}}$
   4. Para cada , será un número de bits aleatorio, y será otro número de bits donde todos los bits excepto los dos últimos son aleatorios, y los dos últimos se calculan como y , donde es la operación XOR bit a bit . ${\displaystyle i,1\leq i<d}$ ${\displaystyle S_{i}}$ ${\displaystyle k}$ ${\displaystyle S_{d}}$ ${\displaystyle k}$ ${\displaystyle S_{d(k-1)}=1\oplus \bigoplus _{j=1}^{d-1}S_{j(k-1)}\oplus \bigoplus _{j=1}^{d}K_{j1(k-1)}}$ ${\displaystyle S_{d(k-2)}=1\oplus \bigoplus _{j=1}^{d-1}S_{j(k-2)}\oplus \bigoplus _{j=1}^{d}K_{j1(k-2)}}$ ${\displaystyle \bigoplus }$
   5. Para el conjunto . Donde indica la rotación bit a bit de hacia la izquierda en bits. ${\displaystyle l=1,2}$ ${\displaystyle K'_{ij}=\operatorname {rot} (K_{il}\oplus S_{i},u)}$ ${\displaystyle \operatorname {rot} (x,t)}$ ${\displaystyle x}$ ${\displaystyle t}$
3. Para cada , Bob transfiere con el protocolo de transferencia inconsciente, donde , y es el -ésimo bit de . ${\displaystyle i}$ ${\displaystyle 0\leq i\leq d}$ ${\displaystyle K'_{il}}$ ${\displaystyle l=b_{i}+1}$ ${\displaystyle b_{i}}$ ${\displaystyle i}$ ${\displaystyle b}$
4. Alice le envía a Bob . ${\displaystyle N=\operatorname {rot} \left(\bigoplus _{j=1}^{d}S_{j},u\right)}$
5. Bob calcula el XOR bit a bit de todos los números que obtuvo en el paso 3 y del paso 4. Bob escanea el resultado de izquierda a derecha hasta que encuentra una secuencia grande de bits cero. Sea el bit a la derecha de esa secuencia ( no es cero). Si el bit a la derecha de es igual a 1, entonces , de lo contrario . ${\displaystyle N}$ ${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle a\geq b}$ ${\displaystyle a<b}$

Prueba

Exactitud

Bob calcula el resultado final a partir de , y el resultado depende de . K , y por lo tanto c también, se pueden dividir en 3 partes. La parte izquierda no afecta el resultado. La parte derecha tiene toda la información importante, y en el medio hay una secuencia de ceros que separa esas dos partes. La longitud de cada partición de c está vinculada al esquema de seguridad. ${\displaystyle N\oplus \bigoplus _{i=1}^{d}K'_{i(b_{i}+1)}=\operatorname {rot} \left(\bigoplus _{i=1}^{d}K_{i(b_{i}+1)},u\right)}$ ${\displaystyle c=\bigoplus _{i=1}^{d}K_{i(b_{i}+1)}}$

Para cada i , solo uno de tiene una parte derecha distinta de cero, y es si , y en caso contrario. Además, si , y tiene una parte derecha distinta de cero, entonces tiene también una parte derecha distinta de cero, y los dos bits más a la izquierda de esta parte derecha serán los mismos que el de . Como resultado, la parte derecha de c es una función de las entradas que Bob transfirió corresponden a los bits únicos en a y b , y los únicos bits en la parte derecha en c que no son aleatorios son los dos más a la izquierda, exactamente los bits que determinan el resultado de , donde i es el bit de orden más alto en el que a y b difieren. Al final, si , entonces esos dos bits más a la izquierda serán 11, y Bob responderá que . Si los bits son 10, entonces , y responderá . Si , entonces no habrá parte derecha en c , y en este caso los dos bits más a la izquierda en c serán 11, y indicarán el resultado. ${\displaystyle K_{i1},K_{i2}}$ ${\displaystyle K_{i1}}$ ${\displaystyle a_{i}=1}$ ${\displaystyle K_{i2}}$ ${\displaystyle i>j}$ ${\displaystyle K_{il}}$ ${\displaystyle K_{il}\oplus K_{jl}}$ ${\displaystyle A_{il}}$ ${\displaystyle a_{i}>b_{i}}$ ${\displaystyle a_{i}>b_{i}}$ ${\displaystyle a\geq b}$ ${\displaystyle a_{i}<b_{i}}$ ${\displaystyle a<b}$ ${\displaystyle a=b}$

Seguridad

La información que Bob envía a Alice es segura porque se envía a través de una transferencia inconsciente, lo cual es seguro.

Bob recibe 3 números de Alice:

1. ${\displaystyle \operatorname {rol} (K_{i(1+b_{i})}\oplus S_{i},u)}$. Cada Bob recibe un número de este tipo, y es aleatorio, por lo que no se transforma ninguna información segura. ${\displaystyle i}$ ${\displaystyle S_{i}}$
2. N . Se trata de una operación XOR de números aleatorios y, por lo tanto, no revela información. La información relevante se revela solo después de calcular c .
3. c . Lo mismo ocurre con c . La parte izquierda de c es aleatoria, y la parte derecha también lo es, excepto los dos bits más a la izquierda. Para deducir cualquier información de esos bits es necesario adivinar otros valores, y la probabilidad de adivinarlos correctamente es muy baja.

Complejidad

La complejidad del protocolo es . Alice construye un número de longitud d para cada bit de a , y Bob calcula XOR d veces de números de longitud d . La complejidad de esas operaciones es . La parte de comunicación también requiere . Por lo tanto, la complejidad del protocolo es ${\displaystyle O(d^{2})}$ ${\displaystyle O(d^{2})}$ ${\displaystyle O(d^{2})}$ ${\displaystyle O(d^{2}).}$

Véase también

• Criptografía
• Sociedad Anónima
• Computación segura entre múltiples partes
• Problema del millonario socialista , una variante en la que los millonarios desean determinar si sus fortunas son iguales.

Referencias

1. Miyahara, Daiki; Hayashi, Yu-ichi; Mizuki, Takaaki; Sone, Hideaki (2020). "Implementaciones prácticas basadas en tarjetas del protocolo del millonario de Yao". Ciencias de la Computación Teórica . 803 : 207–221. doi : 10.1016/j.tcs.2019.11.005 .
2. Yao, Andrew C. (noviembre de 1982). "Protocolos para cálculos seguros". 23.° Simposio anual sobre fundamentos de la informática (sfcs 1982) . Vol. 1. págs. 160–164. doi :10.1109/SFCS.1982.88.
3. Lin, Hsiao-Ying; Tzeng, Wen-Guey (7 de junio de 2005). "Una solución eficiente al problema de los millonarios basada en el cifrado homomórfico". Criptografía aplicada y seguridad de redes . Apuntes de clase en informática. Vol. 3531. págs. 456–466. CiteSeerX 10.1.1.75.4917 . doi :10.1007/11496137_31. ISBN .  978-3-540-26223-7.
4. Ioannidis, I.; Grama, A. (2003). "Un protocolo eficiente para el problema de los millonarios de Yao". 36.ª Conferencia Internacional Anual de Hawái sobre Ciencias de Sistemas, 2003. Actas de la . IEEE. pp. 6 págs. CiteSeerX 10.1.1.110.8816 . doi :10.1109/hicss.2003.1174464. ISBN  978-0769518749.S2CID6907526  .​