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

Resumo Técnico: PolyVeil e Privacidade Combinatória

1. Problema Abordado

O artigo aborda o problema fundamental da soma booleana privada (private Boolean summation) em um cenário de multi-partes.

• Cenário: $k$ clientes, cada um possuindo uma string binária privada de comprimento $n$.
• Objetivo: Um servidor deseja calcular a soma total de todos os bits (o número total de uns) através de todos os $k \times n$ bits, sem aprender qualquer informação sobre os dados individuais de qualquer cliente ou sobre somas parciais.
• Desafio: Equilibrar a precisão exata do resultado com garantias de privacidade robustas, superando as limitações de métodos existentes como Criptografia Homomórfica (custo computacional alto), Computação Segura Multi-Partes (MPC - escalabilidade limitada) e Privacidade Diferencial (DP - perda de precisão devido ao ruído).

2. Metodologia: O Protocolo PolyVeil

Os autores propõem o protocolo PolyVeil, baseado no conceito de Privacidade Combinatória. A ideia central é codificar os dados binários privados como matrizes de permutação dentro do Poliedro de Birkhoff (o conjunto de matrizes duplamente estocásticas).

Mecanismo de Codificação:

1. Codificação: Cada cliente codifica seu bitstream $b$ em uma matriz de permutação $M(b)$ de tamanho $2n \times 2n$, usando uma estrutura de bloco-diagonal onde cada par de bits corresponde a um bloco $2 \times 2$ (Matriz Identidade para 0, Matriz de Troca para 1).
2. Mascaramento (Ocultação): O cliente mistura sua matriz $M(b)$ com $K_t$ matrizes de permutação aleatórias (decoys) $P_i$, ponderadas por coeficientes positivos $\alpha_i$. O resultado é uma matriz duplamente estocástica $D_t$:
   $$D_t = \alpha^* M(b) + \sum_{i=1}^{K_t} \alpha_{t,i} P_{t,i}$$
   Onde $\alpha^* + \sum \alpha_{t,i} = 1$.
3. Extração Algébrica: Existe um vetor de seleção $w$ tal que $w^T M(b) y = \sum b_j$ (soma dos bits). O servidor calcula uma projeção linear $f_t = w^T D_t y$, que resulta em $f_t = \alpha^* s_t + \eta_t$, onde $s_t$ é a soma dos bits do cliente e $\eta_t$ é um termo de ruído calculado pelo cliente.

Arquitetura de Duas Camadas (Solução para Vulnerabilidades):
O artigo identifica que uma implementação ingênua (onde o servidor vê $f_t$ e os valores de ruído $\eta_t$ embaralhados) é vulnerável a um ataque de "desembaralhamento" (de-shuffling) baseado na restrição de integridade dos dados (os bits devem ser inteiros). Para corrigir isso, propõe-se uma arquitetura de duas camadas:

• Camada 1 (Segurança do Servidor): O servidor principal recebe apenas escalares agregados ($F = \sum f_t$ e $H = \sum \eta_t$) de entidades separadas. Isso garante segurança baseada em simulação perfeita (distância estatística zero), pois a visão do servidor é idêntica para qualquer entrada com a mesma soma total.
• Camada 2 (Segurança Computacional do Agregador): Um agregador separado recebe as matrizes completas $D_t$ (sem os valores de ruído $\eta_t$). Para recuperar os dados privados, o agregador precisaria inverter a decomposição de Birkhoff, um problema provado ser NP-difícil e relacionado ao problema #P-difícil do permanente de matrizes (Permanent) e discriminantes mistos.

3. Principais Contribuições

1. Novo Paradigma (Privacidade Combinatória): Introduz uma abordagem que deriva a segurança da estrutura combinatória do poliedro de Birkhoff (não unicidade das decomposições) em vez de apenas de suposições de dificuldade numérica (como fatoração) ou ruído estatístico.
2. Análise de Vulnerabilidade Crítica: Demonstra matematicamente que protocolos de agregação simples são vulneráveis a ataques de desembaralhamento determinísticos quando os dados têm restrições de integridade (Theorem 5.1).
3. Protocolo Corrigido de Duas Camadas: Desenvolve o Algorithm 3, que separa a informação entre um agregador (que vê as matrizes) e um servidor (que vê apenas escalares), garantindo que nenhuma entidade única possa aprender os dados individuais.
4. Provas de Segurança Rigorosas:
   • Segurança do Servidor: Prova de simulação perfeita (informação-teórica).
   • Segurança do Agregador: Redução do problema de inferência de máxima verossimilhança para o cálculo do permanente de matrizes (problema #P-completo), tornando ataques baseados em verossimilhança computacionalmente intratáveis.
5. Análise de Privacidade Diferencial (DP) com Constantes Explícitas: Fornece uma análise de $(\epsilon, \delta)$-DP para o agregador em regime de amostra finita, utilizando o teorema de Berry-Esseen e limites de concentração de Hoeffding.

4. Resultados e Análise de Trade-off

O artigo revela uma tensão fundamental entre os dois regimes de segurança do protocolo:

• Regime de DP Não-Vazio (Pequeno $\alpha^*$):
  • Para obter um $\epsilon$ de DP significativo (não trivial), o parâmetro de sinal $\alpha^*$ deve ser extremamente pequeno ($\sim 10^{-10}$).
  • Resultado: Neste regime, a relação sinal-ruído (SNR) é tão baixa que o sinal dos dados privados é indetectável por qualquer método (incluindo métodos espectrais ou de programação linear). A garantia de DP é tecnicamente correta, mas trivialmente verdadeira porque o ruído esconde completamente o sinal.
• Regime de Segurança Computacional (Moderado $\alpha^*$):
  • Para $\alpha^* \approx 1/(4n)$, o sinal é visível, mas a extração eficiente é bloqueada pela complexidade #P do problema de decomposição.
  • Resultado: O agregador pode ver o sinal, mas não consegue computacionalmente decodificá-lo devido à estrutura combinatória do poliedro de Birkhoff.
• Versão Comprimida: Uma variante onde o agregador recebe apenas um escalar por cliente ($f_t$) em vez da matriz completa.
  • Vantagem: Reduz a complexidade de comunicação para $O(k)$ e permite uma análise de DP univariada.
  • Desvantagem: A estrutura do poliedro de Birkhoff não contribui para a DP nesta versão (o ruído atua como aditivo simples), e o melhor $\epsilon$ encontrado é moderado ($\approx 13$), indicando uma proteção fraca, embora não vazia.

5. Significado e Conclusão

O trabalho estabelece o PolyVeil como um marco na privacidade de dados, introduzindo a Privacidade Combinatória.

• Diferenciação: Diferente do MPC/HE (baseado em teoria dos números) e DP (baseado em ruído estatístico), o PolyVeil usa a complexidade combinatória de decompor matrizes estocásticas.
• Precisão Exata: Ao contrário da DP tradicional, o protocolo permite a recuperação exata da soma agregada, sem perda de precisão no resultado final.
• Questão em Aberto: O principal desafio futuro é fechar a lacuna entre o regime onde a DP é não-vazia (mas o sinal é invisível) e o regime onde a segurança computacional (#P-difícil) é ativa (onde o sinal é visível). O artigo questiona se é possível projetar uma única variante que ofereça simultaneamente uma garantia de DP não-trivial e segurança computacional forte.

Em suma, o PolyVeil oferece uma solução teoricamente robusta para agregação de dados com precisão exata, utilizando a geometria de poliedros para criar barreiras computacionais contra adversários, embora a implementação prática de uma privacidade diferencial forte e não-trivial neste contexto ainda apresente desafios significativos de sinal-ruído.