[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Computación segura bipartita wiki: info, historia y vídeos

Detalles: Categoría: INTERNET

videos internet

Computación segura bipartita

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

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

Uno de los ejemplos mejor conocidos de 2PC es el Inconveniente de los Millonarios, en el que 2 partes, A y B, son millonarios que desean determinar quien es el más rico sin descubrir el partrimonio de cada uno de ellos. Formalmente A tiene una riqueza de a, B tiene una riqueza de b, y se quiere determinar si es cierto que a=b sin descubrir los valores de a o bien b.

Un inconveniente de contexto afín (si bien su propuesta es un tanto más delimitada que la de Yao) fue planteado por Manuel Blum, donde se quiere lanzar una moneda mediante un teléfono.

Formalización

El inconveniente consiste en 2 participantes Alice y Bob tienen algún dato privado, x1 y x2, respectivamente. Los participantes desean calcular el valor de una función pública F evaluándola en los puntos x1 y x2. Un protocolo 2PC se considera seguro si ninguno de los 2 participantes puede aprender alguna información auxiliar del dato del otro, aparte de la que pueda inferir del resultado de la función.

En su propuesta, Andrew C. Yao plantea 2 escenarios posibles bajo los que se puede ejecutar un protocolo para 2PC:

Participantes francos, mas curiosos
Participantes potencialmente indecentes.

Cabe mentar que el inconveniente para participantes potencialmente indecentes no fue absolutamente solucionado hasta el año dos mil siete, cuando Yehuda Lindell y Benny Pinkas proponen un protocolo que es seguro ya antes este género de participantes.

Protocolo para el Inconveniente de los Millonarios

El inconveniente de los millonarios, en un inicio planteado por Yao al presentar el tema de Computación Bipartita Segura, consiste en lo siguiente: Alice y Bob son 2 millonarios, quienes tienen i y j millones respectivamente y desean saber quién tiene la mayor fortuna, sin descubrir cuánto dinero tiene cada uno de ellos. El protocolo propuesto para solventar este inconveniente particularmente es el siguiente:

Sean i y j los valores secretos de Alice y Bob respectivamente, con 1sistema cifrado simétrico) bajo la clave a, respectivamente.<>

Bob elige aleatoreamente un entero x de N bits, y calcula privadamente el valor k=Ea(x) .
Bob manda a Alice el valor k-j+1 .
Alice calcula privadamente los valores yu=Da(k-j+u) para u=1..10 .
Alice produce aleatoreamente un primo de N bits, y calcula los valores zu=yu(mod p) para cada u . Si todos y cada uno de los zu difieren por cuando menos dos (en el sentido de la aritmética modular), parar; de otra forma, reiterar hasta el momento en que los zu difieran todos en por lo menos dos. Sean p y zu los valores finales.
Alice manda el primo p y los próximos diez números a Bob: z1,z2,...,zi,zi+1+1,zi+2+1,...,z10+1 . La suma siempre y en toda circunstancia es módulo p .
Bob mira el j -ésimo número de la secuencia mandada por Alice, y decide que i=j si es igual a x(mod p) , y que i=j de otra manera.
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 urbes distantes, con lo que deben decidir quin se queda con el auto a través del teléfono. Para ello, Alice lanza una moneda al aire y Bob debe adivinar si salió cara o bien sello, mas Bob debe tener una certidumbre de que Alice no manipula el resultado a favor suyo. El protocolo planteado originalmente por Blum es como sigue:

Bob escoge aleatoreamente 2 primos p1 y p2 , coherentes con 3(mod cuatro) . Calcula n=p1p2 y se lo manda a Alice.
Alice verifica que n=1(mod cuatro) y que para algún x existe y tal que x2=y2(mod n) .
Alice escoge valores azarosos xi y manda a Bob sus cuadrados (mod n) así como n .
Bob verifica n , y manda a Alice n , x2(mod n) y bi .
Alice verifica n y x2(mod n) , y determina la secuencia aleatoria: 1 si Bob acertó sobre xi , y -1 en otro caso.
Alice manda a Bob los xi .
Bob verifica los cuadrados.

Protocolo para lanzar una moneda basado en Hash

Posteriormente se han creado distintas soluciones más eficaces y más seguras para este inconveniente, entre ellas resalta la utilización de funciones de Hash para esconder 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 escoge un entero x en secreto (lanzamiento de la moneda), y calcula H(x) y se lo manda a Bob.
Bob afirma a Alice si piensa que x es par o bien impar (apuesta de Bob).
Alice comunica a Bob si acertó o bien no, y lo persuade enviándole x (Bob puede calcular entonces H(x) , comprobando que sea igual al que recibió).

Solución a cualquier inconveniente de 2PC

En mil novecientos ochenta y seis, Andrew C. Yao plantea una solución para el inconveniente de 2PC para calcular cualquier función F. Para ello crea un circuito, representación gráfica de la función booleana, y uno de los participantes se hace cargo de hacerlo ininteligible, esto es, codifica cada una de las entradas a las compuertas del circuito con una máscara que solo conoce y que además de esto tiene su entrada pre-cargada. La manera de codificar estas entradas es cifrando los valores posibles bajo distintas claves solo conocidas por el partícipe que lo hace. El protocolo completo marcha de la próxima forma:

Alice edifica un circuito booleano ininteligible, el que contiene tablas para cada compuerta codificadas con una máscara y con su entrada pre-llenada. Entonces le manda el circuito a Bob.
Bob le solicita a Alice la codificación de los valores que debe ingresar a la entrada primordial a través de trasferencia inconsciente.
Bob ha recibido un circuito ininteligible y la correspondencia de su entrada con los valores codificados de la tabla. Corre el circuito y consigue el resultado de la función que representa el circuito.
Bob le manda el resultado a Alice.

Otras propuestas

La gran mayoría de los protocolos desarrollados a la data usan como base la propuesta de Yao de circuitos booleanos. El año dos mil cuatro un conjunto de estudiosos desarrollan Fairplay, una optimización del protocolo de Yao, mejorando su desempeño. En exactamente el mismo dos mil cuatro, Y. Lindell y B. Pinkas desarrollan una prueba de seguridad para el protocolo de Yao para contrincantes maliciosos, para por último el año dos mil siete incorporar un protocolo eficaz. Por último en dos mil siete, S. Jarecki y V. Shmatikov proponen una opción alternativa para solucionar 2PC, consistente en mandar los valores de entrada utilizando Compromiso de Bits.

?Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: ciento sesenta-164
?Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO mil novecientos ochenta y uno, pp. once-quince, mil novecientos ochenta y uno, reprinted in SIGACT News vol. quince, pp. veintitres-veintisiete, mil novecientos ochenta y tres.
?A. Yao. How to Generate and Exchange Secrets. In 27th FOCS, pages ciento sesenta y dos--ciento sesenta y siete, mil novecientos ochenta y seis. 21
?D. Malkhi, N. Nisan, B. Pinkas and Y. Sella. Fairplay - A Secure Two-Party Computation System. Proceedings of Usenix Security '2004, August nueve-trece, dos mil cuatro.
?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