Computación segura bipartita

La Computación Segura Bipartita o 2PC (siglas del inglés Secure Two-Party Computation) es un subconjunto de la Computación segura multipartita, cuyo objetivo es crear protocolos que permitan a dos partes computar de manera conjunta una función arbitraria de sus entradas sin compartir entre ellas el valor de sus entradas.

Es frecuente que la computación segura bipartita involucre funciones criptográficas dando lugar a protocolos criptográficos bipartitos

Uno de los ejemplos mejor conocidos de 2PC es el Problema de los Millonarios, en el cual dos partes, A y B, son millonarios que quieren determinar quien es el más rico sin revelar el patrimonio de cada uno. Formalmente A tiene una riqueza de $a$, B tiene una riqueza de $b$, y se quiere determinar si es verdad que $a\geq b$ sin revelar los valores de $a$ o $b$.​

Un problema de contexto similar (aunque su propuesta es un poco más acotada que la de Yao) fue planteado por Manuel Blum,​ donde se desea lanzar una moneda a través de un teléfono.

Formalización

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, Andrew C. 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 de los millonarios, 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_{\alpha }$ y $D_{\alpha }$ dos funciones de cifrado y descifrado (en un sistema de cifrado simétrico) bajo la clave $\alpha$, respectivamente.

• Bob escoge aleatoreamente un entero $x$ de $N$ bits, y calcula privadamente el valor $k=E_{\alpha }(x)$.
• Bob envía a Alice el valor $k-j+1$.
• Alice calcula privadamente los valores $y_{u}=D_{\alpha }(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 unidireccional 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​ 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 solo 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 solo 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,​ una optimización del protocolo de Yao, mejorando su rendimiento. En el mismo 2004, Y. Lindell y B. Pinkas​ desarrollan una prueba de seguridad para el protocolo de Yao para adversarios maliciosos, para finalmente el año 2007 implementar un protocolo eficiente.​ 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.

Enlaces externos

• Zero Knowledge Proof (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). 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).

• Datos: Q7444883