Plausible Deniability in Fully Homomorphic Computation

Resumen Técnico: Denegabilidad Plausible en Computación Completamente Homomórfica (PD-FHC)

1. Planteamiento del Problema

La externalización de la computación a proveedores de la nube no confiables expone a los usuarios a dos amenazas distintas que las tecnologías existentes no logran abordar simultáneamente:

1. Privacidad Computacional: Proteger los datos de proveedores honestos pero curiosos (abordado por el Cifrado Completamente Homomórfico (FHE) y los Entornos de Ejecución Confiables (TEEs)).
2. Denegabilidad Plausible: La capacidad de negar de manera creíble la existencia o la intención de una computación cuando se es coaccionado por un adversario poderoso.

Las soluciones actuales presentan brechas críticas:

• FHE: Aunque oculta los valores de los datos, la transmisión de los criptogramas es conspicua. Un adversario coercitivo puede exigir las claves de descifrado, y el mero uso de FHE confirma que se está realizando una computación privada.
• TEEs: Producen registros de atestación que sirven como prueba innegable de ejecución. Además, son vulnerables a fugas por canales laterales.
• Computación Multipartita Segura (MPC): Aunque es robusta contra la revelación de la parte de un solo participante, no permite que los participantes nieguen que la computación ocurrió o que sustituyan una computación diferente.
• Cifrado/Almacenamiento Denegable: Estos abordan datos estáticos (mensajes o archivos), pero no se extienden a la intención computacional dinámica.

El artículo identifica una brecha donde un usuario necesita externalizar una computación booleana mientras mantiene la capacidad de negar qué se computó y, ante un observador externo, que ocurrió una computación en absoluto.

2. Metodología

Los autores proponen PD-FHC, un marco que integra computaciones booleanas en un medio de cobertura (específicamente imágenes RGB) utilizando puertas Fredkin y esteganografía de bit menos significativo (LSB).

Mecanismo Central:

• Cableado Compartido, Semántica Variable: El marco utiliza un cableado único y fijo de puertas Fredkin universales. Una puerta Fredkin es una puerta reversible de 3 entradas/3 salidas donde un bit de control determina si los dos bits de datos se intercambian.
  • Si el bit de control es 0, la puerta actúa como un paso directo (pass-through).
  • Si el bit de control es 1, la puerta intercambia los bits de datos.
  • Al establecer los bits de control mediante datos embebidos, el mismo cableado físico puede implementar diferentes funciones lógicas (por ejemplo, AND, OR, NOT, o circuitos complejos) en diferentes ubicaciones.
• Embebido de Multi-ubicación: El usuario (Alice) embebe un circuito "real" y $L-1$ circuitos "señuelo" en los LSB de una imagen.
  • Circuito Real: Embebido en un conjunto de posiciones secretas $\Lambda_{j^*}$.
  • Circuitos Señuelo: Embebidos en otros conjuntos de posiciones disjuntas $\Lambda_j$.
  • Bits de Relleno (Fill Bits): Todas las posiciones LSB restantes se llenan con bits extraídos de una distribución específica $\pi$.
• Procesamiento Uniforme: El proveedor de la nube (Carol) recibe la imagen y la especificación del cableado ($C_{obf}$). Ella aplica la puerta Fredkin de manera uniforme a cada posición de píxel en paralelo. Ella no sabe qué posiciones contienen datos reales, datos señuelo o ruido de relleno.
• Respuesta ante Coerción: Si es coaccionada, Alice revela los conjuntos de posiciones, las entradas y las salidas para un circuito señuelo. Debido a que el cableado es idéntico y el circuito señuelo produce resultados verificables consistentes con la salida de la nube, el adversario no puede distinguir el circuito señuelo del real.

Fundamentos Teóricos:

• Medio de Computación Denegable (DCM): Un marco abstracto que define un medio con posiciones de bits direccionables, capacidades de lectura/escritura y una familia de puertas que se aplica uniformemente.
• Condición de Marginal Coincidente (Matched-Marginal Condition): Para la seguridad de información, los bits en las posiciones reales, las posiciones señuelo y las posiciones de relleno deben ser extraídos de la misma ley de probabilidad por posición $\pi$. Bajo esta condición, el plano LSB es "intercambiable", lo que significa que la distribución estadística de la imagen es invariante a la permutación de las posiciones.

3. Contribuciones Clave

1. Marco Abstracto: Definición de un Medio de Computación Denegable (DCM) y un Esquema de Computación Denegable (DCS) que separan el modelo de seguridad del medio de cobertura específico (por ejemplo, imágenes, audio, paquetes).
2. Formalización del Modelo de Amenaza: Un modelo de dos fases que distingue entre:
   • Nube Honesta-pero-Curiosa (HBC): Preocupada por la privacidad computacional (ocultar los datos).
   • Adversario Coercitivo: Preocupado por la denegabilidad plausible (ocultar la existencia y la intención de la computación).
   • Los autores definen nuevos juegos de coerción de múltiples rondas que miden la "distinción de existencia" (¿puede el adversario probar que existen circuitos ocultos?) y el "descubrimiento de circuitos" (¿puede el adversario identificar el circuito real entre los señuelos revelados?).
3. Instanciación Basada en Imágenes: Una implementación concreta utilizando imágenes RGB y puertas Fredkin.
   • Prueba de Privacidad de Posición: Bajo la condición de marginal coincidente, el artículo demuestra que el proveedor de la nube obtiene cero ventaja (informacionalmente) en localizar las posiciones del circuito real en comparación con el azar, independientemente de la distribución $\pi$.
   • Ocultación Parcial del Circuito: El cableado es visible, pero la semántica de la puerta está oculta. El artículo demuestra que sin el conocimiento de los bits de control, el cableado no revela nada sobre qué función se está computando.
4. Implementación y Benchmarking: Una implementación en Python evaluada a través de tamaños de circuito (5–302 puertas) y dimensiones de imagen ($128^2$ a $512^2$).

4. Resultados

• Garantías de Seguridad:
  • Privacidad Computacional: La nube no aprende nada sobre los valores de los datos secretos ni sobre la función específica computada, siempre que la familia de puertas preserve la distribución estadística de las posiciones no secretas (una propiedad que las puertas Fredkin satisfacen mediante la permutación de bits).
  • Ocultación de Existencia: Bajo la condición de marginal coincidente, la ventaja de existencia es exactamente cero. Un adversario no puede distinguir entre una imagen que contiene solo bits de relleno y una que contiene circuitos ocultos.
  • Descubrimiento de Circuitos: La ventaja de identificar el circuito real entre los señuelos no revelados está limitada por la plausibilidad semántica de los señuelos y la fuga por canal lateral. Los vectores de posición y cableado contribuyen con cero a la ventaja del adversario.
• Rendimiento: La implementación muestra un rendimiento competitivo con TFHE (una biblioteca líder de FHE) para circuitos booleanos, al tiempo que proporciona la denegabilidad que FHE no puede ofrecer.
• Imperceptibilidad Visual: La modificación de los LSB resulta en un desplazamiento máximo de $\pm 1$ por canal, produciendo un PSNR > 50 dB, lo que hace que los cambios sean visualmente imperceptibles.

5. Significancia y Reivindicaciones

El artículo afirma ser el primero en satisfacer simultáneamente la privacidad computacional, la ocultación de existencia (contra observadores externos) y la ocultación parcial del circuito (contra el proveedor de la nube).

Reivindicaciones Modestas y Limitaciones:

• Alcance de la Plausibilidad de la Cobertura: Los autores declaran explícitamente que PD-FHC no funciona para cualquier imagen (por ejemplo, instantáneas de vacaciones). El servicio de cobertura debe esperar legítimamente entradas de LSB de alta entropía (por ejemplo, dithering, inyección de ruido o procesamiento en el dominio cifrado). Si el servicio declarado espera imágenes naturales, el plano LSB uniforme requerido para la seguridad se vuelve detectable.
• Restricciones de Entrada Real: La garantía de ventaja cero de información es exacta solo si los bits de entrada reales del usuario también siguen la misma distribución $\pi$ que los bits señuelo y de relleno. Para entradas reales estructuradas, la ventaja está limitada por la distancia estadística ($\Delta$) entre la distribución de la entrada real y $\pi$.
• Plausibilidad Semántica: La seguridad contra el descubrimiento de circuitos depende de la $\epsilon$-plausibilidad de los circuitos señuelo. El artículo admite que construir circuitos señuelo semánticamente creíbles (por ejemplo, una comprobación de brillo frente a un hash criptográfico) es una tarea manual y específica del dominio que aún no está automatizada.
• Ataques Activos: El marco asume una nube honesta-pero-curiosa y observadores externos pasivos. No protege contra atacantes activos que puedan modificar la imagen o negarse a computar.
• Sin Ofuscación Criptográfica: El artículo evita explícitamente reclamar ofuscación de circuitos criptográfica (que está sujeta a resultados de imposibilidad). La "ofuscación" es puramente esteganográfica, dependiendo de los bits de control ocultos para variar la semántica de las puertas.

En resumen, PD-FHC ofrece un enfoque novedoso para la externalización de la computación donde el usuario puede negar de manera creíble la intención específica de la computación presentando una función alternativa verificable que es indistinguible de la real bajo coerción, siempre que se cumplan las condiciones estadísticas del medio de cobertura.