Computación Bipartita

Computación Bipartita: En criptografía, Computación Bipartita Segura (Secure Two-Party Computation o 2PC) es un problema que fue inicialmente planteado por Andrew C. Yao en un trabajo^[1] del año 1982, donde introduce el Problema de los Millonarios, que plantea la necesidad de calcular el valor de una función, cuyos argumentos son valores conocidos por dos individuos quienes no desean hacerlos públicos. Un problema de contexto similar (aunque su propuesta es un poco más acotada que la de Yao) fue planteado por Manuel Blum,^[2] donde se desea lanzar una moneda a través de un teléfono.

Contenido

1 Problema 2PC

2 Ejemplos

2.1 Protocolo para el Problema de los Millonarios

2.2 Protocolo para lanzamiento de una moneda

2.3 Protocolo para lanzar una moneda basado en Hash

3 Solución a cualquier problema de 2PC

4 Otras propuestas

5 Referencias

6 Enlaces externos

Problema 2PC

El problema consiste en dos participantes Alice y Bob tienen algún dato privado, $x 1$ y $x 2$ , respectivamente. Los participantes desean calcular el valor de una función pública $F$ evaluándola en los puntos $x 1$ y $x 2$ . Un protocolo 2PC se considera seguro si ninguno de los dos participantes puede aprender alguna información adicional del dato del otro, además de la que pueda deducir del resultado de la función.

En su propuesta, Yao plantea dos escenarios posibles bajo los cuales se puede ejecutar un protocolo para 2PC:

Participantes honestos, pero curiosos

Participantes potencialmente deshonestos.

Cabe mencionar que el problema para participantes potencialmente deshonestos no fue completamente solucionado hasta el año 2007, cuando Yehuda Lindell y Benny Pinkas plantean un protocolo que es seguro antes este tipo de participantes.

Ejemplos

Protocolo para el Problema de los Millonarios

El problema, inicialmente planteado por Yao al presentar el tema de Computación Bipartita Segura, consiste en lo siguiente: Alice y Bob son dos millonarios, quienes poseen $i$ y $j$ millones respectivamente y desean saber quién posee la mayor fortuna, sin revelar cuánto dinero tiene cada uno. El protocolo propuesto para solucionar este problema en particular es el siguiente:

Sean $i$ y $j$ los valores secretos de Alice y Bob respectivamente, con $1 < i, j < 10$ . Sean $E α$ y $D α$ dos funciones de cifrado y descifrado (en un sistema de cifrado simétrico) bajo la clave $α$ , respectivamente.

Bob escoge aleatoreamente un entero $x$ de $N$ bits, y calcula privadamente el valor $k = E α (x)$ .

Bob envía a Alice el valor $k - j + 1$ .

Alice calcula privadamente los valores $y u = D α (k - j + u)$ para $u = 1..10$ .

Alice genera aleatoreamente un primo de $N$ bits, y calcula los valores $z_u = y_u (mod \ p)$ para cada $u$ . Si todos los $z u$ difieren por al menos 2 (en el sentido de la aritmética modular), parar; de otro modo, repetir hasta que los $z u$ difieran todos en al menos 2. Sean $p$ y $z u$ los valores finales.

Alice envía el primo $p$ y los siguientes 10 números a Bob: $z 1, z 2,..., z i, z i + 1 + 1, z i + 2 + 1,..., z 10 + 1$ . La suma siempre es módulo $p$ .

Bob mira el $j$ -ésimo número de la secuencia enviada por Alice, y decide que $i \geq j$ si es igual a $x(mod \ p)$ , y que $i \leq j$ de otro modo.

Bob le comunica el resultado a Alice.

Protocolo para lanzamiento de una moneda

La situación es la siguiente: Alice y Bob están divorciados y viven en ciudades distantes, por lo que deben decidir quin se queda con el auto a través del teléfono. Para esto, Alice lanza una moneda al aire y Bob debe adivinar si salió cara o sello, pero Bob debe tener una certeza de que Alice no manipula el resultado a su favor. El protocolo planteado originalmente por Blum es como sigue:

Bob elige aleatoreamente dos primos $p 1$ y $p 2$ , congruentes con $3(mod \ 4)$ . Calcula $n = p 1 p 2$ y se lo envía a Alice.

Alice comprueba que $n=1(mod \ 4)$ y que para algún $x$ existe y tal que $x^2 = y^2 (mod \ n)$ .

Alice elige valores aleatorios $x i$ y envía a Bob sus cuadrados $(mod \ n)$ junto con $n$ .

Bob comprueba $n$ , y envía a Alice $n$ , $x^2 (mod \ n)$ y $b i$ .

Alice comprueba $n$ y $x^2 (mod \ n)$ , y determina la secuencia aleatoria: 1 si Bob acertó sobre $x i$ , y −1 en otro caso.

Alice envía a Bob los $x i$ .

Bob comprueba los cuadrados.

Protocolo para lanzar una moneda basado en Hash

Posteriormente se han creado diversas soluciones más eficientes y más seguras para este problema, entre ellas destaca la utilización de funciones de Hash para ocultar el resultado. Asumiendo la existencia de una función unidirecional H, el protocolo es el siguiente:

Alice y Bob acuerdan una función $H$ .

Alice elige un entero $x$ secretamente (lanzamiento de la moneda), y calcula $H (x)$ y se lo envía a Bob.

Bob dice a Alice si cree que $x$ es par o impar (apuesta de Bob).

Alice comunica a Bob si acertó o no, y lo convence enviándole $x$ (Bob puede calcular entonces $H (x)$ , verificando que sea igual al que recibió).

Solución a cualquier problema de 2PC

En 1986, Andrew C. Yao propone una solución^[3] para el problema de 2PC para calcular cualquier función F. Para esto crea un circuito, representación gráfica de la función booleana, y uno de los participantes se encarga de hacerlo ilegible, es decir, codifica cada una de las entradas a las compuertas del circuito con una máscara que sólo ella conoce y que además tiene su entrada pre-cargada. La forma de codificar estas entradas es cifrando los valores posibles bajo diversas claves sólo conocidas por el participante que lo hace. El protocolo completo funciona de la siguiente forma:

Alice construye un circuito booleano ilegible, el que contiene tablas para cada compuerta codificadas con una máscara y con su entrada pre-llenada. Luego le envía el circuito a Bob.

Bob le pide a Alice la codificación de los valores que debe ingresar a la entrada principal mediante transferencia inconsciente.

Bob ha recibido un circuito ilegible y la correspondencia de su entrada con los valores codificados de la tabla. Corre el circuito y obtiene el resultado de la función que representa el circuito.

Bob le envía el resultado a Alice.

Otras propuestas

La gran mayoría de los protocolos desarrollados a la fecha utilizan como base la propuesta de Yao de circuitos booleanos. El año 2004 un grupo de investigadores desarrollan Fairplay,^[4] una optimización del protocolo de Yao, mejorando su rendimiento. En el mismo 2004, Y. Lindell y B. Pinkas^[5] desarrollan una prueba de seguridad para el protocolo de Yao para adversarios maliciosos, para finalmente el año 2007 implementar un protocolo eficiente.^[6] Finalmente en 2007, S. Jarecki y V. Shmatikov plantean una alternativa para resolver 2PC, que consiste en enviar los valores de entrada usando Compromiso de Bits.

Referencias

↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164

↑ Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981, pp. 11-15, 1981, reprinted in SIGACT News vol. 15, pp. 23-27, 1983.

↑ A. Yao. How to Generate and Exchange Secrets. In 27th FOCS, pages 162--167, 1986. 21

↑ D. Malkhi, N. Nisan, B. Pinkas and Y. Sella. Fairplay - A Secure Two-Party Computation System. Proceedings of Usenix Security '2004, August 9-13, 2004.

↑ Y. Lindell and B. Pinkas. A Proof of Security of Yao's Protocol for Two-Party Computation. To appear in the Journal of Cryptology.

↑ Y. Lindell and B. Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In Proc. EUROCRYPT, 2007

Enlaces externos

Zero Knowledge Proof Artículo ilustrativo de lo que es una Demostración de Nula Divulgación.

Solución al problema de los Millonarios Descripción del protocolo de Yao (en inglés).

The Fairplay Project — Incluye un paquete de software para Computación Bipartita Segura (en inglés).

Categoría:
Protocolos de cifrado