Privacidade diferencial

Origem: Wikipédia, a enciclopédia livre.

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.[1]

A privacidade diferencial foi desenvolvida por criptógrafos e, como tal, é frequentemente associada à criptografia, e extrai muito de sua linguagem da criptografia.

História[editar | editar código-fonte]

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.[2]

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.[3] 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.[4] 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.[1] Seu trabalho foi co-recipiente do TCC Test-of-Time Award de 2016[5] e do Prêmio Gödel de 2017.[6]

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.[7][8]

Privacidade ε-diferencial[editar | editar código-fonte]

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[editar | editar código-fonte]

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.[9]

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[editar | editar código-fonte]

(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.[10]

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.[10]

Robustez ao pós-processamento[editar | editar código-fonte]

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[editar | editar código-fonte]

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 é extensível. Podemos querer proteger bancos de dados que diferem em linhas, o que equivale a um adversário com informações auxiliares arbitrárias que saberem 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 ,[11] ou seja, para D1 e D2 diferindo em items:

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[editar | editar código-fonte]

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 exponencial[12] e a amostragem posterior[13] amostram de uma família de distribuições dependente do problema.

Sensibilidade[editar | editar código-fonte]

Seja um número inteiro positivo, uma coleção de conjuntos de dados, e uma função. A sensibilidade[1] de uma função, denotada , é definida por

em que o máximo é sobre todos os pares de conjuntos de dados e em diferindo em no máximo um elemento e denota a norma .

No exemplo do banco de dados médico abaixo, se considerarmos que é a função , então a sensibilidade da função é um, pois a alteração de uma entrada qualquer no banco de dados faz com que a saída da função seja alterada ou em zero ou em um.

Existem técnicas (que são descritas abaixo) com as quais podemos criar um algoritmo diferencialmente privado para funções com baixa sensibilidade.

O mecanismo de Laplace[editar | editar código-fonte]

O mecanismo de Laplace adiciona ruído de Laplace (ou seja, ruído da distribuição de Laplace, que pode ser expresso pela função de densidade de probabilidade , que tem média zero e desvio padrão ). Agora, no nosso caso, definimos a função de saída de como uma função a valores reais (chamada de saída de transcrição por ) como , em que e é a consulta/função de valor real original que planejamos executar no banco de dados. Agora claramente pode ser considerada uma variável aleatória contínua, onde

que é no máximo . Podemos considerar como sendo o fator de privacidade . Desta forma, segue um mecanismo diferencialmente privado (como pode ser visto na definição acima). Se tentarmos usar esse conceito em nosso exemplo de diabetes, segue-se do fato derivado acima que, para ter como o algoritmo -diferencialmente privado, precisamos ter . Embora tenhamos usado o ruído de Laplace aqui, outras formas de ruído, como o ruído gaussiano, podem ser empregadas, mas podem exigir um leve relaxamento da definição de privacidade diferencial.[11]

De acordo com essa definição, a privacidade diferencial é uma condição do mecanismo de liberação (ou seja, a parte confiável que libera informações sobre o conjunto de dados) e não do conjunto de dados em si. Intuitivamente, isso significa que, para quaisquer dois conjuntos de dados semelhantes, um determinado algoritmo diferencialmente privado se comportará aproximadamente da mesma forma em ambos os conjuntos de dados. A definição dá uma forte garantia de que a presença ou ausência de um indivíduo não afetará significativamente a saída final do algoritmo.

Por exemplo, suponha que temos um banco de dados de registros médicos no qual cada registro é um par (Nome, X), em que é um booleano que indica se uma pessoa tem diabetes ou não. Por exemplo:

Nome Tem Diabetes (X)
Ross 1
Mônica 1
Joey 0
Febe 0
Chandler 1
Rachel 0

Agora suponha que um usuário mal-intencionado (geralmente chamado de adversário ) queira descobrir se Chandler tem diabetes ou não. Suponha que ele também saiba em qual linha do banco de dados Chandler reside. Agora suponha que o adversário só tenha permissão para usar uma forma específica de consulta que retorna a soma parcial do primeiro linhas de coluna no banco de dados. Para descobrir o status de diabetes de Chandler, o adversário executa e , então calcula sua diferença. Neste exemplo, e , então sua diferença é 1. Isso indica que o campo "Tem Diabetes" na linha de Chandler deve ser 1. Este exemplo destaca como as informações individuais podem ser comprometidas mesmo sem consultar explicitamente as informações de um indivíduo específico.

Continuando este exemplo, se construirmos substituindo (Chandler, 1) por (Chandler, 0), então esse adversário malicioso será capaz de distinguir de calculando para cada conjunto de dados. Se o adversário fosse obrigado a receber os valores através de um algoritmo -diferencialmente privado, então para um suficientemente pequeno, ele não poderia distinguir entre os dois conjuntos de dados.

Resposta aleatória[editar | editar código-fonte]

Um exemplo simples, especialmente desenvolvido nas ciências sociais,[14] é pedir a uma pessoa que responda à pergunta "Você possui o atributo A ?", de acordo com o seguinte procedimento:

  1. Jogue uma moeda.
  2. Se der cara, jogue a moeda novamente (ignorando o resultado) e responda à pergunta honestamente.
  3. Se der coroa, jogue a moeda novamente e responda "Sim" se der cara, e "Não" se der coroa.

(O lançamento extra aparentemente redundante no primeiro caso é necessário em situações em que apenas o ato de jogar uma moeda pode ser observado por outros, mesmo que o resultado real permaneça oculto.) A confidencialidade surge então da refutabilidade das respostas individuais.

Mas, no geral, esses dados com muitas respostas são significativos, pois respostas positivas são dadas a um quarto por pessoas que não possuem o atributo A e três quartos por pessoas que realmente o possuem. Assim, se p é a verdadeira proporção de pessoas com A, então esperamos obter (1/4)(1-p) + (3/4)p = (1/4) + p/2 respostas positivas. Portanto, é possível estimar p.

Em particular, se o atributo A é sinônimo de comportamento ilegal, então responder “Sim” não é incriminador, na medida em que a pessoa tem probabilidade de resposta “Sim”, seja ela qual for.

Embora este exemplo, inspirado pela resposta aleatória, possa ser aplicável a microdados (ou seja, liberar conjuntos de dados com cada resposta individual), por definição a privacidade diferencial exclui liberações de microdados e é aplicável apenas a consultas (ou seja, a agregação de respostas individuais em um resultado), pois isso violaria os requisitos, mais especificamente a negação plausível de que um sujeito participou ou não.[15][16]

Transformações estáveis[editar | editar código-fonte]

Uma transformação é -estável se a distância de Hamming entre e é no máximo -vezes a distância de Hamming entre e para quaisquer dois bancos de dados . O Theorem 2 de[10] afirma que se existe um mecanismo que é -diferentemente privado, então o mecanismo composto é -diferencialmente privado.

Isso pode ser generalizado para a privacidade do grupo, pois o tamanho do grupo pode ser pensado como a distância de Hamming entre e (Onde contém o grupo e não). Nesse caso é -diferencialmente privado.

Outras noções de privacidade diferencial[editar | editar código-fonte]

Como a privacidade diferencial é considerada muito forte ou fraca para algumas aplicações, muitas versões dela foram propostas.[17] O relaxamento mais difundido é (ε, δ)-privacidade diferencial,[18] que enfraquece a definição ao permitir uma pequena densidade de probabilidade δ adicional na qual o limite superior ε não se aplica.

Adoção de privacidade diferencial em aplicações do mundo real[editar | editar código-fonte]

Vários usos de privacidade diferencial na prática são conhecidos até o momento:

Considerações de propósito público[editar | editar código-fonte]

Existem várias considerações de propósito público em relação à privacidade diferencial que são importantes de serem consideradas, especialmente para formuladores de políticas e públicos focados em políticas interessados nas oportunidades e riscos sociais da tecnologia:[27]

  • Utilidade e precisão de dados. A principal preocupação com a privacidade diferencial é o conflito entre a utilidade dos dados e a privacidade individual. Se o parâmetro de perda de privacidade estiver definido para favorecer a utilidade, os benefícios de privacidade são reduzidos (menos “ruído” é injetado no sistema); se o parâmetro de perda de privacidade for definido para favorecer uma maior privacidade, a precisão e a utilidade do conjunto de dados são reduzidas (mais “ruído” é injetado no sistema). É importante que os formuladores de políticas considerem os compromissos impostos pela privacidade diferencial para ajudar a definir as melhores práticas e padrões apropriados em torno do uso dessa prática de preservação de privacidade, especialmente considerando a diversidade de casos de uso organizacional. Vale a pena notar, porém, que a diminuição da precisão e utilidade é um problema comum a todos os métodos de limitação de divulgação estatística e não é exclusivo da privacidade diferencial. O que é único, no entanto, é como os formuladores de políticas, pesquisadores e implementadores podem considerar a mitigação dos riscos apresentados por meio dessa compensação.
  • Privacidade e segurança de dados. A privacidade diferencial fornece uma medida quantificada da perda de privacidade e um limite superior e permite que os curadores escolham um compromisso explícito entre privacidade e precisão. É robusto a ataques de privacidade ainda desconhecidos. No entanto, incentiva um maior compartilhamento de dados, que, se mal feito, aumenta o risco de privacidade. A privacidade diferencial implica que a privacidade seja protegida, mas isso depende muito do parâmetro de perda de privacidade escolhido e pode levar a uma falsa sensação de segurança. Por fim, embora seja robusto contra futuros ataques de privacidade imprevistos, uma contra-medida pode ser criada que não podemos prever.

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. a b c Calibrating Noise to Sensitivity in Private Data Analysis by Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. In Theory of Cryptography Conference (TCC), Springer, 2006. doi:10.1007/11681878_14. The full version appears in Journal of Privacy and Confidentiality, 7 (3), 17-51. doi:10.29012/jpc.v7i3.405
  2. Dalenius, Tore (1977). «Towards a methodology for statistical disclosure control» (PDF). Statistik Tidskrift. 15 
  3. Dorothy E. Denning; Peter J. Denning; Mayer D. Schwartz (março de 1978). «The Tracker: A Threat to Statistical Database Security» (PDF). 4 (1): 76–96 
  4. 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. doi:10.1145/773153.773173
  5. «TCC Test-of-Time Award» 
  6. «2017 Gödel Prize» 
  7. Hilton, Michael. «Differential Privacy: A Historical Survey» 
  8. Dwork, Cynthia (25 de abril de 2008). «Differential Privacy: A Survey of Results». In: Agrawal, Angsheng; Du; Duan; Li. Theory and Applications of Models of Computation. Col: Lecture Notes in Computer Science (em inglês). 4978. [S.l.]: Springer Berlin Heidelberg. pp. 1–19. ISBN 9783540792277. doi:10.1007/978-3-540-79228-4_1 
  9. The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth. Foundations and Trends in Theoretical Computer Science. Vol. 9, no. 3–4, pp. 211‐407, Aug. 2014. doi:10.1561/0400000042
  10. a b c Privacy integrated queries: an extensible platform for privacy-preserving data analysis by Frank D. McSherry. In Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD), 2009. doi:10.1145/1559845.1559850
  11. a b Differential Privacy by Cynthia Dwork, International Colloquium on Automata, Languages and Programming (ICALP) 2006, p. 1–12. doi:10.1007/11787006_1
  12. F.McSherry and K.Talwar. Mechasim Design via Differential Privacy. Proceedings of the 48th Annual Symposium of Foundations of Computer Science, 2007.
  13. Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, Benjamin Rubinstein. Robust and Private Bayesian Inference. Algorithmic Learning Theory 2014
  14. Warner, S. L. (março de 1965). «Randomised response: a survey technique for eliminating evasive answer bias». Taylor & Francis. Journal of the American Statistical Association. 60 (309): 63–69. JSTOR 2283137. PMID 12261830. doi:10.1080/01621459.1965.10480775 
  15. Dwork, Cynthia. "A firm foundation for private data analysis." Communications of the ACM 54.1 (2011): 86–95, supra note 19, page 91.
  16. Bambauer, Jane, Krishnamurty Muralidhar, and Rathindra Sarathy. "Fool's gold: an illustrated critique of differential privacy." Vand. J. Ent. & Tech. L. 16 (2013): 701.
  17. SoK: Differential Privacies by Damien Desfontaines, Balázs Pejó. 2019.
  18. Dwork, Cynthia, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. "Our data, ourselves: Privacy via distributed noise generation." In Advances in Cryptology-EUROCRYPT 2006, pp. 486–503. Springer Berlin Heidelberg, 2006.
  19. Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, and Lars Vilhuber. "Privacy: Theory meets Practice on the Map". In Proceedings of the 24th International Conference on Data Engineering, ICDE) 2008.
  20. Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response". In Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS), 2014. doi:10.1145/2660267.2660348
  21. google/rappor, GitHub, 15 de julho de 2021 
  22. Tackling Urban Mobility with Technology by Andrew Eland. Google Policy Europe Blog, Nov 18, 2015.
  23. «Apple - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever». Apple. Consultado em 16 de junho de 2016 
  24. Collecting telemetry data privately by Bolin Ding, Jana Kulkarni, Sergey Yekhanin. NIPS 2017.
  25. «Privitar Lens». Consultado em 20 de fevereiro de 2018 
  26. LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale by Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, Parvez Ahammad. arXiv:2002.05839.
  27. «Technology Factsheet: Differential Privacy». Belfer Center for Science and International Affairs (em inglês). Consultado em 12 de abril de 2021 

Leitura adicional[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]