circuito distorsionado
El circuito distorsionado 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 distorsionados es complicada. La invención del circuito distorsionado 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 distorsionado" fue utilizado por primera vez por Beaver, Micali y Rogaway en STOC'90. [4] El protocolo de Yao que resuelve el problema de los millonarios de Yao fue el ejemplo inicial de computación segura, pero no está directamente relacionado con circuitos distorsionados.
En el protocolo de circuito distorsionado, hacemos uso de la transferencia inconsciente . En la transferencia olvidada, se transfiere una cadena entre un emisor y un receptor de la siguiente manera: un emisor tiene dos cadenas y . El receptor elige y el remitente envía con el protocolo de transferencia ajeno tal que
Tenga en cuenta que si bien el receptor no conoce los valores, en la práctica el receptor conoce cierta información sobre lo que codifica para que el receptor no elija a ciegas . Es decir, si codifica un valor falso, codifica un valor verdadero y el receptor quiere obtener el valor verdadero codificado, el receptor elige .
El operador es concatenación de cadenas . El operador es XOR bit a bit . k es un parámetro de seguridad y la longitud de las claves. Debe ser superior a 80 y normalmente se establece en 128.
El circuito booleano para funciones pequeñas se puede generar a mano. Es convencional hacer el circuito con compuertas XOR y AND de 2 entradas . Es importante que el circuito generado tenga el mínimo número de compuertas AND (ver Optimización 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 generan 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 compuertas AND para el circuito del Problema de los millonarios es igual al ancho de bits de las entradas.
