Resumo Técnico: Composição para Pufferfish Privacy

Declaração do Problema

A Privacidade Diferencial (DP) é o padrão ouro para proteção de privacidade, amplamente implementada por grandes organizações devido às suas garantias rigorosas e, crucialmente, às suas propriedades de composição. A composição permite que a perda de privacidade de um sistema complexo seja calculada como a soma das perdas de seus mecanismos constituintes, permitindo a construção de sistemas de grande escala para preservação de privacidade a partir de componentes menores.

No entanto, para conjuntos de dados com fortes correlações (por exemplo, registros médicos onde o status de infecção de uma pessoa afeta outros), as semânticas padrão de DP podem ser excessivamente restritivas ou sem sentido. A Pufferfish privacy, uma definição baseada em inferência/posterior, aborda isso ao permitir que curadores de dados especifiquem um conjunto de distribuições a priori e pares de segredos, garantindo que um adversário bayesiano aprenda pouco sobre segredos específicos. Apesar de suas vantagens semânticas para dados correlacionados, a Pufferfish é raramente usada na prática porque carece de garantias de composição.

O artigo identifica uma falha crítica: é possível projetar mecanismos Pufferfish que possuem zero vazamento de privacidade quando executados uma única vez, mas que revelam todo o conjunto de dados quando executados múltiplas vezes (um fenômeno termo de colapso de privacidade). Essa falta de composição torna o design de plataformas de consultas múltiplas baseadas em Pufferfish intratável, pois cada novo mecanismo exige uma análise conjunta tediosa e manual de como ele interage com todos os outros mecanismos suportados.

Metodologia

Os autores investigam as condições necessárias e suficientes exigidas para garantir a composição linear para mecanismos Pufferfish. Sua abordagem envolve três pilos teóricos principais:

1. Demonstração de Colapso de Privacidade

O artigo constrói contraexemplos específicos (Teoremas 1, 2 e 3) mostrando que definições baseadas em posterior, incluindo Pufferfish, não defendem inerentemente contra o vazamento de privacidade via composição.

• Segredo/prior único: Um mecanismo pode retornar uma tupla onde os componentes dependem do segredo de uma forma que, quando executado duas vezes, permite que um atacante deduza o verdadeiro conjunto de dados com alta probabilidade, apesar de ter zero vazamento em uma única execução.
• Múltiplos segredos/priors: Mesmo com conjuntos expandidos de segredos ou priors, mecanismos podem ser projetados para satisfazer a privacidade Pufferfish para uma única execução, mas falhar catastroficamente após a composição.

2. Condições Necessárias (Restrições NfC)

Os autores provam que, para um conjunto de mecanismos Pufferfish comporem linearmente, eles devem satisfazer uma classe de restrições chamada restrições NfC (Necessária para Composição).

• Essas restrições assumem a forma de desigualdades envolvendo combinações convexas de log-probabilidades de saídas de mecanismos através de diferentes conjuntos de dados.
• Crucialmente, o artigo prova que, para que essas restrições também sejam invariantes à pós-processamento (uma propriedade fundamental para utilidade prática), as restrições devem reduzir-se às desigualdades padrão de Privacidade Diferencial (DP).
• Insight Chave: Para alcançar a composição linear em Pufferfish, os mecanismos devem essencialmente satisfazer uma forma de privacidade diferencial. O parâmetro de privacidade Pufferfish $\epsilon_{puffer}$ não pode ser garantido para compor linearmente sem adotar restrições do tipo DP.

3. Condições Suficientes e a Curva de Influência $a(b)$

Para preencher a lacuna entre DP e Pufferfish, os autores introduzem a curva de influência $a(b)$.

• Definição: Esta curva caracteriza o pior caso de vazamento de informação através de um conjunto de entradas de "baixa influência" ($L$) quando um conjunto de "alta influência" ($H$) de tamanho $b$ é permitido variar. Ela quantifica o quanto um segredo pode influenciar o restante do conjunto de dados além de um grupo específico de tamanho $b$.
• Tradução: O artigo estabelece uma fórmula de tradução: se um mecanismo satisfaz a $\epsilon_{DP}$-privacidade diferencial por entrada, ele satisfaz a $\epsilon_{puffer}$-privacidade Pufferfish onde:
  $$\epsilon_{puffer} = b \cdot \epsilon_{DP} + a(b)$$
  Aqui, $b \cdot \epsilon_{DP}$ contabiliza a privacidade de grupo de $b$ entradas, e $a(b)$ é a penalidade pelas correlações que se estendem além desse grupo.
• Composição: Os autores provam que, se os mecanismos forem construídos usando esta tradução, seus parâmetros Pufferfish compõem linearmente (especificamente, de forma subaditiva). A "penalidade" $a(b)$ é paga apenas uma vez, não por mecanismo, permitindo uma melhor utilidade do que a simples adição.

Principais Contribuições

1. Prova de Colapso de Privacidade: O artigo demonstra rigorosamente que definições de privacidade baseadas em posterior (como Pufferfish) não são robustas à composição sem restrições adicionais, mostrando mecanismos que são seguros isoladamente, mas falham completamente quando compostos.
2. Condições Necessárias e Suficientes: Os autores provam que a composição linear em Pufferfish necessita a inclusão de desigualdades do tipo privacidade diferencial (restrições NfC). Eles mostram que apenas restrições do tipo DP são invariantes à pós-processamento dentro deste framework.
3. Framework da Curva de Influência $a(b)$: Eles introduzem um framework geral para traduzir qualquer mecanismo DP existente de per-entry em um mecanismo Pufferfish composível. Isso generaliza o trabalho anterior (ex: o Mecanismo de Markov Quilt de Song et al.) que era limitado ao ruído de Laplace e priors de redes de Markov.
4. Robustez à Incerteza do Prior: O framework inclui métodos para lidar com priors mal especificados, permitindo que curadores computem limites superiores para a curva de influência mesmo quando a distribuição real dos dados é incerta (ex: dentro de uma margem de erro de 20%).

Resultados Experimentais

Os autores avaliam seu framework (denominado Ours-Exp) contra o estado da arte do Mecanismo de Markov Quilt (MQM) em dois conjuntos de dados do mundo real com fortes correlações temporais:

• Conjunto de Dados Foursquare Check-in: Dados de localização com alta correlação de usuário.
• Conjunto de Dados Capture24: Dados de monitoramento de atividade de 24 horas.

Descobertas:

• Utilidade Superior: O framework proposto supera significativamente o MQM em todos os parâmetros de privacidade ($\epsilon_{puffer}$) e métricas (Accuracy@k, Hit Rate, NDCG, erro de contagem $\ell_1$).
• Flexibilidade do Mecanismo: A melhoria decorre da capacidade do framework de adaptar o Mecanismo Exponencial (que é ótimo para consultas Top-$k$) para o cenário Pufferfish. O MQM é restrito ao mecanismo de Laplace, que é menos adequado para consultas de ranking.
• Robustez: A incorporação de 20% de incerteza do prior no cálculo da curva de influência resultou em apenas uma diminuição modesta na utilidade, demonstrando a viabilidade prática do framework mesmo com conhecimento prévio imperfeito.

Significância e Alegações

O artigo alega resolver um grande gargalo que impede o desenvolvimento de plataformas de resposta a consultas baseadas em Pufferfish. Ao provar que mecanismos Pufferfish composíveis devem inerentemente satisfazer restrições de privacidade diferencial, os autores argumentam que o caminho a seguir não é inventar novos mecanismos complexos específicos de Pufferfish, mas sim alavancar a vasta biblioteca de mecanismos de DP existentes.

A significância deste trabalho reside em:

• Unificação: Ele vincula formalmente Pufferfish e Privacidade Diferencial, mostrando que alcançar semânticas interpretáveis para dados correlacionados e benefícios de composição requer a adoção de mecanismos de DP.
• Praticidade: Fornece uma "receita" para designers de sistemas: calcule a curva de influência $a(b)$ para seus dados e segredos específicos e, então, simplesmente reescale o orçamento de privacidade de qualquer algoritmo DP para alcançar uma garantia Pufferfish composível.
• Generalização: Vai além das limitações do trabalho anterior (que era restrito a ruído de Laplace e redes de Markov) para suportar conjuntos de dados tabulares gerais e priors arbitrários.

Os autores concluem que seus resultados teóricos implicam que o design de novos mecanismos para Pufferfish deve ser feito construindo sobre as plataformas de DP existentes, tornando a adaptação de DP para Pufferfish um processo inevitável e sistemático, em vez de um heurístico.