Protocolo GMW y oblivious transfer

El protocolo Goldreich-Micali-Wigderson (GMW) evalúa circuitos booleanos utilizando comparticiones de secretos XOR. El valor de cada cable se divide entre todas las partes, que interactúan puerta por puerta.

La parte i posee una compartición s_i tal que s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (el valor real del cable). Las puertas XOR son gratuitas: cada parte aplica XOR localmente a sus comparticiones.

Para una puerta AND sobre los cables a y b, el cálculo de (a_1⊕a_2)(b_1⊕b_2) se expande en términos cruzados. Evaluar el término cruzado a_i·b_j entre las partes i≠j requiere Oblivious Transfer.

En una OT 1-de-2, el emisor tiene los mensajes (m_0, m_1) y el receptor tiene el bit de elección c. El receptor obtiene m_c; el emisor no sabe nada sobre c y el receptor no sabe nada sobre m_{1-c}.

Se basa en Diffie-Hellman: el receptor genera dos claves públicas de modo que conoce el logaritmo discreto de una sola de ellas. El emisor cifra cada mensaje con una de las claves. El receptor solo descifra el texto cifrado que ha elegido.

Ishai et al. (2003): a partir de k OT base se generan m >> k OT utilizando únicamente operaciones de clave simétrica. La extensión IKNP reduce el coste de OT a aproximadamente 3 llamadas a AES por OT después de una configuración inicial única.

Cada puerta AND requiere una OT por cada par de partes. Con la extensión de OT, precalcular todas las OT durante una fase offline permite que la fase online consista en un único intercambio XOR por puerta.

GMW semihonesto puede convertirse en seguro frente a partes maliciosas mediante pruebas de conocimiento cero o Cut-and-Choose OT. El coste aumenta entre 3 y 8 veces, pero se garantiza la seguridad frente a partes que intenten hacer trampas.

MASCOT (Keller et al.) amplía OT para producir triples AND autenticadas en el modelo malicioso, lo que permite el protocolo SPDZ, que se trata en la siguiente lección.

EMP-toolkit y MOTION implementan GMW con extensión de OT. Alcanzan millones de puertas AND por segundo entre dos partes a través de una LAN, lo que hace viables las aplicaciones reales.

¿Por qué las puertas XOR del protocolo GMW no requieren comunicación entre las partes?

GMW utiliza comparticiones de secretos XOR sobre circuitos booleanos. Las puertas XOR son gratuitas; las puertas AND requieren OT. La extensión de OT hace que OT sea económica. La seguridad frente a partes maliciosas añade pruebas ZK o Cut-and-Choose. Bibliotecas como EMP ofrecen un rendimiento práctico para aplicaciones reales.