El circuito ilegible es un protocolo criptográfico que permite el cálculo seguro de dos partes en el que dos partes que desconfían pueden evaluar conjuntamente una función sobre sus entradas privadas sin la presencia de un tercero de confianza. En el protocolo de circuito distorsionado, la función debe describirse como un circuito booleano .
La historia de los circuitos confusos es complicada. La invención del circuito confuso se atribuyó a Andrew Yao , ya que Yao introdujo la idea en la presentación oral de un artículo [1] en FOCS'86. Esto fue documentado por Oded Goldreich en 2003. [2] El primer documento escrito sobre esta técnica fue de Goldreich, Micali y Wigderson en STOC'87. [3] El término "circuito confuso" fue utilizado por primera vez por Beaver, Micali y Rogaway en STOC'90. [4] El protocolo de Yao para resolver el problema de los millonarios de Yao fue el ejemplo inicial de computación segura, pero no está directamente relacionado con circuitos confusos.
Fondo
Transferencia ajena
En el protocolo de circuito distorsionado, hacemos uso de la transferencia inconsciente . En la transferencia inconsciente, una cadena se transfiere entre un remitente y un receptor de la siguiente manera: un remitente tiene dos cadenas y . El receptor elige y el remitente envía con el protocolo de transferencia inconsciente tal que
- el receptor no obtiene ninguna información sobre ,
- El valor de no está expuesto al remitente.
Tenga en cuenta que si bien el receptor no conoce el valores, en la práctica, el receptor conoce alguna información sobre lo que codifica para que el receptor no elija ciegamente . Es decir, si codifica un valor falso, codifica un valor verdadero y el receptor desea obtener el valor verdadero codificado, el receptor elige .
La transferencia inconsciente se puede construir utilizando criptografía asimétrica como el criptosistema RSA .
Definiciones y notaciones
Operador es la concatenación de cadenas . Operadores XOR bit a bit . k es un parámetro de seguridad y la longitud de las claves. Debe ser mayor que 80 y generalmente se establece en 128.
Protocolo de circuito ilegible
El protocolo consta de los 6 pasos siguientes:
- La función subyacente (por ejemplo, en el problema de los millonarios, función de comparación) se describe como un circuito booleano con puertas de 2 entradas. El circuito es conocido por ambas partes. Este paso lo puede realizar un tercero de antemano.
- Alice confunde (cifra) el circuito. Llamamos a Alice la balbucea .
- Alice envía el circuito confuso a Bob junto con su entrada encriptada.
- Para calcular el circuito, Bob también necesita distorsionar su propia entrada. Con este fin, necesita que Alice lo ayude, porque solo el confuso sabe cómo cifrar. Finalmente, Bob puede cifrar su entrada mediante una transferencia ajena. En términos de la definición de arriba, Bob es el receptor y Alice el remitente en esta transferencia inconsciente.
- Bob evalúa (descifra) el circuito y obtiene las salidas cifradas. Llamamos a Bob el evaluador .
- Alice y Bob se comunican para conocer el resultado.
Generación de circuitos
El circuito booleano para funciones pequeñas se puede generar a mano. Es convencional hacer el circuito con puertas XOR y AND de 2 entradas . Es importante que el circuito generado tenga el número mínimo de puertas AND (consulte Optimización de XOR libre ). Existen métodos que generan el circuito optimizado en términos de número de puertas AND utilizando la técnica de síntesis lógica . [5] El circuito para el problema de los millonarios es un circuito comparador digital (que es una cadena de sumadores completos que funcionan como un restador y emiten la bandera de acarreo ). Se puede implementar un circuito sumador completo usando solo una puerta AND y algunas puertas XOR . Esto significa que el número total de puertas Y para el circuito del Problema de los millonarios es igual al ancho de bits de las entradas.
Garbling
Alice (confusa) cifra el circuito booleano en este paso para obtener un circuito confuso . Alice asigna dos cadenas generadas aleatoriamente llamadas etiquetas a cada cable en el circuito: una para la semántica booleana 0 y otra para 1. (La etiqueta tiene una longitud de k bits, donde k es el parámetro de seguridad y generalmente se establece en 128). a todas las puertas del circuito y reemplaza 0 y 1 en las tablas de verdad con las etiquetas correspondientes. La siguiente tabla muestra la tabla de verdad para una puerta AND con dos entradas y salida :
a | B | C |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Alice reemplazó 0 y 1 con las etiquetas correspondientes:
a | B | C |
---|---|---|
Luego, encripta la entrada de salida de la tabla de verdad con las dos etiquetas de entrada correspondientes. La tabla cifrada se llama tabla ilegible. Esto se hace de manera que uno pueda descifrar la tabla distorsionada solo si tiene las dos etiquetas de entrada correctas. En la siguiente tabla,es un cifrado simétrico de doble clave en el que k es la clave secreta y X es el valor que se va a cifrar (consulte Cifrado de bloques de clave fija ).
Mesa ilegible |
---|
Después de esto, Alice permuta aleatoriamente la tabla de modo que el valor de salida no se pueda determinar a partir de la fila. El nombre del protocolo, confuso , se deriva de esta permutación aleatoria.
Transferencia de datos
Alice envía las tablas confusas calculadas para todas las puertas del circuito a Bob. Bob necesita etiquetas de entrada para abrir las tablas distorsionadas. Por lo tanto, Alice elige las etiquetas correspondientes a su entraday se los envía a Bob. Por ejemplo, si la entrada de Alice es, luego ella envía , , , , y a Bob. Bob no aprenderá nada sobre la entrada de Alice,, ya que las etiquetas son generadas aleatoriamente por Alice y le parecen cadenas aleatorias a Bob.
Bob también necesita las etiquetas correspondientes a su entrada. Recibe sus etiquetas a través de transferencias ajenas a cada parte de su entrada. Por ejemplo, si la entrada de Bob es, Bob primero pide entre las etiquetas de Alice y . A través de una transferencia inconsciente de 1 de 2 , recibey así. Después de las transferencias inconscientes , Alice no aprenderá nada sobre la entrada de Bob y Bob no aprenderá nada sobre las otras etiquetas.
Evaluación
Después de la transferencia de datos, Bob tiene las tablas distorsionadas y las etiquetas de entrada. Atraviesa todas las puertas una por una e intenta descifrar las filas en sus tablas distorsionadas. Puede abrir una fila para cada tabla y recuperar la etiqueta de salida correspondiente:, dónde . Continúa la evaluación hasta que llega a las etiquetas de salida.
Salida reveladora
Después de la evaluación, Bob obtiene la etiqueta de salida, , y Alice conoce su asignación al valor booleano ya que tiene ambas etiquetas: y . O Alice puede compartir su información con Bob o Bob puede revelar la salida a Alice de modo que uno o ambos aprendan la salida.
Mejoramiento
Point-and-permute
En esta optimización, Alice genera un bit aleatorio, , llamado bit de selección para cada cable . Luego establece el primer bit de la etiqueta 0, a y el primer bit de la etiqueta 1, , a ( NO de). Luego, en lugar de permutar aleatoriamente, ordena la tabla distorsionada de acuerdo con el bit de selección de entradas. De esta manera, Bob no necesita probar las cuatro filas de la tabla para encontrar la correcta, ya que tiene las etiquetas de entrada y puede encontrar la fila correcta y descifrarla con un solo intento. Esto reduce 4 veces la carga de evaluación. Tampoco revela nada sobre el valor de salida porque los bits de selección se generan aleatoriamente. [6]
Reducción de filas
Esta optimización reduce el tamaño de las tablas distorsionadas de 4 filas a 3 filas. Aquí, en lugar de generar una etiqueta para el cable de salida de una puerta al azar, Alice la genera usando una función de las etiquetas de entrada. Ella genera las etiquetas de salida de manera que la primera entrada de la tabla distorsionada se convierte en 0 y ya no es necesario enviarla: [7]
XOR gratis
En esta optimización, Alice genera un valor de bits aleatorio global (k-1) que se mantiene en secreto. Durante el distorsionado de las puertas de entrada y , ella solo genera las etiquetas y calcula las otras etiquetas como y . Usando estos valores, la etiqueta del cable de salida de una puerta XOR con cables de entrada , se establece en . La prueba de seguridad en Random Oracle Model para esta optimización se da en el artículo Free-XOR. [8]
Implicación
La optimización de XOR libre implica un punto importante de que la cantidad de transferencia de datos (comunicación) y el número de cifrado y descifrado (cálculo) del protocolo de circuito distorsionado se basa solo en el número de puertas AND en el circuito booleano, no en las puertas XOR . Por lo tanto, entre dos circuitos booleanos que representan la misma función, se prefiere el que tiene el menor número de puertas AND.
Cifrado de bloques de clave fija
Este método permite distorsionar y evaluar de manera eficiente las puertas AND utilizando AES de clave fija , en lugar de la costosa función de hash criptográfica como SHA-2 . En este esquema ilegible que es compatible con las técnicas Free XOR y Row Reduction , la clave de salida está encriptado con el token de entrada y usando la función de encriptación , dónde , es un cifrado de bloque de clave fija (por ejemplo, instanciado con AES ), yes un número único por puerta (por ejemplo, identificador de puerta) llamado tweak . [9]
Mitad y
Esta optimización reduce el tamaño de la mesa distorsionada para puertas AND de 3 filas en Reducción de filas a 2 filas. Se muestra que este es el mínimo teórico para el número de filas en la tabla distorsionada, para una determinada clase de técnicas distorsionadas. [10]
Seguridad
El circuito ilegible de Yao es seguro contra un adversario semi-honesto. Este tipo de adversario sigue el protocolo y no realiza ningún comportamiento malicioso, pero intenta violar la privacidad de la entrada de la otra parte al analizar los mensajes transmitidos en el protocolo.
Es más difícil hacer que este protocolo sea seguro contra un adversario malintencionado que se desvíe del protocolo. Una de las primeras soluciones para hacer que el protocolo sea seguro contra adversarios malintencionados es utilizar la prueba de conocimiento cero para evitar actividades malintencionadas durante el protocolo. [11] Durante años, este enfoque se consideró más una solución teórica que una solución práctica debido a la complejidad de los gastos generales. Pero, se muestra que es posible usarlo con solo una pequeña sobrecarga. [12] Otro enfoque es usar varios GC para un circuito y verificar la exactitud de un subconjunto de ellos y luego usar el resto para el cálculo con la esperanza de que si el mutilador era malicioso, se detectaría durante la fase de verificación. [13] Otra solución es autenticar el esquema de distorsión de modo que el evaluador pueda verificar el circuito distorsionado. [14] [15]
Ver también
- Criptografía
- RSA
- Computación multipartita segura
- El problema de los millonarios de Yao
Referencias
- ^ Yao, Andrew Chi-Chih (1986). "Cómo generar e intercambiar secretos". 27º Simposio Anual sobre Fundamentos de las Ciencias de la Computación (SFCS 1986) . Fundamentos de las Ciencias de la Computación, 1986., 27º Simposio Anual de . págs. 162-167. doi : 10.1109 / SFCS.1986.25 . ISBN 978-0-8186-0740-0.
- ^ Goldreich, Oded (2003). "Criptografía y protocolos criptográficos" . Computación distribuida: artículos en celebración del vigésimo aniversario de PODC . 16 (2-3): 177-199. CiteSeerX 10.1.1.117.3618 . doi : 10.1007 / s00446-002-0077-1 . S2CID 9966766 .
- ^ Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1987). Cómo jugar CUALQUIER juego mental . Proceeding STOC '87 Proceedings of the 19th Annual ACM Symposium on Theory of Computing . págs. 218-229. doi : 10.1145 / 28395.28420 . ISBN 978-0897912211. S2CID 6669082 .
- ^ Beaver, Donald; Micali, Silvio; Rogaway, Phillip (1990). La complejidad redonda de los protocolos seguros . Procedimientos Procedimientos STOC '90 del Vigésimo Segundo Simposio Anual ACM sobre Teoría de la Computación . págs. 503–513. CiteSeerX 10.1.1.697.1624 . doi : 10.1145 / 100216.100287 . ISBN 978-0897913614. S2CID 1578121 .
- ^ Songhori, Ebrahim M; Hussain, Siam U; Sadeghi, Ahmad-Reza; Schneider, Thomas; Koushanfar, Farinaz (2015). TinyGarble: Circuitos ilegibles secuenciales altamente comprimidos y escalables . Seguridad y privacidad (SP), Simposio IEEE 2015 en . págs. 411–428. doi : 10.1109 / SP.2015.32 . ISBN 978-1-4673-6949-7. S2CID 5346323 .
- ^ Beaver, Donald; Micali, Silvio; Rogaway, Phillip (1990). La complejidad redonda de los protocolos seguros . Actas del Vigésimo Segundo Simposio Anual ACM sobre Teoría de la Computación . págs. 503–513. CiteSeerX 10.1.1.697.1624 . doi : 10.1145 / 100216.100287 . ISBN 978-0897913614. S2CID 1578121 .
- ^ Naor, Moni; Pinkas, Benny; Sumner, Reuban (1999). Subastas que preservan la privacidad y diseño de mecanismos . Actas de la 1ª Conferencia ACM sobre Comercio Electrónico . págs. 129-139. CiteSeerX 10.1.1.17.7459 . doi : 10.1145 / 336992.337028 . ISBN 978-1581131765. S2CID 207593367 .
- ^ Kolesnikov, Vladimir; Schneider, Thomas (2008). Circuito confuso mejorado: puertas y aplicaciones XOR gratuitas . Coloquio internacional sobre autómatas, lenguajes y programación . Apuntes de conferencias en informática. 5126 . págs. 486–498. CiteSeerX 10.1.1.160.5268 . doi : 10.1007 / 978-3-540-70583-3_40 . ISBN 978-3-540-70582-6.
- ^ Bellare, Mihir; Hoang, Viet Tung; Keelveedhi, Sriram; Rogaway, Phillip (2013). Mezcla eficiente de un blockcipher de clave fija . Seguridad y privacidad (SP), 2013 IEEE Symposium on . págs. 478–492. CiteSeerX 10.1.1.299.2755 . doi : 10.1109 / SP.2013.39 . ISBN 978-0-7695-4977-4. S2CID 1351222 .
- ^ Zahur, Samee; Rosulek, Mike; Evans, David (2015). Dos mitades forman un todo (PDF) .
- ^ 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. S2CID 8689051 .
- ^ 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. S2CID 226228208 .
- ^ Lindell, Yehuda; Pinkas, Benny (2007). Naor, Moni (ed.). "Un protocolo eficiente para la computación segura de dos partes en presencia de adversarios maliciosos" . Avances en Criptología - EUROCRYPT 2007 . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 4515 : 52–78. Código Bib : 2007LNCS.4515 ... 52L . doi : 10.1007 / 978-3-540-72540-4_4 . ISBN 978-3-540-72540-4.
- ^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Prabhakaran, Manoj; Sahai, Amit (2011). Paterson, Kenneth G. (ed.). "Computación segura no interactiva eficiente" . Avances en Criptología - EUROCRYPT 2011 . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 6632 : 406–425. doi : 10.1007 / 978-3-642-20465-4_23 . ISBN 978-3-642-20465-4.
- ^ Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2017). Kalai, Yael; Reyzin, Leonid (eds.). "Circuitos distorsionados activamente seguros con sobrecarga de comunicación constante en el modelo sencillo" . Teoría de la criptografía . Apuntes de conferencias en informática. Cham: Springer International Publishing. 10678 : 3–39. doi : 10.1007 / 978-3-319-70503-3_1 . ISBN 978-3-319-70503-3.
Otras lecturas
- "Circuito ilegible de Yao" (PDF) . CS598 . illinois.edu . Consultado el 18 de octubre de 2016 .