Differential Privacy I: Introdução (PT/BR)

O que significa privacidade no contexto de análise de dados? Conheça a "Fundamental Law of Information Recovery" que torna explícito um trade-off inevitável quando se deseja extrair informações úteis de um conjunto de dados que acarreta um risco para a privacidade dos dados. Nos levando ao objetivo da Privacidade Diferencial.

Photo by Matthew Henry on Unsplash

Privacidade Diferencial (Differential Privacy)é um assunto que recentemente se tornou meu alvo de pesquisa e estudo, e materiais em português são bem escassos. Essa série de posts sobre DP em PT/BR, que será dividida em partes, é uma tradução do tutorial escrito pelos autores M. Brubaker e S. Prince, da Borealis AI, e você encontra a versão original disponível blog da Borealis AI: Differential Privacy I: Introduction.

Glossário: (Nomes mais comuns utilizados na literatura, em inglês)
ML: Machine Learning — Aprendizado de Máquina;
DP: Differential Privacy — Privacidade Diferencial;
Linkage Attacks — Ataques de ligação de informações;
k-anonymity , k-anonymous — "Anonimato k", k-anônimo;
ε-differentially private — epsilon-diferencialmente privado;

A recente revolução de aprendizado de máquina vem sendo alimentada por dados, sendo eles comumente providos pelos próprios usuários finais. Considere um fabricante de smartphones tentando tornar a digitação do seu produto mais rápida e precisa, uma loja tentando fazer com que os clientes encontrem os produtos que desejam, ou um médico tentando interpretar um teste médico. ML pode auxiliar nesse processo, mas apenas quando alimentado por dados relacionados sobre o usuário final, o que eles querem comprar, quais os tipos de testes e resultados médicos pacientes recebem, etc. Consequentemente, organizações vem coletando mais e mais dados sobre seus usuários para construírem esses sistemas.

Dado esse cenário, isso aumenta a preocupação em torno da privacidade dos dados. Emails, mensagens de texto e registros médicos contém informações sensíveis/confidenciais e os proprietários esperam que sua privacidade seja fortemente protegida ao usar esses serviços. Ao mesmo tempo, os potenciais benefícios de (por exemplo) um melhor diagnóstico médico, ao fornecer mais dados, são inegáveis. Isso nos deixa com um desafio: como podemos realizar aprendizado de máquina em dados para permitir que tenhamos avanços técnicos sem criar riscos excessivos para a privacidade dos usuários?

Nessa série de posts vamos explorar o problema de privacidade em ML. Nessa primeira parte vamos discutir definições de privacidade em análise de dados e abordar o básico de DP. Em seguida iremos considerar o problema de como aplicar ML com privacidade diferencial.

Abordagens iniciais de privacidade

Primeiramente vamos definir o que realmente significa privacidade no contexto de análise de dados. Trabalhos/pesquisas anteriores se depararam com dificuldades em estabelecer uma definição formal de privacidade que correspondesse às expectativas do usuário e, ao mesmo tempo, fosse prática. Para entender por que isso é difícil, veremos algumas noções prévias relacionadas a privacidade.

Anonimização e Linkage Attacks

A abordagem mais direta é a conhecida como anonimização (anonymization), em que as informações de identificação são removidas. Por exemplo, o nome de um paciente ser removido de um registro médico. Infelizmente, a anonimização raramente é suficiente para proteger a privacidade, pois as informações restantes podem ser de identificação única. Por exemplo, dado o gênero, CEP (código postal), idade, etnia e altura, pode ser possível identificar uma única pessoa, mesmo em uma base de dados consideravelmente grande.

Inclusive, esse caso já aconteceu com o Governador de Massachusetts, William Weld, em 1997. Após um grupo de seguros ter divulgado registros médicos que estavam, obviamente, sem dados pessoais, como nome e endereço do paciente, e um universitário foi capaz de retirar o anonimato (“deanonymize”) dos registros que pertenciam ao Governados Weld cruzando referências com listas eleitorais públicas. Esse é um exemplo de linkage attack, onde conexões com outras fontes de informação são usadas para remover o anonimato em um conjunto de dados. Essas formas de ataques são geralmente bem sucedidas em vários conjuntos de dados anônimos, incluindo um desafio da Netflix onde pesquisadores conseguiram fazer esse cruzamento de informações (Netflix challenge) e também na pesquisa de dados de genoma, abordada no artigo Identifying Participants in the Personal Genome Project by Name (A Re-identification Experiment).

k-anonymity

Outra abordagem para prevenir linkage attacks é k-anonymity. Um conjunto de dados é dito como k-anonymous se, para qualquer registro pessoal no conjunto de dados, existe pelo menos k -1 outros registros que são indistinguíveis. Se o conjunto de dados é k-anonymous, o máximo que um linkage attack poderia fazer é identificar um grupo k de registros que podem pertencer à pessoa de interesse. Mesmo que o conjunto de dados não seja inerentemente k-anonymous, o que pode ser feito é a remoção completa de campos de dados (como nomes e endereços) e uma censura seletiva de campos de pessoas individuais que são particularmente únicas.

Infelizmente, k-anonymity não é suficiente, a não ser para conjuntos de dados muito grandes com um pequeno número de campos simples para cada registro. Intuitivamente, quanto mais campos e quanto mais entradas, mais único um registro pode ser e mais difícil é garantir que haja k registros equivalentes.

Centralização de dados e ataques de rastreamentos

Outra solução é não liberar os dados. Em vez disso, manter os dados centralizados em uma parte confiável na qual obtemos resposta de consultas(queries). Mas como garantir que essas queries não irão vazar informações privadas? Uma ideia pode ser permitir apenas consultas que sejam simples, como contagem. Além disso, respostas só podem ser retornadas quando há um tamanho mínimo do conjunto de queries (por exemplo, estamos contando um grande número de registros).

Infelizmente, esse esquema também é vulnerável a ataques de rastreadores. Considere contar todos os registros de pacientes que são fumantes, e depois contar o número de pacientes que fumam cujo nome não é Marcus Brubaker. Ambas as consultas contam com um grande número de registros, mas juntas identificam se Marcus é fumante. Mesmo que os nomes não estejam disponíveis, uma combinação com um linkage attack pode revelar as mesmas informações.

Lei Fundamental da Recuperação de Informações

Na seção anterior nós vimos abordagens simples em que a privacidade dos dados é vulnerável à ataques. Isso levanta a questão de quando é possível garantir a privacidade individual em um conjunto de dados. Uma definição inicial de privacidade garantiu que nada pudesse ser aprendido sobre um indivíduo quando os dados fossem divulgados. Em essência, essa definição requeria que alguém que observasse os dados divulgados soubesse nada mais sobre o registro do indivíduo do que antes da observação. Infelizmente, essa noção é falha: se você não puder aprender nada de novo a partir de novas observações de dados liberados, então esses dados não devem conter nenhuma informação que já não esteja disponível.

Isso levanta uma questão crítica quando se trata de entender a privacidade com a análise de dados; é impossível permitir a análise de dados úteis sem pelo menos alguma chance de aprender sobre os dados subjacentes. Desde então, foi formalmente demonstrado que, para qualquer mecanismo de consulta que não destrua totalmente as informações, um invasor com acesso a consultas suficientes, pode eventualmente, reconstruir o conjunto de dados. Esse resultado é conhecido como "Lei Fundamental de Recuperação de Informações" e torna explícito um trade-off inevitável. Se você deseja extrair informações úteis de um conjunto de dados, isso acarreta um risco para a privacidade dos dados.

Isso pode parecer condenar toda a noção de análise de dados privados. Mas, na verdade, ele deixa claro que o objetivo deve ser quantificar e limitar quanta privacidade é realmente perdida. Esse é o objetivo da DP.

Photo by NASA on Unsplash

Privacidade Diferencial

Considere um individuo que esta decidindo se deve permitir que seus dados sejam incluídos em um banco de dados. Por exemplo, pode ser um paciente decidindo se seus registros médicos podem ser usados para estudo, ou alguém decidindo se deve responder a um questionário de uma pesquisa. Uma noção útil de privacidade seria uma garantia de que ao permitir que seus dados fossem incluídos, isso teria um impacto insignificante sobre eles no futuro. E como já vimos, a privacidade absoluta é inerentemente impossível, mas o que está sendo garantido aqui é uma chance muito pequena de uma violação da privacidade. Isso é exatamente o que DP oferece.

Resposta Randomizada

DP baseia-se conceitualmente em um método conhecido como resposta aleatória. A ideia principal é introduzir um mecanismo de randomização que forneça uma negabilidade plausível. Considere um questionário de pesquisa que pergunte se as pessoas cometeram fraude em seus impostos. Perguntas sobre os resultados dessa pesquisa podem conceder informações sobre um único indivíduo. No entanto, imagine se as respostas registradas dessa pesquisas são aleatórias; uma moeda é lançada e se o resultado for "cara", uma resposta aleatória é gravada em vez da resposta verdadeira. Com um pouco de cuidado ainda é possível usar os resultados da pesquisa para estimar uma fração de pessoas que cometeram fraude. No entanto, todo individuo tem uma negabilidade plausível: o resultado registrado pode ou não ser o valor verdadeiro e, portanto, a privacidade individual é protegida.

Nesse exemplo, temos um parâmetro que é a probabilidade de que a resposta verdadeira seja registrada. Se for muito provável que a resposta verdadeira é registrada, haverá menos proteção da privacidade. Por outro lado, se for improvável que a resposta verdadeira seja registrada, há mais proteção da privacidade. Também está claro que, independente da probabilidade, se um indivíduo responder a pesquisa várias vezes, haverá menos proteção, mesmo que sua resposta seja potencialmente aleatória todas as vezes. Sendo assim, DP formaliza como definimos, medimos e rastreamos a proteção da privacidade concedida a um indivíduo em função de fatores como a probabilidade de randomização e número de questionários/pesquisas.

Definição clássica de Privacidade Diferencial

Considere duas base de dados D e D', que se diferem em apenas um único registro. Além disso, consideramos um mecanismo aleatório M[•] que opera nas bases de dados para produzir um resultado. Este mecanismo é diferencialmente privado se os resultados de M[D] e M[D'] sejam quase indistinguíveis para cada escolha de D e D'.

Mais formalmente, um mecanismo M[•] é ε-differentially private (ε-DP) se para todos os subconjuntos de saída S ⊂ Range M[•] e banco de dados D e D'

O termo ε (epsilon) controla o quanto a saída do mecanismo pode diferir entre os dois bancos de dados adjacentes, e captura quanta privacidade é perdida quando o mecanismo é executado no banco. Grandes valores de ε correspondem a menores garantias de que a privacidade foi mantida, enquanto valores próximos de zero garantem que menos privacidade seja perdida.

Esta definição é bastante opaca e se não parecer óbvia, não se preocupe. Nos posts seguintes, será fornecido vários exemplos fáceis de entender que tornarão essas idéias claras. No entanto, primeiro iremos reformular a definição de privacidade diferencial em termos de divergências.

Relação com divergências

Existe uma conexão bem próxima entre ε-DP e divergências entre distribuições de probabilidade. Uma divergência é uma medida da diferença entre distribuições de probabilidade. Ela é zero se as distribuições são idênticas e se torna maior quanto mais se diferem.

Dado que o mecanismo M[•] é randomizado, há uma distribuição de probabilidade sobre sua saída. O mecanismo é ε-differentially private se e somente se

para bases de dados D e D' diferindo por no máximo um único registro. Aqui div[⋅ || ⋅] é da Divergência de Renyi de ordem α=∞ (alpha = infinito). Em outras palavras, ε quantifica o quão grande pode ser a divergência entre as distribuições de resultados quando o mecanismo é aplicado a dois conjuntos de dados vizinhos (figura 1).

Da perspectiva de alguém que escolhe fazer parte de um conjunto de dados onde o acesso foi ε-DP, os custos adicionais em média serão um fator de exp[ε] maior do que se eles não participassem. Definindo um valor apropriado de ε para um determinado cenário é um problema desafiador, mas essas conexões e garantias podem ser usadas para ajudar a fazer esse ajuste, dependendo da sensibilidade dos dados e das necessidades da análise.

Propriedades de Privacidade Diferencial

No tópico anterior foi considerado apenas um único mecanismo fixo sendo executado uma vez. No entanto, executar várias consultas ou usar informações externas pode levar a violações de privacidade. Como poderemos ter certeza de que isso não acontecerá aqui? Mecanismos diferencialmente privados possuem duas propriedades valiosas que nos permitem ter algumas garantias.

Pós-processamento: Mecanismos diferencialmente privados são imunes aos pós-processamento. A composição de qualquer função com mecanismo diferencialmente privado permanecerá diferencialmente privada. Mais formalmente, se um mecanismo M[•] é ε-DP e g[•] é uma função qualquer, então g[M[•]] também é pelo menos ε-DP. Isso significa que a privacidade vai ser preservada mesmo na presença de linkage attacks.

Composição: Mecanismos DP são fechados sob composição. Aplicar vários mecanismos (ou o mesmo mecanismo várias vezes) ainda resulta no mecanismo geral sendo diferencialmente privado, mas com um ε diferente. Especialmente, uma composição de k-mecanismos, cada um deles ε-DP, então a composição é pelo menos kε-DP. Isso fornece algumas garantias sobre robustez dos ataques de rastreamento.

A propriedade de pós-processamento nos permite tratar mecanismos DP como peças genéricas. Qualquer uma das grandes bibliotecas de mecanismos podem ser combinados enquanto ainda preservam a privacidade. No entanto, o teorema da composição também deixa claro que há um limite; enquanto a composição preserva a privacidade, o valor de ε aumenta, e portanto a quantidade de privacidade perdida aumenta a cada mecanismo aplicado. Eventualmente, o valor de ε se tornará tão grande que as garantias de privacidade diferencial se tornarão praticamente inúteis.

Conclusão

Neste primeiro post, foi abordado a história da privacidade diferencial, apresentado sua definição formal. Posteriormente você vai saber mais detalhadamente como DP pode ser usada para construir aproximações diferencialmente privadas para algumas consultas de banco de dados comuns. Para obter mais detalhes sobre esses fundamentos, a melhor referência é esta monografia: The Algorithmic Foundations of Differential Privacy.

Na parte II desse post, será coberto alguns exemplos do Mecanismo de Laplace e de outros mecanismos desenvolvidos recentemente, incluindo aqueles que nos permitem realizar aprendizado de máquina privado de forma diferenciada, enquanto ainda desenvolvemos ferramentas de ML padrão. Finalmente, discutiremos DP no contexto de modelos generativos e geração de dados sintéticos.

Referências

Segue-se referências citadas ao longo do texto.

• Blog post original: Tutorial #12: Differential Privacy I: Introduction;
• Netflix Challenge: Why ‘Anonymous’ Data Sometimes Isn’t;
• Identifying Participants in the Personal Genome Project by Name (A Re-identification Experiment);
• “Anonymized” data really isn’t — and here’s why not;
• Tracker Attacks: Scholar references;
• Fundamental Law of Information Recovery [The Algorithmic Foundations of Differential Privacy];
• Renyi Differential Privacy;
• Differential Privacy: An Economic Method for Choosing Epsilon;
• Calibrating Noise to Sensitivity in Private Data Analysis;