¿Qué es exactamente un “ circuito ilegible ”?

Un circuito es solo una forma de representar un cálculo. No hay nada específicamente criptográfico en un circuito. Solo significa un cálculo en línea recta (sin bucles o construcciones de control de flujo) que consiste solo en operaciones en bits , como Y, O, NO.

A circuito ilegible es una forma de «encriptar un cálculo» que revela solo el resultado del cálculo, pero no revela nada sobre las entradas o valores intermedios . Usamos el término «circuito» porque los circuitos confusos funcionan tomando el cálculo que le interesa, expresado como un circuito , y luego haciendo algunas cosas criptográficas para cada operación (Y, O, NO) en el circuito. .

Si queremos ser un poco más precisos, un «esquema confuso» consiste en:

• (Distorsionar) Una forma de convertir un (simple) circuito $ C $ en un distorsionado circuito $ \ widehat C $.

• (Codificar) Una forma de convertir cualquier entrada (simple) $ x $ para el circuito en una entrada confusa $ \ widehat x $. Necesita la aleatoriedad secreta que se utilizó para distorsionar el circuito para codificar $ x $ en $ \ widehat x $.

• (Evaluar) Una forma de tomar un distorsionado circuito $ \ widehat C $ y distorsionado ingresan $ \ widehat x $ y calculan la salida del circuito $ C (x) $. Cualquiera puede hacer esto, no tienes que saber $ x $ o la aleatoriedad secreta dentro de $ \ widehat C $ para evaluar y aprender $ C (x) $.

Estoy simplificando un poco aquí. Pero la idea principal de la seguridad es que $ \ widehat C $ y $ \ widehat x $ juntos no filtran más información que $ C (x) $. En particular, no revelan nada acerca de $ x $, pero permiten que se realice el cálculo $ C (x) $ (sin darse cuenta). Esto es lo que quiero decir con «cifrar un cálculo».

La principal aplicación para circuitos confusos es el cálculo seguro de dos partes. Imagine que Alice tiene una entrada privada $ x $ y Bob tiene una entrada privada $ y $. Están de acuerdo en alguna función $ f $ y están de acuerdo en que ambos quieren aprender $ f (x, y) $, pero no quieren que su oponente aprenda nada más que $ f (x, y ) $. Para lograr esto, pueden hacer lo siguiente (este es el protocolo clásico de Yao):

1. Las partes acuerdan una forma de expresar $ f $ como un (simple ) circuito. Alice confunde el circuito $ f \ mapsto \ widehat f $. Ella envía $ \ widehat f $ a Bob, así como su propia «entrada confusa» $ \ widehat x $.

2. Alice sabe cómo codificar cualquier entrada para $ f $ en una entrada «confusa», pero solo Bob conoce su entrada privada $ y $. Así que las partes hacen arreglos para que Bob elija una versión confusa $ \ widehat y $ sin que Alice sepa qué era $ y $. Esto se puede hacer con una primitiva llamada transferencia inconsciente.

3. Ahora Bob tiene el circuito confuso $ \ widehat f $, y una entrada confusa $ \ widehat x, \ widehat y $ para ese circuito. Luego puede ejecutar el procedimiento de evaluación y aprender $ f (x, y) $. Puede revelar $ f (x, y) $ a Alice.

Podemos argumentar que el protocolo no revela más de $ f (x, y) $ en lo siguiente manera:

• Alice no ve nada más que la respuesta final $ f (x, y) $ en este protocolo (la seguridad de la transferencia inconsciente garantiza que no aprenda nada en el paso 2).

• Aunque Bob ve $ \ widehat f $, $ \ widehat x $ y $ \ widehat y $, la seguridad de los circuitos confusos asegura que estos valores no » t revelar nada más allá de $ f (x, y) $.

Este enfoque funciona cuando Alice & Bob es semi-honesto (es decir, siguen el protocolo según las instrucciones). Pero cuando Alice es maliciosa, puede alterar alguna otra función $ f «$ en lugar de $ f $ que acordaron.Por lo tanto, se deben agregar otras cosas al protocolo para evitar que esto suceda, cuando queremos seguridad contra adversarios maliciosos.

Material de referencia:

• La construcción de Yao y su prueba de seguridad (video), Yehuda Lindell
• Una prueba del protocolo de Yao para la computación segura entre dos partes , Yehuda Lindell & Benny Pinkas
• Fundamentos de circuitos distorsionados , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• Una breve historia de optimizaciones prácticas de circuitos ilegibles , un video mío . Las primeras diapositivas cubren la construcción «clásica» de circuitos confusos.

Comentarios

• ¿Cómo Bob confunde y ¿sin conocer la aleatoriedad secreta que eligió Alice cuando se le ocurrió el esquema confuso?
• La codificación confusa funciona poco a poco. Tome Bob s primer bit. Alice puede pensar para sí misma: " si Bob tiene el bit de entrada 0, entonces su codificación confusa debería ser $ G_0 $. Si ingresó el bit 1, entonces su codificación confusa debería ser $ G_1 $. " Transferencia ajena es una primitiva donde Alice proporciona dos cadenas $ G_0, G_1 $ como entrada. Bob proporciona un bit $ b $ como entrada y aprende $ G_b $ (pero no el otro $ G_ {1-b} $). Alice no ' t aprende $ b $. Las partes pueden realizar una transferencia ajena a cada bit de entrada de Bob '. En cuanto a cómo funciona realmente la transferencia inconsciente, esa es otra cuestión;)
• Además del circuito confuso de Yao ', puede ' no se puede reutilizar. ¿Puede resolver mi confusión de que " permite asignar diferentes claves cada vez que se ejecuta un circuito distorsionado o las claves se fijan para los bits de entrada 0 y 1 "