Problema de MPC y circuitos ofuscados de Yao

MPC permite que n partes, cada una con una entrada privada x_i, calculen conjuntamente f(x_1,...,x_n) sin revelar sus entradas entre sí, como si una tercera parte de confianza realizara el cálculo.

El problema de los millonarios de Yao (1982): Alice y Bob quieren saber quién es más rico sin revelar su patrimonio. No existe una tercera parte de confianza. MPC resuelve este problema con garantías criptográficas.

1. Privacidad: las partes solo conocen la salida y lo que pueden inferir de ella. 2. Corrección: la salida es correcta incluso si algunas partes están comprometidas. 3. Existen variantes para adversarios semihonestos y maliciosos.

Cualquier función puede expresarse como un circuito booleano (puertas AND, XOR y NOT). Los protocolos MPC suelen operar en el nivel del circuito y evalúan cada puerta de forma segura.

Alice (garbler) asigna dos etiquetas aleatorias a cada cable: una para 0 y otra para 1. Cifra la tabla de verdad de cada puerta utilizando las etiquetas de los cables de entrada. Bob (evaluator) obtiene las etiquetas correspondientes a sus entradas mediante Oblivious Transfer.

Bob recibe tablas garbled (4 cifrados por cada puerta AND). Descifra exactamente una fila utilizando sus etiquetas de entrada y obtiene la etiqueta de salida, sin saber si representa 0 o 1.

Asocie un bit de selección aleatorio a cada etiqueta. Bob utiliza los bits de selección para encontrar la fila garbled correcta en O(1), en lugar de intentar los cuatro descifrados. Esto reduce el cálculo 4 veces.

Kolesnikov y Schneider (2008): elija un desplazamiento global Δ. Entonces label_1 = label_0 ⊕ Δ para cada cable. Las puertas XOR pasan a ser gratuitas (no requieren cifrado), lo que ahorra aproximadamente un 30 % de ancho de banda.

Zahur et al. (2015): cada puerta AND solo requiere 2 textos cifrados (en lugar de 4). Combinado con Free-XOR, esto reduce a la mitad el ancho de banda de los circuitos garbled estándar.

Los circuitos garbled clásicos son para dos partes. Las extensiones multipartitas (por ejemplo, el protocolo BMR) paralelizan el garbling entre todas las partes, pero requieren una comunicación O(n²). Son prácticas para valores pequeños de n.

En el protocolo de circuitos garbled de Yao, ¿cómo obtiene Bob las etiquetas de los cables correspondientes a sus bits de entrada privados?

MPC permite que las partes calculen conjuntamente sin revelar sus entradas. Los circuitos garbled codifican funciones booleanas como tablas de verdad cifradas. Las optimizaciones (Free-XOR, Half-Gates y Point-and-Permute) los hacen prácticos. OT proporciona las etiquetas de entrada de Bob de forma privada.