Multi-user Pufferfish Privacy

Resumo Técnico: Privacidade Pufferfish Multi-usuário

1. Problema Investigado

O artigo aborda o desafio de garantir a indistinguibilidade individual em sistemas multi-usuário onde os dados são inerentemente estocásticos (aleatórios). Diferentemente da Privacidade Diferencial (DP) clássica, que assume que os dados de origem são determinísticos (cada indivíduo reporta sempre o mesmo valor), este trabalho considera cenários onde:

• Os usuários reportam realizações de variáveis aleatórias (ex: dados que variam ao longo do tempo ou em pesquisas sensíveis).
• O sistema deve proteger contra ataques de inferência de associação (membership inference) e inferência de atributos.
• As ameaças incluem: um usuário alterar seu valor reportado, um usuário sair do sistema (ausência) ou ser substituído por outro usuário com características estatísticas diferentes.

O objetivo é calibrar o ruído adicionado a uma consulta agregada (soma) de modo a satisfazer o framework de Privacidade Pufferfish, garantindo que um adversário não possa distinguir entre diferentes cenários de segredos (secrets) com base na saída da consulta.

2. Metodologia

Os autores utilizam o framework de Privacidade Pufferfish, proposto por Kifer e Machanavajjhala, que generaliza a Privacidade Diferencial ao permitir que o banco de dados seja condicionado estatisticamente a um segredo e que o adversário possua crenças prévias.

• Mecanismo de Ruído: Adiciona-se ruído Laplaciano ($N_\theta$) à resposta da consulta agregada $Y = X + N_\theta$.
• Calibração de Ruído (Método Kantorovich): Em vez de usar a sensibilidade $\ell_1$ tradicional, o artigo emprega a métrica de Wasserstein de ordem 1 (distância de transporte óptimo de Kantorovich). A escala do ruído $\theta$ é determinada pela distância máxima entre as distribuições de probabilidade dos segredos em questão.
• Modelo do Sistema:
  • Um conjunto de usuários $V$, onde cada usuário $i$ tem uma probabilidade de presença $\zeta_i$.
  • Cada usuário reporta uma variável aleatória $D_i$.
  • A consulta é uma soma separável: $X = \sum D_i$.
  • O segredo $S$ pode ser o valor específico reportado, a presença/ausência do usuário ou a distribuição de probabilidade que os dados do usuário seguem.

3. Principais Contribuições

O artigo deriva condições suficientes para atingir a privacidade Pufferfish em quatro cenários de pares de segredos distintos, demonstrando que a proteção depende apenas das estatísticas do usuário individual em questão, e não dos outros usuários no sistema.

1. Indistinguibilidade de Valores ($S_{a,b}$):

   • Garante que não se possa distinguir se um usuário reportou o valor $a$ ou $b$.
   • Resultado: A escala do ruído deve ser $\theta = \frac{\max |a_i - b_i|}{\epsilon}$. Isso é análogo à sensibilidade $\ell_1$, mas aplicado a variáveis aleatórias.

2. Indistinguibilidade de Presença/Ausência ($S_{a,\perp}$):

   • Garante que não se possa distinguir se um usuário está presente reportando o valor $a$ ou ausente.
   • Resultado: A ausência é tratada como a reportagem de zero. A escala necessária é $\theta = \frac{\max |a_i|}{\epsilon}$.

3. Indistinguibilidade de Distribuições (Presença vs. Ausência) ($S_{P,\perp}$):

   • Garante que não se possa distinguir se um usuário está presente seguindo uma distribuição $P_i$ ou ausente.
   • Condição Relaxada: Para variáveis binárias (Bernoulli), os autores derivam uma condição suficiente relaxada que permite reduzir o ruído. A condição exata envolve resolver $E[e^{|D_i|/\theta}] = e^\epsilon$.
   • Significado: Permite proteger classes inteiras de registros (ex: remover todos os dados de um grupo demográfico específico) com menos ruído do que métodos conservadores.

4. Indistinguibilidade de Distribuições (Troca de Usuário) ($S_{P,Q}$):

   • Garante que não se possa distinguir se um usuário segue a distribuição $P_i$ ou $Q_i$.
   • Resultado: Utiliza a distância de transporte ótimo entre as distribuições $P_i$ e $Q_i$. Para variáveis binárias, é proposta uma condição relaxada (Lema 2) que calcula $\theta$ baseado nas probabilidades específicas e nas estatísticas dos outros usuários, resultando em menor ruído do que a abordagem conservadora ($\theta = 1/\epsilon$).

4. Resultados Experimentais

Os autores validaram suas teorias em três conjuntos de dados reais do repositório UCI: Adult, Bank Marketing e Student Performance.

• Redução de Ruído: A aplicação das condições relaxadas (especialmente para variáveis binárias e distribuições distintas) resultou em uma redução significativa no parâmetro de escala $\theta$ em comparação com as condições conservadoras (baseadas no valor máximo absoluto).
• Utilidade dos Dados: A redução do ruído implica em uma maior utilidade dos dados agregados, mantendo o mesmo nível de garantia de privacidade ($\epsilon$).
• Independência de $\zeta_i$: Os experimentos confirmaram que as condições suficientes derivadas são independentes da probabilidade de presença ($\zeta_i$) dos usuários, simplificando a implementação em sistemas dinâmicos.
• Método Numérico: Foi demonstrado que o uso do método de Brent para resolver a equação não linear na condição relaxada (Teorema 3) é viável e eficaz para encontrar o $\theta$ ótimo.

5. Significado e Conclusão

Este trabalho preenche uma lacuna importante na literatura de privacidade, estendendo a calibração de ruído baseada em transporte ótimo (Kantorovich) para o contexto de variáveis aleatórias multi-usuário.

• Inovação Teórica: Demonstra que a privacidade Pufferfish para um indivíduo pode ser garantida analisando apenas as estatísticas desse indivíduo, ignorando a complexidade combinatória do restante do sistema.
• Aplicabilidade Prática: Oferece mecanismos para proteger dados em cenários modernos como aprendizado federado e agregação privada local, onde os dados não são estáticos.
• Eficiência: As condições relaxadas para variáveis binárias e distribuições permitem um equilíbrio muito melhor entre privacidade e utilidade dos dados, reduzindo a quantidade de ruído necessário sem comprometer a segurança contra inferências estatísticas avançadas.

Em suma, o paper fornece uma ferramenta matemática robusta para projetar mecanismos de privacidade em sistemas onde a incerteza e a variabilidade dos dados são inerentes, superando as limitações da Privacidade Diferencial clássica.