Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

Título: Além de Épsilon: Uma Estrutura QIF Principiada para Privacidade Diferencial Local

Enunciado do Problema
A Privacidade Diferencial Local (LDP) tornou-se o padrão para coleta de dados com preservação de privacidade em sistemas de grande escala, particularmente para estimativa de frequência. No entanto, o cenário atual para comparação de protocolos LDP depende fortemente de duas abordagens limitadas:

1. O parâmetro $\epsilon$: Este limita a distinguibilidade no pior caso, mas falha em capturar o vazamento de informação real sob ataques de inferência realistas (por exemplo, reconstrução de dados ou reidentificação). Dois protocolos que satisfazem a mesma garantia de $\epsilon$-LDP podem exibir comportamentos de vazamento significativamente diferentes.
2. Análise orientada à utilidade: Os protocolos são classificados com base no erro de estimativa (por exemplo, Erro Quadrático Médio) para um $\epsilon$ fixo. Esta visão é dependente da métrica e não fornece uma ordenação principiada da força da privacidade independente da função de utilidade específica.

Consequentemente, há uma falta de um método sistemático e independente do adversário para determinar quando um protocolo LDP é intrinsecamente mais privado que outro.

Metodologia
Os autores propõem uma estrutura baseada em Fluxo Quantitativo de Informação (QIF) para analisar protocolos de estimativa de frequência LDP. A metodologia central envolve:

• Modelagem de Canal: Representar mecanismos LDP como canais probabilísticos de teoria da informação definidos por matrizes de canal estocásticas por linha ($C_{x,y} = \Pr[Y=y|X=x]$).
• Relações de Refinamento (Ordenação de Blackwell): Utilizar o conceito de refinamento de canal ($B \sqsubseteq A$) para estabelecer uma ordem parcial. O protocolo $A$ refina $B$ se $A$ não vazar mais informação que $B$ para qualquer adversário de caso médio, independentemente de seu conhecimento prévio ou função de ganho específica. Isso é equivalente a $A$ ser um "embaralhamento" de $B$ (isto é, $B \cdot W = A$ para algum canal $W$).
• Conexão com Privacidade Diferencial $f$: Aproveitar a equivalência entre o refinamento QIF e a ordenação das funções de compromisso em $f$-DP (derivada do lema de Neyman-Pearson) para comparar mecanismos, particularmente para canais binários.
• Medidas de Vulnerabilidade: Analisar protocolos usando a capacidade de Bayes (vazamento máximo de caso médio) e vincular ataques de reconstrução de dados diretamente à vulnerabilidade de Bayes sob uma priora uniforme.

Os autores aplicam esta estrutura a sete protocolos de última geração: Resposta Aleatorizada Generalizada (GRR), Seleção de Subconjunto (SS), Hashing Local Binário (BLH), Hashing Local Otimizado (OLH), Codificação Unária Simétrica (SUE), Codificação Unária Otimizada (OUE) e Limiar com Codificação de Histograma (THE).

Principais Contribuições

1. Estrutura QIF Unificada: O artigo fornece uma estrutura independente de métrica para comparar protocolos LDP por meio de matrizes de canal e relações de refinamento, permitindo comparações entre adversários e funções de utilidade diversos.
2. Ponte entre LDP e QIF: Os autores demonstram formalmente que os ataques de reconstrução de dados estudados na literatura anterior coincidem com as noções padrão de QIF de vulnerabilidade de Bayes. Especificamente, a taxa de sucesso esperada de tais ataques corresponde à capacidade de Bayes do canal LDP.
3. Correção da Análise de Hashing Local: O artigo identifica e corrige um erro na análise esperada de ataque de reconstrução de dados para protocolos de Hashing Local (LH) (especificamente BLH e OLH) relatada em trabalhos anteriores [8]. Os autores derivam o risco de Bayes correto via vulnerabilidade média, fornecendo uma fórmula que coincide com avaliações experimentais para todos os tamanhos de domínio, ao contrário da aproximação anterior que falhava para domínios pequenos.
4. Análise de Refinamento: O estudo estabelece relações de refinamento entre protocolos, descobrindo que:
   • As famílias GRR, SUE, OUE e THE formam "famílias de refinamento" onde a monotonicidade da privacidade vale em relação a $\epsilon$.
   • OUE e SUE são incomparáveis (nenhum refina o outro) no cenário bit a bit.
   • THE refina SUE para todo $\theta$, mas a relação entre THE e OUE depende do limiar $\theta$ e de $\epsilon$.
   • Protocolos anteriormente considerados "ótimos" com base em métricas de erro são às vezes estritamente dominados por ou incomparáveis a outros protocolos quando vistos através da lente do vazamento de informação.

Resultados

• Validação Experimental: Usando o conjunto de dados Kosarak, os autores corroboraram experimentalmente as relações de refinamento teóricas. Por exemplo, confirmaram que, quando o limiar $\theta$ em THE satisfaz condições específicas em relação a $\epsilon$, o OUE vaza mais informação que o THE; caso contrário, a relação não é de refinamento.
• Convergência da Capacidade de Bayes: A análise das capacidades de Bayes revelou comportamentos de convergência distintos à medida que $\epsilon$ aumenta:
  • GRR, SS e THE convergem para $k$ (o tamanho do domínio).
  • SUE converge para um valor ligeiramente superior a $k$.
  • BLH converge para 2 (devido à sua saída binária).
  • OLH e OUE convergem para aproximadamente $k/2$.
• Correção de Fórmulas de LH: A nova fórmula para a Taxa de Sucesso do Adversário (ASR) de Hashing Local (Eq. 26) mostrou-se compatível com os resultados experimentais para todos os $k$ e $\epsilon$, ao passo que a fórmula anterior (Eq. 25) desviava-se significativamente para tamanhos de domínio pequenos.

Significado
O artigo afirma preencher a lacuna entre as comunidades de LDP e métodos formais. Ao ir além do único parâmetro $\epsilon$ e das métricas específicas de utilidade, a abordagem baseada em QIF proposta permite um "raciocínio principiado e consciente do adversário" sobre sistemas localmente privados. Revela que classificações baseadas exclusivamente no erro de estimativa podem ser enganosas, pois podem ignorar casos em que um protocolo é estritamente dominado por outro em termos de vazamento de privacidade. A estrutura oferece um método mais robusto e abrangente para avaliar a superioridade dos protocolos, garantindo que as garantias de privacidade sejam compreendidas não apenas como limites de pior caso, mas como medidas precisas de fluxo de informação contra modelos de ameaça diversos.