Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes

1. Problema

El objetivo central es calcular la suma total de bits (el número de unos) en una colección de $k$ cadenas binarias privadas de longitud $n$, sin revelar la información individual de ningún cliente ni la suma parcial de subconjuntos de clientes.

• Contexto: Aplicaciones en vigilancia epidemiológica (conteo de positivos sin diagnósticos individuales) o analíticas federadas.
• Limitaciones de enfoques existentes:
  • MPC (Cálculo Seguro Multi-Parte): Alto costo de comunicación y computación que escala con la complejidad del circuito.
  • Criptografía Homomórfica (HE): Requiere infraestructura de clave pública y tiene un costo operativo significativo por operación.
  • Privacidad Diferencial (DP): Sacrifica la precisión (introduce ruido) para garantizar la privacidad, ofreciendo resultados aproximados en lugar de exactos.

2. Metodología: Protocolo PolyVeil

El protocolo introduce un nuevo paradigma llamado Privacidad Combinatoria, basado en la codificación de datos binarios como matrices de permutación dentro del Polítopo de Birkhoff (el conjunto de matrices doblemente estocásticas).

Arquitectura de Dos Capas

El protocolo corrige vulnerabilidades de versiones anteriores mediante una arquitectura que separa la información entre dos entidades no colusivas:

1. Servidor (S): Recibe solo escalares agregados.
2. Agregador (A): Recibe las matrices enmascaradas pero no los valores de ruido individuales.

Funcionamiento del Protocolo (Variante Completa - Algoritmo 3)

1. Codificación del Cliente: Cada cliente $t$ codifica su flujo de bits $b_t$ en una matriz de permutación $M_t$ de tamaño $2n \times 2n$ (usando bloques diagonales $2 \times 2$).
2. Enmascaramiento (Mixing): El cliente genera $K_t$ matrices de permutación aleatorias (decoy) $P_{t,i}$ y coeficientes positivos $\alpha_{t,i}$. Construye una matriz doblemente estocástica enmascarada:
   $$D_t = \alpha^* M_t + \sum_{i=1}^{K_t} \alpha_{t,i} P_{t,i}$$
   Donde $\alpha^*$ es un parámetro público que controla la señal.
3. Extracción de Ruido: El cliente calcula un término de ruido escalar $\eta_t$ basado en las permutaciones decoy y lo envía a un canal de agregación de ruido separado.
4. Agregación:
   • El Agregador recibe las matrices $D_t$, calcula $F = \sum w^T D_t y$ (donde $w, y$ son vectores de selección) y envía $F$ al servidor.
   • El Agregador de Ruido (entidad separada) suma los $\eta_t$ y envía $H = \sum \eta_t$ al servidor.
5. Recuperación Exacta: El servidor calcula la suma total exacta:
   $$S = \frac{F - H}{\alpha^*}$$
   El ruido algebraico se cancela perfectamente, permitiendo un resultado exacto.

Variante Comprimida

Existe una variante donde los clientes envían solo el escalar $f_t = \alpha^* s_t + \eta_t$ al agregador, reduciendo la comunicación de $O(n^2)$ a $O(1)$ por cliente.

3. Contribuciones Clave

A. Detección y Corrección de la "Ataque de Desorden" (De-shuffling Attack)

El análisis revela una vulnerabilidad fatal en protocolos simples: si el servidor ve los valores escalares vinculados a la identidad ($f_t$) y los valores de ruido mezclados ($\eta_t$), puede recuperar los datos individuales con probabilidad 1.

• Mecanismo: El servidor prueba todas las permutaciones posibles de asignar $\eta_t$ a $f_t$. Debido a la restricción de integralidad (la suma de bits $s_t$ debe ser un entero entre 0 y $n$), solo una asignación produce enteros válidos para todos los clientes, revelando los datos exactos.
• Solución: La arquitectura de dos capas elimina esta posibilidad al separar la información: el agregador ve las matrices pero no los $\eta_t$, y el servidor ve los sumatorios pero no las matrices individuales.

B. Seguridad de Dos Capas

1. Seguridad del Servidor (Teórica/Incondicional): El servidor recibe solo $(F, H)$. Se demuestra mediante simulación basada en información que su vista es idénticamente distribuida para cualquier conjunto de entradas que produzca la misma suma total $S$. Esto ofrece seguridad incondicional (distancia estadística cero) contra adversarios computacionalmente ilimitados.
2. Seguridad del Agregador (Computacional): El agregador ve las matrices $D_t$. Recuperar $M_t$ a partir de $D_t$ requiere evaluar la densidad de una matriz doblemente estocástica aleatoria.
   • Resultado Teórico: Se prueba que calcular esta densidad (y por tanto realizar ataques basados en verosimilitud) es un problema #P-difícil, reduciéndose al cálculo del permanente de matrices y discriminantes mixtos. Esto establece una barrera computacional contra adversarios polinomiales.

C. Análisis de Privacidad Diferencial (DP)

Se proporciona un análisis de $(\varepsilon, \delta)$-DP con constantes explícitas para el agregador.

• Hallazgo Crítico: Existe una tensión fundamental.
  • Para lograr una garantía de DP no vacua (donde el ruido oculta la señal), el parámetro $\alpha^*$ debe ser extremadamente pequeño, haciendo que la señal sea indetectable (SNR $\approx 10^{-7}$). En este régimen, la privacidad se debe al ruido, no a la estructura combinatoria.
  • Para que la señal sea detectable (SNR moderado) y útil, el problema de inferencia se vuelve #P-difícil gracias a la estructura del polítopo de Birkhoff, pero la garantía de DP formal se vuelve vacua.
• Conclusión: El protocolo no logra simultáneamente una DP no vacua y seguridad computacional en el mismo régimen de parámetros, lo que se identifica como una pregunta abierta central.

4. Resultados Principales

• Exactitud: El protocolo devuelve la suma exacta de los bits, a diferencia de los métodos de DP que introducen error.
• Complejidad de Comunicación:
  • Variante completa: $O(kn^2)$.
  • Variante comprimida: $O(k)$ (independiente de $n$), sin necesidad de acuerdo de claves par a par.
• Seguridad:
  • El servidor no puede aprender nada sobre los datos individuales (seguridad teórica perfecta).
  • El agregador no puede aprender los datos individuales en tiempo polinomial (seguridad computacional basada en #P).
• Evaluación Numérica: En la variante comprimida, se logra un $\varepsilon \approx 13$ con un SNR $\approx 1$, lo que implica que el agregador reduce su incertidumbre sobre los datos individuales en menos del 0.3% (MMSE), aunque la garantía de DP formal es débil.

5. Significado e Impacto

El trabajo define un nuevo paradigma de Privacidad Combinatoria, distinto de:

• MPC/HE: Que dependen de la dureza de problemas de teoría de números (factorización, LWE).
• DP: Que depende del ruido estadístico y sacrifica precisión.

PolyVeil utiliza la estructura combinatoria intrínseca de los polítopos (la no unicidad de la descomposición de Birkhoff) para crear una barrera computacional. Su contribución más profunda es demostrar que la seguridad puede derivarse de la dificultad de contar descomposiciones en un polítopo (#P-dureza), ofreciendo resultados exactos sin infraestructura de clave pública.

Desafío Abierto: La principal limitación identificada es la brecha entre el régimen de seguridad computacional (señal visible pero difícil de decodificar) y el régimen de privacidad diferencial no vacua (señal invisible). Cerrar esta brecha para lograr ambas propiedades simultáneamente es el problema central para futuras investigaciones.