Cálculo seguro entre dos partes

La computación segura de dos partes (2PC) es un subproblema de la computación segura de múltiples partes (MPC) que ha recibido especial atención por parte de los investigadores debido a su estrecha relación con muchas tareas criptográficas . El objetivo de 2PC es crear un protocolo genérico que permita a dos partes calcular conjuntamente una función arbitraria en sus entradas sin compartir el valor de sus entradas con la parte contraria. Uno de los ejemplos más conocidos de 2PC es el problema del millonario de Yao , en el que dos partes, Alice y Bob, son millonarios que desean determinar quién es más rico sin revelar su riqueza. Formalmente, Alice tiene riqueza , Bob tiene riqueza y ellos desean calcular sin revelar los valores o ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle a \ geq b}$ ${\ Displaystyle a}$ ${\ Displaystyle b}$ .

El protocolo de circuito distorsionado de Yao para el cálculo de dos partes ^[1] solo proporcionaba seguridad contra adversarios pasivos. Goldreich, Micali y Wigderson ^[2] introdujeron una de las primeras soluciones generales para lograr la seguridad contra un adversario activo mediante la aplicación de prueba de conocimiento cero ^[3] para imponer un comportamiento semi-honesto. Se sabía que este enfoque no era práctico durante años debido a los gastos generales de alta complejidad. Sin embargo, se han realizado mejoras significativas hacia la aplicación de este método en 2PC y Abascal, Faghihi Sereshgi, Hazay, Ishai y Venkitasubramaniam dieron el primer protocolo eficiente basado en este enfoque. ^[4]Lindell y Pinkas, ^[5] Ishai, Prabhakaran y Sahai ^[6] y Nielsen y Orlandi propusieron otro tipo de protocolos 2PC que son seguros contra adversarios activos . ^[7] Jarecki y Shmatikov propusieron otra solución para este problema, que funciona explícitamente con entradas comprometidas. ^[8]

Seguridad

La seguridad de un protocolo de cálculo de dos partes generalmente se define mediante una comparación con un escenario idealizado que es seguro por definición. El escenario idealizado involucra a una parte confiable que recopila la información de las dos partes a través de canales seguros y devuelve el resultado si ninguna de las partes elige abortar. El protocolo de cálculo criptográfico de dos partes es seguro, si no se comporta peor que este protocolo ideal, pero sin los supuestos de confianza adicionales . Esto generalmente se modela usando un simulador. La tarea del simulador es actuar como un envoltorio alrededor del protocolo idealizado para que parezca el protocolo criptográfico. La simulación tiene éxito con respecto a una teoría de la información , respectivamente.adversario limitado computacionalmente si la salida del simulador es estadísticamente cercana , respectivamente computacionalmente indistinguible, de la salida del protocolo criptográfico. Un protocolo de cálculo de dos partes es seguro, si para todos los adversarios existe un simulador exitoso.

Ver también

Una primitiva importante en 2PC es la transferencia inconsciente .
Capacidad de composición universal

Referencias

^ Yao, AC (1982). "Protocolos para cálculos seguros". 23º Simposio Anual sobre Fundamentos de las Ciencias de la Computación (sfcs 1982) . págs. 160-164. doi : 10.1109 / SFCS.1982.38 . S2CID 206558698 .
^ Goldreich, O .; Micali, S .; Wigderson, A. (1 de enero de 1987). "Cómo jugar CUALQUIER juego mental" . Actas del XIX Simposio Anual ACM sobre Teoría de la Computación . STOC '87. Nueva York, Nueva York, EE. UU.: Association for Computing Machinery: 218–229. doi : 10.1145 / 28395.28420 . ISBN 978-0-89791-221-1.
^ Goldwasser, S; Micali, S; Rackoff, C (1 de diciembre de 1985). "La complejidad del conocimiento de los sistemas de prueba interactivos" . Actas del Decimoséptimo Simposio Anual ACM sobre Teoría de la Computación . STOC '85. Providence, Rhode Island, EE. UU.: Asociación de Maquinaria de Computación: 291–304. doi : 10.1145 / 22145.22178 . ISBN 978-0-89791-151-1.
^ Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de octubre de 2020). "¿Es práctico el paradigma clásico de GMW? El caso de 2PC no interactivo activamente seguro" . Actas de la Conferencia 2020 ACM SIGSAC sobre seguridad informática y de comunicaciones . CCS '20. Evento virtual, Estados Unidos: Asociación de Maquinaria de Computación: 1591–1605. doi : 10.1145 / 3372297.3423366 . ISBN 978-1-4503-7089-9.
^ Lindell, Y .; Pinkas, B. (2007). Avances en Criptología - EUROCRYPT 2007 . Apuntes de conferencias en Ciencias de la Computación. 4515 . págs. 52–78. doi : 10.1007 / 978-3-540-72540-4_4 . ISBN 978-3-540-72539-8.
^ Ishai, Y .; Prabhakaran, M .; Sahai, A. (2008). Avances en criptología - CRYPTO 2008 . Apuntes de conferencias en Ciencias de la Computación. 5157 . págs. 572–591. doi : 10.1007 / 978-3-540-85174-5_32 . ISBN 978-3-540-85173-8.
^ Nielsen, JB; Orlandi, C. (2009). "LEGO para computación segura de dos partes". Teoría de la criptografía . Apuntes de conferencias en Ciencias de la Computación. 5444 . págs. 368–386. CiteSeerX 10.1.1.215.4422 . doi : 10.1007 / 978-3-642-00457-5_22 . ISBN 978-3-642-00456-8.
^ Jarecki, S .; Shmatikov, V. (2007). Avances en Criptología - EUROCRYPT 2007 . Apuntes de conferencias en Ciencias de la Computación. 4515 . págs. 97-114. doi : 10.1007 / 978-3-540-72540-4_6 . ISBN 978-3-540-72539-8.

Este artículo relacionado con la criptografía es un código auxiliar . Puedes ayudar a Wikipedia expandiéndolo .

[1] Yao, AC (1982). "Protocolos para cálculos seguros". 23º Simposio Anual sobre Fundamentos de las Ciencias de la Computación (sfcs 1982) . págs. 160-164. doi : 10.1109 / SFCS.1982.38 . S2CID 206558698 .

[2] Goldreich, O .; Micali, S .; Wigderson, A. (1 de enero de 1987). "Cómo jugar CUALQUIER juego mental" . Actas del XIX Simposio Anual ACM sobre Teoría de la Computación . STOC '87. Nueva York, Nueva York, EE. UU.: Association for Computing Machinery: 218–229. doi : 10.1145 / 28395.28420 . ISBN 978-0-89791-221-1.

[3] Goldwasser, S; Micali, S; Rackoff, C (1 de diciembre de 1985). "La complejidad del conocimiento de los sistemas de prueba interactivos" . Actas del Decimoséptimo Simposio Anual ACM sobre Teoría de la Computación . STOC '85. Providence, Rhode Island, EE. UU.: Asociación de Maquinaria de Computación: 291–304. doi : 10.1145 / 22145.22178 . ISBN 978-0-89791-151-1.

[4] Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de octubre de 2020). "¿Es práctico el paradigma clásico de GMW? El caso de 2PC no interactivo activamente seguro" . Actas de la Conferencia 2020 ACM SIGSAC sobre seguridad informática y de comunicaciones . CCS '20. Evento virtual, Estados Unidos: Asociación de Maquinaria de Computación: 1591–1605. doi : 10.1145 / 3372297.3423366 . ISBN 978-1-4503-7089-9.

[5] Lindell, Y .; Pinkas, B. (2007). Avances en Criptología - EUROCRYPT 2007 . Apuntes de conferencias en Ciencias de la Computación. 4515 . págs. 52–78. doi : 10.1007 / 978-3-540-72540-4_4 . ISBN 978-3-540-72539-8.

[6] Ishai, Y .; Prabhakaran, M .; Sahai, A. (2008). Avances en criptología - CRYPTO 2008 . Apuntes de conferencias en Ciencias de la Computación. 5157 . págs. 572–591. doi : 10.1007 / 978-3-540-85174-5_32 . ISBN 978-3-540-85173-8.

[7] Nielsen, JB; Orlandi, C. (2009). "LEGO para computación segura de dos partes". Teoría de la criptografía . Apuntes de conferencias en Ciencias de la Computación. 5444 . págs. 368–386. CiteSeerX 10.1.1.215.4422 . doi : 10.1007 / 978-3-642-00457-5_22 . ISBN 978-3-642-00456-8.

[8] Jarecki, S .; Shmatikov, V. (2007). Avances en Criptología - EUROCRYPT 2007 . Apuntes de conferencias en Ciencias de la Computación. 4515 . págs. 97-114. doi : 10.1007 / 978-3-540-72540-4_6 . ISBN 978-3-540-72539-8.

[1]