Protocolo de computación confidencial

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de noviembre de 2017; las comprobaciones requieren 7 ediciones .

En criptografía , un protocolo de cómputo confidencial (también cómputo seguro, seguro o secreto de múltiples partes, ing. cómputo seguro de múltiples partes ) es un protocolo criptográfico que permite a varios participantes realizar un cálculo que depende de los datos de entrada secretos de cada uno de ellos. , de tal manera que ningún participante pudo obtener información sobre la entrada secreta de otra persona. Por primera vez, Andrew Yao planteó el problema de la computación confidencial en 1982 en el artículo [1] . Dos millonarios, Alice y Bob, quieren saber cuál de ellos es más rico, pero no quieren revelar la cantidad exacta de su riqueza. Yao proponía en su artículo una forma original de solucionar este problema, que luego se conoció como el problema de los millonarios . Mucho más tarde, en 2004, Yehuda Lindell y Benny Pinkas proporcionaron una prueba matemáticamente rigurosa de la exactitud del protocolo de Yao en [2] . El problema de la computación confidencial está estrechamente relacionado con el problema de compartir secretos .

Enunciado del problema formalizado

N participantes p 1 , p 2 , …, p N participan en cálculo confidencial . Cada participante tiene datos de entrada secretos d 1 , d 2 , …, d N respectivamente. Los participantes quieren encontrar el valor F(d 1 , d 2 , …, d N ) , donde F es una función computable de N argumentos conocidos por todos los participantes . Se supone que entre los participantes habrá infractores semi-honestos , es decir, aquellos que siguen fielmente el protocolo, pero intentan obtener información adicional de cualquier dato intermedio.

Requisitos de seguridad

Los requisitos de seguridad para los protocolos informáticos confidenciales suelen tener diferentes requisitos de seguridad según la situación. Estos son los principales requisitos.

Confidencialidad. Ninguno de los participantes debe poder recibir más información de la prescrita.
Exactitud. Cada participante debe tener la garantía de recibir los datos correctos.
Información garantizada. Los participantes no deben poder evitar que otros participantes obtengan el resultado.

Un ejemplo de solución al problema de los millonarios

Que los millonarios Alice y Bob quieran saber de quién es la mayor fortuna sin revelar la cantidad exacta de sus fortunas. Para mayor precisión, supongamos que Alicia tiene i millón y Bob tiene j , donde 1<i y j<10 . En primer lugar, Alice y Bob necesitarán un criptosistema de clave pública sólido , como RSA [3] . Sea E a una función de cifrado arbitraria para la clave a , y D a la función de descifrado de clave privada para la clave pública a . Sea a la clave pública de Alice. Entonces el protocolo queda así:

Bob elige un entero aleatorio x de N bits y calcula confidencialmente k=E a (x) ;
Bob envía un número k-j+1 a Alice ;
Alicia considera confidencialmente los valores y u =D a (k-j+u) para u=1,2,…,10 ;
Alice elige un número primo aleatorio p de N/2 bits para que los números z u =y u mod(p) difieran en al menos 2 módulos p para todo u y envía el número p a Bob;
Alice envía los números z 1 , z 2 , …, z i seguidos de los números z i+1 +1, …, z 10 +1 ; los números se toman módulo p;
Bob, que sabe cuánto dinero tiene ( j ), compara el número j con el número x mod p elegido en el primer paso, y si son iguales, entonces Bob concluye que i ⩾ j , y i < j en caso contrario;
Bob informa el resultado a Alice.

Se puede ver que el protocolo le permite determinar sin ambigüedades cuyo estado es mayor y, al mismo tiempo, los participantes no pueden conocer los estados de los demás.

Implementaciones

Hay dos enfoques diferentes para implementar el protocolo. El primer enfoque generalmente se basa en compartir secretos y trabaja en la representación de la función calculada en forma de un circuito aritmético ( ing. aritmético circuito ), como, por ejemplo, en el BGW (Ben-Or, Goldwasser y Wigderson) [ 4] y CCD (Chaum, Crepeau y Damgard [5] . Este enfoque generalmente se aplica cuando se sabe que la mayoría de los participantes son honestos (lo que solo es posible si el número de participantes es más de dos). Otro enfoque es representar la función como un diagrama lógico . Este enfoque fue utilizado por Andrew Yao al construir un circuito distorsionado ( English garbled circuit ) [6] , así como en el protocolo GMW (Goldreich, Micali y Wigderson) [7] .

El método del esquema aritmético es más adecuado para realizar operaciones de suma y multiplicación (donde los participantes comparten el secreto y el secreto solo se puede recrear si se recibe información de cada uno de los participantes), pero no es adecuado para realizar operaciones de comparación. Este enfoque ha logrado un gran éxito en el proyecto SIMAP [8] .

El método del circuito lógico realiza sumas y multiplicaciones con menos eficiencia, pero puede realizar fácilmente operaciones binarias como comparaciones. Este segundo enfoque, en el que se basa el sistema de dos manos de Andrew Yao , fue implementado por Mulchy en el sistema de juego limpio [9 ] . Este sistema también brinda la capacidad de implementar la funcionalidad necesaria, representada por un lenguaje de programación de alto nivel en forma de bucle lógico, que luego es interpretado por el entorno de tiempo de ejecución y ejecutado de manera segura. También existe un sistema "FairplayMP" [10] , que es una extensión de "Fairplay" en el caso de más de dos participantes. Una ventaja significativa de los sistemas basados en métodos con circuitos lógicos es que se realizan en un número constante de intercambios de información, mientras que la ventaja de los sistemas basados en circuitos aritméticos es la capacidad de realizar operaciones aritméticas (suma y multiplicación) muy rápidamente.

Ejemplo de protocolo

Para simplificar, supongamos que dos participantes participan en el cálculo, es decir, N=2 , y los participantes necesitan calcular la función F.

Representemos la función F en forma de circuito lógico , es decir, representaremos los datos de entrada de la función F en forma binaria, y la función en sí se implementa mediante las operaciones AND, OR y NOT. Luego, los bits de todos los argumentos de la función F se alimentan a la entrada del circuito lógico , y el circuito en sí consta de puertas lógicas AND, OR y NOT, y en la salida produce el resultado de la función F en formato binario.
El participante p 1 genera para cada cable del circuito lógico dos números aleatorios diferentes k 0 u k 1 . Los números representan el cero y el uno encriptados en ese cable, respectivamente.
El participante p 1 crea una tabla de cálculo encriptada para cada esquema. Para una puerta OR binaria, dicha tabla se vería así:

Cable de entrada w 1	Cable de entrada w 2	Cable de salida w 3	Tabla de cálculo cifrada
${\displaystyle k_{1}^{0))$	${\displaystyle k_{2}^{0))$	${\displaystyle k_{3}^{0))$	$c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))$
${\displaystyle k_{1}^{0))$	${\displaystyle k_{2}^{1))$	${\displaystyle k_{3}^{1))$	$c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))$
${\displaystyle k_{1}^{1))$	${\displaystyle k_{2}^{0))$	${\displaystyle k_{3}^{1))$	$c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))$
${\displaystyle k_{1}^{1))$	${\displaystyle k_{2}^{1))$	${\displaystyle k_{3}^{1))$	$c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))$

Aquí significa el resultado del cifrado del valor x con la clave k , y - respectivamente, el descifrado del texto cifrado y con la clave k . Debe elegir un esquema de cifrado simétrico , que tiene una propiedad adicional: si intenta descifrar el texto con la clave incorrecta, el algoritmo devuelve un error. $E_{k}(x)$ ${\ Displaystyle D_ {k} (y)}$

El significado de esta tabla es el siguiente: si conocemos los valores encriptados de la señal k 1 u k 2 en los cables de entrada de la válvula w 1 u w 2 , respectivamente, entonces podemos calcular el valor de la señal encriptada calculando el valor para todo i =1...4 . En tres casos de cuatro, debería ocurrir un error, y en el cuarto restante obtendremos el valor encriptado k 3 de la señal en la salida de la puerta. $d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))$

El participante p 1 envía el circuito lógico y las tablas de cálculo encriptadas para todos los circuitos al participante p 2 .
El participante p 1 envía al participante p 2 los valores encriptados de las señales de entrada para aquellas entradas que corresponden a los datos de entrada del participante p 1 .
Para cada cable de entrada w i correspondiente a los datos de entrada p 2 , el participante p 1 envía un número al participante p 2 utilizando el protocolo de transferencia olvidada , donde bi es el valor del bit secreto de datos de entrada del participante p 2 . Con tal transferencia, el participante p 1 no conoce el valor de b i . Dado que para cada cable se seleccionaron previamente aleatoriamente sus propios números aleatorios, que son cero y uno, entonces el participante p 2 no podrá averiguar qué número es cero y cuál es uno para los cables de entrada del participante p 1 , y por lo tanto no podrá averiguar los datos del participante de entrada p 1 . $k_{i}^{b_{i))$
Ahora el miembro p 2 tiene un circuito lógico encriptado y valores encriptados de todos los cables de entrada. Calcula en forma encriptada (como se describió anteriormente) todas las puertas del circuito una tras otra y luego pasa el resultado encriptado al participante p 1 .
El participante p 1 descifra el resultado y lo informa al participante p 2 .

Protocolos utilizados

La transmisión olvidada puede ser un componente importante del protocolo informático confidencial .
Protocolo de participante virtual: un protocolo que oculta la identidad de los participantes [11] .
Los protocolos de suma segura permiten a los participantes que colaboran calcular algunas características a partir de su información individual sin revelar esta información entre sí [12] .

Aplicación práctica

Voto electrónico . Por ejemplo, cada participante puede votar a favor o en contra, entonces el resultado de la votación de n participantes será la función F(x 1 ,…,x n ) , donde x i puede tomar los valores 0 (en contra) y 1 (por).
Subastas electrónicas. Cada participante puja x i , y la función F(x 1 , …,x n ) devuelve el número del máximo x i .
Estadísticas. Digamos que los estudiantes quieren saber su mejor calificación o promedio sin mostrarse las calificaciones entre ellos.
bases de datos Por ejemplo, supongamos que el usuario desea consultar una base de datos y obtener una respuesta sin exponer la consulta. El propietario del servidor con la base de datos no desea que la información que no sea la respuesta a la solicitud llegue al usuario cuando realiza las solicitudes. En este caso, tanto el usuario como el servidor serán partícipes del protocolo informático confidencial.
Autoridad de certificación distribuida . Suponga que necesita crear una autoridad de certificación que emitirá certificados a los usuarios, firmándolos con alguna clave secreta. Para proteger la clave, la clave se puede dividir entre varios servidores para que cada servidor conserve su propia parte de la clave. Entonces surge el problema: cómo realizar una operación criptográfica (en este ejemplo, emitir una firma) sin transferir todas las partes de la clave a una computadora. Este problema se resuelve utilizando un protocolo de cálculo privado, donde la entrada a la función de cálculo privado son las partes clave y el mensaje firmado, y la salida es el mensaje firmado.

Notas

^ Andrew Chi-Chih Yao: Protocolos para cálculos seguros (resumen extendido) FOCS 1982: 160-164
↑ Yehuda Lindell, Benny Pinkas: Una prueba del protocolo de Yao para la computación bipartita segura, Cryptology ePrint Archive, Informe 2004/175
↑ Solución al problema del millonario Archivado el 19 de mayo de 2008.
↑ M. Ben-Or, S. Goldwasser y A. Wigderson. Teoremas de completitud para computación distribuida tolerante a fallas no criptográfica. En STOC 20, 1-10, 1988.
↑ P. Bogetoft, D. L. Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach y T. Toft. El cómputo multipartito seguro cobra vida. En Criptografía Financiera y Seguridad de Datos – FC 2009
↑ A. Yao. Cómo generar e intercambiar secretos. En 27th FOCS, 162-167, 1986.
↑ Goldreich, S. Micali y A. Widderson. Cómo jugar cualquier juego mental: un teorema de integridad para protocolos con mayoría honesta. En 19 STOC, 218-229, 1987.
↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. y T.Toft. Una implementación práctica de subastas computacionales seguras basadas en enteros multiparte. En Criptografía financiera y seguridad de datos - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
↑ D. Malkhi, N. Nisan, B. Pinkas y Y. Sella. Fairplay es un sistema de computación bipartito seguro. En Proc. del 13º Simposio de Seguridad de USENIX, 2004.
↑ A. Ben-David, N. Nisan y B. Pinkas. FairplayMP: un sistema para el cómputo multipartidista seguro. En Seguridad Informática y de las Comunicaciones - CCS 2008, ACM, 257-266, 2008.
↑ Pathak Rohit, Joshi Satyadhar, Avances en seguridad y garantía de la información, Springer Berlin/Heidelberg, ISSN 0302-9743 (Impreso) 1611-3349 (En línea), ISBN 978-3-642-02616-4 , DOI 10.1007/978-3 -642-02617-1
↑ Rashid Sheikh, Brijesh Kumar y Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (en línea), Vol.6, No.2, nov. 2009