El problema de los millonarios de Yao es un problema de computación seguro de múltiples partes introducido en 1982 por el científico informático y teórico computacional Andrew Yao . El problema habla 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 verdadero o falso sin revelar los valores reales de y .
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 tiempo y espacio. [1]
Protocolos y prueba
El protocolo de Hsiao-Ying Lin y Wen-Guey Tzeng
Dejar ser una cadena binaria de longitud n .
Denote la codificación 0 de s comoy codificación 1 de s como
Entonces, el protocolo [2] se basa en la siguiente afirmación:
- Supongamos que un y b son cadenas binarias de longitud n bits.
- Luego si los conjuntos y tienen un elemento común (donde a y b son las codificaciones binarias de los números enteros correspondientes).
El protocolo aprovecha esta idea en una solución práctica al problema de los millonarios de Yao al realizar una intersección de conjuntos privados entre y .
El protocolo de Ioannidis y Ananth
El protocolo [3] utiliza una variante de transferencia inconsciente , llamada transferencia 1-2 inconsciente. En esa transferencia, un bit se transfiere de la siguiente manera: un remitente tiene dos bits y . El receptor eligey el remitente envía con el protocolo de transferencia inconsciente tal que
- el receptor no obtiene ninguna información sobre ,
- El valor de no está expuesto al remitente.
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.
- 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 , dónde y .
- será el -th bit del número que aparece en la celda (dónde indica el bit menos significativo ). Además, se denota como el -th bit del número de Alice . Para cada, Alice realiza las siguientes acciones.
- Por cada pedacito ella establece y a bits aleatorios.
- Si , dejar , de lo contrario deja y por cada colocar a un bit aleatorio.
- Para colocar y a .
- Para cada , será un azar -número de bits, 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 , dónde es la operación XOR bit a bit .
- Para colocar . Dóndeindica la rotación bit a bit de a la izquierda por bits.
- Para cada , Transferencias de Bob con el protocolo de transferencia inconsciente, donde , y es el -th bit de .
- Alice le envía a Bob .
- Bob calcula el XOR bit a bit de todos los números que obtuvo en el paso 3 y desde el paso 4. Bob escanea el resultado de izquierda a derecha hasta que encuentra una gran secuencia de cero bits. Dejar ser 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 .
Prueba
Exactitud
Bob calcula el resultado final de , y el resultado depende de . K , y por lo tanto también c , 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.
Por cada yo , solo uno de tiene una parte derecha distinta de cero, y es Si , y de lo 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 los de . Como resultado, la parte derecha de c es una función de las entradas de Bob transfiere corresponden a los bits únicas en una y b , y la única bits en la parte derecha en c que no son al azar son los dos más a la izquierda, exactamente los bits que determina 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, entoncesy el 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 e indicarán el resultado.
Seguridad
La información que Bob envía a Alice es segura porque se envía a través de una transferencia ajena, que es segura.
Bob recibe 3 números de Alice:
- . Para cada Bob recibe uno de esos números, y es aleatorio, por lo que no se transforma ninguna información segura.
- N . Este es un 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 .
- c . Lo mismo ocurre con c . La parte izquierda de c es aleatoria y la parte derecha también es aleatoria, excepto por los dos bits más a la izquierda. Deducir cualquier información de esos bits requiere adivinar otros valores, y la posibilidad de adivinarlos correctamente es muy baja.
Complejidad
La complejidad del protocolo es. Alice construye el número d -length para cada bit de a , y Bob calcula XOR d veces de los números d -length. La complejidad de esas operaciones es. La parte de la comunicación también toma. Por tanto, la complejidad del protocolo es
Ver también
- Criptografía
- RSA
- Computación multipartita segura
- Millonario socialista , una variante en la que los millonarios quieren determinar si sus fortunas son iguales.
enlaces externos
Referencias
- ^ Yao, Andrew C. (noviembre de 1982). "Protocolos para cálculos seguros". FOCS . 23º Simposio anual sobre los fundamentos de la informática (FOCS 1982): 160-164. doi : 10.1109 / SFCS.1982.88 .
- ^ 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 la red . Apuntes de conferencias en Ciencias de la Computación. 3531 . págs. 456–466. CiteSeerX 10.1.1.75.4917 . doi : 10.1007 / 11496137_31 . ISBN 978-3-540-26223-7.
- ^ Ioannidis, I .; Grama, A. (2003). Un protocolo eficaz para el problema de los millonarios de Yao . 36ª Conferencia Internacional Anual de Hawaii sobre Ciencias de Sistemas, 2003. Actas del . IEEE. CiteSeerX 10.1.1.110.8816 . doi : 10.1109 / hicss.2003.1174464 . ISBN 978-0769518749.