A privacidade diferencial é um sistema para compartilhar publicamente informações sobre um conjunto de dados, descrevendo os padrões de grupos dentro do conjunto de dados e ao mesmo tempo reter informações sobre indivíduos no conjunto de dados. A ideia por trás da privacidade diferencial é que, se o efeito de fazer uma única substituição arbitrária no banco de dados for pequeno o suficiente, o resultado da consulta não poderá ser usado para inferir muito sobre um único indivíduo e, portanto, fornecerá privacidade. Outra maneira de descrever a privacidade diferencial é como uma restrição quanto aos algoritmos usados para publicar informações agregadas sobre um banco de dados estatísticos, que limita a divulgação de informações privadas de registros cujas informações estão no banco de dados. Por exemplo, algoritmos diferencialmente privados são usados por algumas agências governamentais para publicar informações demográficas ou outros agregados estatísticos, garantindo a confidencialidade das respostas da pesquisa, e por empresas para coletar informações sobre o comportamento do usuário enquanto controlam o que é visível até mesmo para analistas internos.
Em linhas gerais, um algoritmo é diferencialmente privado se um observador vendo sua saída não puder dizer se a informação de um indivíduo em particular foi usada na computação. A privacidade diferencial é frequentemente discutida no contexto da identificação de indivíduos cujas informações podem estar em um banco de dados. Embora não se refira diretamente a ataques de identificação e reidentificação, algoritmos diferencialmente privados provavelmente resistem a tais ataques.
A privacidade diferencial foi desenvolvida por criptógrafos e, como tal, é frequentemente associada à criptografia, e extrai muito de sua linguagem da criptografia.
História As organizações oficiais de estatísticas são encarregadas de coletar informações de indivíduos ou estabelecimentos e publicar dados agregados para atender ao interesse público. Por exemplo, o Censo dos Estados Unidos de 1790 coletou informações sobre indivíduos que vivem nos Estados Unidos e publicou tabulações com base em sexo, idade, raça e condição de servidão. As organizações estatísticas há muito coletam informações sob uma promessa de confidencialidade de que as informações fornecidas serão usadas para fins estatísticos, mas que as publicações não produzirão informações que possam ser rastreadas até um indivíduo ou estabelecimento específico. Para atingir esse objetivo, as organizações estatísticas há muito suprimem informações em suas publicações. Por exemplo, em uma tabela que apresenta as vendas de cada negócio em uma cidade agrupada por categoria de negócio, uma célula que contém informações de apenas uma empresa pode ser suprimida, para manter o sigilo das vendas específicas dessa empresa.
A adoção de sistemas eletrônicos de processamento de informações por agências estatísticas nas décadas de 1950 e 1960 aumentou drasticamente o número de tabelas que uma organização estatística poderia produzir e, ao fazê-lo, aumentou significativamente o potencial de divulgação indevida de informações confidenciais. Por exemplo, se uma empresa que teve seus números de vendas suprimidos também tiver esses números exibidos no total de vendas de uma região, talvez seja possível determinar o valor suprimido subtraindo as outras vendas desse total. Mas também pode haver combinações de adições e subtrações que podem fazer com que as informações privadas sejam reveladas. O número de combinações que precisam ser verificadas aumenta exponencialmente com o número de publicações e é potencialmente ilimitado se os usuários dos dados puderem fazer consultas ao banco de dados estatísticos usando um sistema de consulta interativo.
Em 1977, Tore Dalenius formalizou a matemática da supressão de células.
Em 1979, Dorothy Denning, Peter J. Denning e Mayer D. Schwartz formalizaram o conceito de Tracker, um adversário que poderia aprender o conteúdo confidencial de um banco de dados estatísticos criando uma série de consultas direcionadas e lembrando os resultados. Esta pesquisa e outras subsequentes mostraram que as propriedades de privacidade em um banco de dados só podem ser preservadas considerando cada nova consulta à luz de (possivelmente todas) as consultas anteriores. Essa linha de trabalho às vezes é chamada de privacidade de consulta, com o resultado final sendo que rastrear o impacto de uma consulta na privacidade de indivíduos no banco de dados era NP-difícil.
Em 2003, Kobbi Nissim e Irit Dinur demonstraram que é impossível publicar consultas arbitrárias em um banco de dados estatístico privado sem revelar alguma quantidade de informação privada, e que todo o conteúdo de informação do banco de dados pode ser revelado publicando os resultados de uma quantidade surpreendentemente pequena de consultas aleatórias - muito menos do que foi sugerido pelo trabalho anterior.Irit Dinur and Kobbi Nissim. 2003. Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS '03). ACM, New York, NY, USA, 202–210. O fenômeno geral é conhecido como a Lei Fundamental da Recuperação da Informação, e seu principal insight, ou seja, que no caso mais geral, a privacidade não pode ser protegida sem injetar alguma quantidade de ruído, levou ao desenvolvimento da privacidade diferencial.
Em 2006, Cynthia Dwork, Frank McSherry, Kobbi Nissim e Adam D. Smith publicaram um artigo formalizando a quantidade de ruído que precisava ser adicionado e propondo um mecanismo generalizado para fazê-lo. Seu trabalho foi co-recipiente do TCC Test-of-Time Award de 2016 e do Prêmio Gödel de 2017.
Desde então, pesquisas posteriores mostraram que existem muitas maneiras de produzir estatísticas muito precisas do banco de dados, garantindo altos níveis de privacidade.
Privacidade ε-diferencial O artigo de 2006 de Dwork, McSherry, Nissim e Smith introduziu o conceito de privacidade ε-diferencial, uma definição matemática para a perda de privacidade associada a qualquer liberação de dados extraída de um banco de dados estatísticos. (Aqui, o termo banco de dados estatísticos significa um conjunto de dados que são coletados sob o compromisso de confidencialidade com a finalidade de produzir estatísticas que, por sua produção, não comprometam a privacidade dos indivíduos que forneceram os dados.)
A intuição para a definição de privacidade ε-diferencial de 2006 é que a privacidade de uma pessoa não pode ser comprometida por uma divulgação estatística se seus dados não estiverem no banco de dados. Portanto, com privacidade diferencial, o objetivo é dar a cada indivíduo aproximadamente a mesma privacidade que resultaria da remoção de seus dados. Ou seja, as funções estatísticas executadas no banco de dados não devem depender excessivamente dos dados de qualquer indivíduo.
É claro que a contribuição de cada indivíduo para o resultado de uma consulta ao banco de dados depende em parte do número de pessoas cujos dados estão envolvidos na consulta. Se o banco de dados contém dados de uma única pessoa, os dados dessa pessoa contribuem com 100%. Se o banco de dados contém dados de cem pessoas, os dados de cada uma contribuem com apenas 1%. A principal percepção da privacidade diferencial é que, à medida que a consulta é feita nos dados de cada vez menos pessoas, mais ruído precisa ser adicionado ao resultado da consulta para produzir o mesmo nível de privacidade. Daí o nome do artigo de 2006, "Calibrating noise to sensitivity in private data analysis".
O artigo de 2006 apresenta tanto uma definição matemática de privacidade diferencial quanto um mecanismo baseado na adição de ruído de Laplace (ou seja, ruído proveniente da distribuição de Laplace) que satisfaz a definição.
Definição de privacidade ε-diferencial Seja ε um número real positivo e um algoritmo aleatório que recebe um conjunto de dados como entrada (representando as ações da parte confiável que detém os dados). Seja a imagem de . Diz-se que o algoritmo fornece -privacidade diferencial se, para todos os conjuntos de dados e que diferem em um único elemento (ou seja, os dados de uma pessoa), e todos os subconjuntos de :
onde a probabilidade é tomada sobre a aleatoriedade usada pelo algoritmo.
A privacidade diferencial oferece garantias fortes e robustas que facilitam o projeto modular e a análise de mecanismos diferencialmente privados devido à sua capacidade de composição, robustez ao pós-processamento e degradação graciosa na presença de dados correlacionados.
Componibilidade (Auto-)componibilidade refere-se ao fato de que a distribuição conjunta das saídas de mecanismos diferencialmente privados (possivelmente escolhidos de forma adaptativa) satisfaz a privacidade diferencial.
Composição sequencial. Se consultarmos um mecanismo de privacidade ε-diferencial vezes, e a randomização do mecanismo é independente para cada consulta, então o resultado seria -diferencialmente privado. No caso mais geral, se houver mecanismos independentes: , cujas garantias de privacidade são privacidade diferencial, respectivamente, então qualquer função deles: é -diferencialmente privada.
Composição paralela. Se os mecanismos anteriores são calculados em subconjuntos disjuntos do banco de dados privado, então a função seria -diferentemente privada em vez disso.
Robustez ao pós-processamento Para qualquer função determinística ou aleatória definida sobre a imagem do mecanismo , se satisfaz a privacidade ε-diferencial, o mesmo acontece com .
Em conjunto, a componibilidade e a robustez ao pós-processamento permitem a construção modular e a análise de mecanismos diferencialmente privados e motivam o conceito de orçamento de perda de privacidade. Se todos os elementos que acessam dados sensíveis de um mecanismo complexo são separadamente diferencialmente privados, sua combinação também será, seguida de pós-processamento arbitrário.
Privacidade do grupo Em geral, a privacidade ε-diferencial é projetada para proteger a privacidade entre bancos de dados vizinhos que diferem apenas em uma linha. Isso significa que nenhum adversário com informações auxiliares arbitrárias pode saber se um participante em particular enviou suas informações. No entanto, isso também pode ser estendido. Podemos querer proteger bancos de dados que diferem em linhas, o que equivale a considerar um adversário com informações auxiliares arbitrárias tentando saber se participantes em particular enviaram suas informações. Isso pode ser alcançado porque se itens mudam, a dilatação da probabilidade é limitada por ao invés de , ou seja, para D1 e D2 diferindo em itens:
Assim, utilizando ε em vez de atinge-se o resultado desejado (proteção de itens). Em outras palavras, em vez de ter cada item ε-diferencialmente privado protegido, agora cada grupo de itens são protegidos de forma ε-diferencialmente privada (e cada item é -diferencialmente privado protegido).
Mecanismos ε-diferencialmente privados Como a privacidade diferencial é um conceito probabilístico, qualquer mecanismo diferencialmente privado é necessariamente aleatório. Alguns deles, como o mecanismo de Laplace, descrito abaixo, dependem da adição de ruído controlado à função que queremos calcular. Outros, como o mecanismo exponencialF.McSherry and K.Talwar. Mechasim Design via Differential Privacy. Proceedings of the 48th Annual Symposium of Foundations of Computer Science, 2007. e a amostragem posteriorChristos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, Benjamin Rubinstein. Robust and Private Bayesian Inference. Algorithmic Learning Theory 2014 amostram de uma família de distribuições dependente do problema.
Sensibilidade Seja um número inteiro positivo, uma coleção de conjuntos de dados, e uma função. A sensibilidade de uma função, denotada , é definida por