Privacidade diferencial: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
Criada por tradução da página "Differential privacy"
 
Ajustes nas referências da tradução; traduzindo nome/parâmetro nas citações, outros ajustes usando script
Linha 2: Linha 2:
A '''privacidade diferencial''' ('''DP''') é 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.
A '''privacidade diferencial''' ('''DP''') é 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.
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.<ref name="DMNS06" />


A privacidade diferencial foi desenvolvida por criptógrafos e, como tal, é frequentemente associada à criptografia, e extrai muito de sua linguagem da criptografia.
A privacidade diferencial foi desenvolvida por criptógrafos e, como tal, é frequentemente associada à criptografia, e extrai muito de sua linguagem da criptografia.
Linha 11: Linha 11:
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.
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.<ref>{{Citar periódico |url=https://archives.vrdc.cornell.edu/info7470/2011/Readings/dalenius-1977.pdf |titulo=Towards a methodology for statistical disclosure control |ultimo=Dalenius |primeiro=Tore |ano=1977 |volume=15 |journal=Statistik Tidskrift}}</ref>
Em 1977, Tore Dalenius formalizou a matemática da supressão de células.<ref>{{Citar periódico |url=https://archives.vrdc.cornell.edu/info7470/2011/Readings/dalenius-1977.pdf |titulo=Towards a methodology for statistical disclosure control |ultimo=Dalenius |primeiro=Tore |ano=1977 |volume=15 |periódico=Statistik Tidskrift}}</ref>


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.<ref>{{Citar periódico |url=http://www.dbis.informatik.hu-berlin.de/fileadmin/lectures/SS2011/VL_Privacy/Tracker1.pdf |titulo=The Tracker: A Threat to Statistical Database Security |data=March 1978 |número=1 |ultimo=Dorothy E. Denning |ultimo2=Peter J. Denning |paginas=76–96 |ultimo3=Mayer D. Schwartz |volume=4}}</ref> 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 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.<ref>{{Citar periódico |url=http://www.dbis.informatik.hu-berlin.de/fileadmin/lectures/SS2011/VL_Privacy/Tracker1.pdf |titulo=The Tracker: A Threat to Statistical Database Security |data=março de 1978 |número=1 |ultimo=Dorothy E. Denning |ultimo2=Peter J. Denning |paginas=76–96 |ultimo3=Mayer D. Schwartz |volume=4}}</ref> 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.<ref>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}}</ref> 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 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.<ref>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}}</ref> 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<ref>{{Citar web|url=https://www.iacr.org/workshops/tcc/awards.html|titulo=TCC Test-of-Time Award}}</ref> e do [[Prêmio Gödel|Prêmio Gödel de]] 2017.<ref>{{Citar web|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|titulo=2017 Gödel Prize}}</ref>
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.<ref name="DMNS06" /> Seu trabalho foi co-recipiente do ''TCC Test-of-Time Award'' de 2016<ref>{{Citar web|url=https://www.iacr.org/workshops/tcc/awards.html|titulo=TCC Test-of-Time Award}}</ref> e do [[Prêmio Gödel]] de 2017.<ref>{{Citar web|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|titulo=2017 Gödel Prize}}</ref>


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.<ref>{{Citar periódico |titulo=Differential Privacy: A Historical Survey |ultimo=Hilton |primeiro=Michael}}</ref><ref>{{Citar livro|título=Theory and Applications of Models of Computation|ultimo=Dwork|primeiro=Cynthia|data=2008-04-25|editora=Springer Berlin Heidelberg|editor-sobrenome=Agrawal|editor-nome1=Angsheng|series=Lecture Notes in Computer Science|volume=4978|páginas=1–19|língua=en|capitulo=Differential Privacy: A Survey of Results|doi=10.1007/978-3-540-79228-4_1|isbn=9783540792277|editor-sobrenome2=Du|editor-sobrenome3=Duan|editor-sobrenome4=Li}}</ref>
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.<ref>{{Citar periódico |titulo=Differential Privacy: A Historical Survey |ultimo=Hilton |primeiro=Michael}}</ref><ref>{{Citar livro|título=Theory and Applications of Models of Computation|ultimo=Dwork|primeiro=Cynthia|data=2008-04-25|editora=Springer Berlin Heidelberg|editor-sobrenome=Agrawal|editor-nome1=Angsheng|series=Lecture Notes in Computer Science|volume=4978|páginas=1–19|língua=en|capitulo=Differential Privacy: A Survey of Results|doi=10.1007/978-3-540-79228-4_1|isbn=9783540792277|editor-sobrenome2=Du|editor-sobrenome3=Duan|editor-sobrenome4=Li}}</ref>
Linha 31: Linha 31:


=== Definição de privacidade ε-diferencial ===
=== Definição de privacidade ε-diferencial ===
Seja ε um [[número real]] positivo e <math>\mathcal{A}</math> um [[Algoritmo probabilístico|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 <math>\textrm{im}\ \mathcal{A}</math> a [[Conjunto imagem|imagem]] de <math>\mathcal{A}</math>. Diz-se que o algoritmo <math>\mathcal{A}</math> fornece <math>\varepsilon</math>-privacidade diferencial se, para todos os conjuntos de dados <math>D_1</math> e <math>D_2</math> que diferem em um único elemento (ou seja, os dados de uma pessoa), e todos os subconjuntos <math>S</math> de <math>\textrm{im}\ \mathcal{A}</math>:<center>
Seja ε um [[número real]] positivo e <math>\mathcal{A}</math> um [[Algoritmo probabilístico|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 <math>\textrm{im}\ \mathcal{A}</math> a [[Conjunto imagem|imagem]] de <math>\mathcal{A}</math>. Diz-se que o algoritmo <math>\mathcal{A}</math> fornece <math>\varepsilon</math>-privacidade diferencial se, para todos os conjuntos de dados <math>D_1</math> e <math>D_2</math> que diferem em um único elemento (ou seja, os dados de uma pessoa), e todos os subconjuntos <math>S</math> de <math>\textrm{im}\ \mathcal{A}</math>:

<math>\Pr[\mathcal{A}(D_1) \in S] \leq \exp\left(\varepsilon\right) \cdot \Pr[\mathcal{A}(D_2) \in S],</math>
<math display="block">\Pr[\mathcal{A}(D_1) \in S] \leq \exp\left(\varepsilon\right) \cdot \Pr[\mathcal{A}(D_2) \in S],</math>
</center>onde a probabilidade é tomada sobre a [[aleatoriedade]] usada pelo algoritmo.

onde a probabilidade é tomada sobre a [[aleatoriedade]] usada pelo algoritmo.<ref name="DPBook"/>


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.
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.
Linha 40: Linha 42:
(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.
(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 <math>t</math> vezes, e a randomização do mecanismo é independente para cada consulta, então o resultado seria <math>\varepsilon t</math>-diferencialmente privado. No caso mais geral, se houver <math>n</math> mecanismos independentes: <math>\mathcal{M}_1,\dots,\mathcal{M}_n</math>, cujas garantias de privacidade são <math>\varepsilon_1,\dots,\varepsilon_n</math> privacidade diferencial, respectivamente, então qualquer função <math>g</math> deles: <math>g(\mathcal{M}_1,\dots,\mathcal{M}_n)</math> é <math>\left(\sum\limits_{i=1}^{n} \varepsilon_i\right)</math>-diferencialmente privada.
'''Composição sequencial.''' Se consultarmos um mecanismo de privacidade ε-diferencial <math>t</math> vezes, e a randomização do mecanismo é independente para cada consulta, então o resultado seria <math>\varepsilon t</math>-diferencialmente privado. No caso mais geral, se houver <math>n</math> mecanismos independentes: <math>\mathcal{M}_1,\dots,\mathcal{M}_n</math>, cujas garantias de privacidade são <math>\varepsilon_1,\dots,\varepsilon_n</math> privacidade diferencial, respectivamente, então qualquer função <math>g</math> deles: <math>g(\mathcal{M}_1,\dots,\mathcal{M}_n)</math> é <math>\left(\sum\limits_{i=1}^{n} \varepsilon_i\right)</math>-diferencialmente privada.<ref name="PINQ" />


'''Composição paralela.''' Se os mecanismos anteriores são calculados em subconjuntos ''disjuntos'' do banco de dados privado, então a função <math>g</math> seria <math>(\max_i \varepsilon_i)</math>-diferentemente privada em vez disso.
'''Composição paralela.''' Se os mecanismos anteriores são calculados em subconjuntos ''disjuntos'' do banco de dados privado, então a função <math>g</math> seria <math>(\max_i \varepsilon_i)</math>-diferentemente privada em vez disso.<ref name="PINQ" />


=== Robustez ao pós-processamento ===
=== Robustez ao pós-processamento ===
Linha 50: Linha 52:


=== Privacidade do grupo ===
=== 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 é extensível. Podemos querer proteger bancos de dados que diferem em <math>c</math> linhas, o que equivale a um adversário com informações auxiliares arbitrárias que saberem se '''<math>c</math>''' participantes em particular enviaram suas informações. Isso pode ser alcançado porque se <math>c</math> itens mudam, a dilatação da probabilidade é limitada por <math>\exp ( \varepsilon c )</math> ao invés de <math>\exp ( \varepsilon )</math>, ou seja, para D<sub>1</sub> e D<sub>2</sub> diferindo em <math>c</math> items:
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 <math>c</math> linhas, o que equivale a um adversário com informações auxiliares arbitrárias que saberem se '''<math>c</math>''' participantes em particular enviaram suas informações. Isso pode ser alcançado porque se <math>c</math> itens mudam, a dilatação da probabilidade é limitada por <math>\exp ( \varepsilon c )</math> ao invés de <math>\exp ( \varepsilon )</math>,<ref name="Dwork, ICALP 2006" /> ou seja, para D<sub>1</sub> e D<sub>2</sub> diferindo em <math>c</math> items:


: <math>\Pr[\mathcal{A}(D_{1})\in S]\leq
: <math>\Pr[\mathcal{A}(D_{1})\in S]\leq
Linha 61: Linha 63:


=== Sensibilidade ===
=== Sensibilidade ===
Seja <math>d</math> um número inteiro positivo, <math>\mathcal{D}</math> uma coleção de conjuntos de dados, e <math>f \colon \mathcal{D} \rightarrow \mathbb{R}^d</math> uma função. A ''sensibilidade'' de uma função, denotada <math>\Delta f</math>, é definida por
Seja <math>d</math> um número inteiro positivo, <math>\mathcal{D}</math> uma coleção de conjuntos de dados, e <math>f \colon \mathcal{D} \rightarrow \mathbb{R}^d</math> uma função. A ''sensibilidade''<ref name="DMNS06"/> de uma função, denotada <math>\Delta f</math>, é definida por


: <math>\Delta f=\max \lVert f(D_1)-f(D_2) \rVert_1,</math>
: <math>\Delta f=\max \lVert f(D_1)-f(D_2) \rVert_1,</math>
Linha 77: Linha 79:




que é no máximo <math>e^{\frac{|f(D_{1})-f(D_{2})|}{\lambda}}\leq e^{\frac{\Delta(f)}{\lambda}}\,\!</math>. Podemos considerar <math>\frac{\Delta(f)}{\lambda}\,\!</math> como sendo o fator de privacidade <math>\varepsilon\,\!</math>. Desta forma, <math>\mathcal{T}\,\!</math> 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 <math>\mathcal{A}\,\!</math> como o algoritmo <math>\varepsilon\,\!</math>-diferencialmente privado, precisamos ter <math>\lambda=1/\varepsilon\,\!</math>. 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.
que é no máximo <math>e^{\frac{|f(D_{1})-f(D_{2})|}{\lambda}}\leq e^{\frac{\Delta(f)}{\lambda}}\,\!</math>. Podemos considerar <math>\frac{\Delta(f)}{\lambda}\,\!</math> como sendo o fator de privacidade <math>\varepsilon\,\!</math>. Desta forma, <math>\mathcal{T}\,\!</math> 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 <math>\mathcal{A}\,\!</math> como o algoritmo <math>\varepsilon\,\!</math>-diferencialmente privado, precisamos ter <math>\lambda=1/\varepsilon\,\!</math>. 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.<ref name="Dwork, ICALP 2006" />


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.
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.
Linha 109: Linha 111:


=== Resposta aleatória ===
=== Resposta aleatória ===
Um exemplo simples, especialmente desenvolvido nas [[ciências sociais]],<ref>{{Citar periódico |titulo=Randomised response: a survey technique for eliminating evasive answer bias |data=March 1965 |publicado=[[Taylor & Francis]] |número=309 |ultimo=Warner |primeiro=S. L. |paginas=63–69 |doi=10.1080/01621459.1965.10480775 |jstor=2283137 |pmid=12261830 |volume=60 |journal=[[Journal of the American Statistical Association]]}}</ref> é pedir a uma pessoa que responda à pergunta "Você possui o ''atributo A'' ?", de acordo com o seguinte procedimento:
Um exemplo simples, especialmente desenvolvido nas [[ciências sociais]],<ref>{{Citar periódico |titulo=Randomised response: a survey technique for eliminating evasive answer bias |data=março de 1965 |publicado=[[Taylor & Francis]] |número=309 |ultimo=Warner |primeiro=S. L. |paginas=63–69 |doi=10.1080/01621459.1965.10480775 |jstor=2283137 |pmid=12261830 |volume=60 |periódico=[[Journal of the American Statistical Association]]}}</ref> é pedir a uma pessoa que responda à pergunta "Você possui o ''atributo A'' ?", de acordo com o seguinte procedimento:


# [[Cara ou coroa|Jogue uma moeda]].
# [[Cara ou coroa|Jogue uma moeda]].
Linha 124: Linha 126:


=== Transformações estáveis ===
=== Transformações estáveis ===
Uma transformação <math>T</math> é <math>c</math>-estável se a [[distância de Hamming]] entre <math>T(A)</math> e <math>T(B)</math> é no máximo <math>c</math>-vezes a distância de Hamming entre <math>A</math> e <math>B</math> para quaisquer dois bancos de dados <math>A,B</math>. O Teorema 2 em afirma que se existe um mecanismo <math>M</math> que é <math>\varepsilon</math>-diferentemente privado, então o mecanismo composto <math>M\circ T</math> é <math>(\varepsilon \times c)</math>-diferencialmente privado.
Uma transformação <math>T</math> é <math>c</math>-estável se a [[distância de Hamming]] entre <math>T(A)</math> e <math>T(B)</math> é no máximo <math>c</math>-vezes a distância de Hamming entre <math>A</math> e <math>B</math> para quaisquer dois bancos de dados <math>A,B</math>. O ''Theorem 2'' de<ref name="PINQ"/> afirma que se existe um mecanismo <math>M</math> que é <math>\varepsilon</math>-diferentemente privado, então o mecanismo composto <math>M\circ T</math> é <math>(\varepsilon \times c)</math>-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 <math>h</math> entre <math>A</math> e <math>B</math> (Onde <math>A</math> contém o grupo e <math>B</math> não). Nesse caso <math>M\circ T</math> é <math>(\varepsilon \times c \times h)</math>-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 <math>h</math> entre <math>A</math> e <math>B</math> (Onde <math>A</math> contém o grupo e <math>B</math> não). Nesse caso <math>M\circ T</math> é <math>(\varepsilon \times c \times h)</math>-diferencialmente privado.


== <span lang="ru" dir="ltr">Outras</span> noções de privacidade diferencial ==
== Outras noções de privacidade diferencial ==
Como a privacidade diferencial é considerada muito forte ou fraca para algumas aplicações, muitas versões dela foram propostas. O relaxamento mais difundido é (ε, δ)-privacidade diferencial, que enfraquece a definição ao permitir uma pequena densidade de probabilidade δ adicional na qual o limite superior ε não se aplica.
Como a privacidade diferencial é considerada muito forte ou fraca para algumas aplicações, muitas versões dela foram propostas.<ref name="DP19"/> O relaxamento mais difundido é (ε, δ)-privacidade diferencial,<ref name="DKMMN06"/> 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 ==
== Adoção de privacidade diferencial em aplicações do mundo real ==
Vários usos de privacidade diferencial na prática são conhecidos até o momento:
Vários usos de privacidade diferencial na prática são conhecidos até o momento:


* 2008: [[Departamento do Censo dos Estados Unidos]], para mostrar padrões de deslocamento.
* 2008: [[Departamento do Censo dos Estados Unidos]], para mostrar padrões de deslocamento.<ref name="MachanavajjhalaKAGV08"/>
* 2014: RAPPORT do [[Google]], para telemetria, como aprender estatísticas sobre softwares indesejados que sequestram as configurações dos usuários. <ref>{{Citation|title=google/rappor|date=2021-07-15|url=https://github.com/google/rappor|publisher=GitHub}}</ref>
* 2014: RAPPORT do [[Google]], para telemetria, como aprender estatísticas sobre softwares indesejados que sequestram as configurações dos usuários.<ref name="RAPPOR"/><ref>{{Citation|título=google/rappor|data=2021-07-15|url=https://github.com/google/rappor|publicado=GitHub}}</ref>
* 2015: Google, para compartilhar estatísticas históricas de tráfego.
* 2015: Google, para compartilhar estatísticas históricas de tráfego.<ref name="Eland"/>
* 2016: A [[Apple|<span lang="es" dir="ltr">Apple</span>]] anunciou sua intenção de usar privacidade diferencial no [[iOS 10]] para melhorar sua tecnologia de [[Assistente virtual inteligente|assistente pessoal inteligente]].<ref name=":0">{{Citar web|url=https://www.apple.com/pr/library/2016/06/13Apple-Previews-iOS-10-The-Biggest-iOS-Release-Ever.html|titulo=Apple - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever|acessodata=16 June 2016|website=Apple}}</ref>
* 2016: A [[Apple|<span lang="es" dir="ltr">Apple</span>]] anunciou sua intenção de usar privacidade diferencial no [[iOS 10]] para melhorar sua tecnologia de [[Assistente virtual inteligente|assistente pessoal inteligente]].<ref name=":0">{{Citar web|url=https://www.apple.com/pr/library/2016/06/13Apple-Previews-iOS-10-The-Biggest-iOS-Release-Ever.html|titulo=Apple - Press Info - Apple Previews iOS 10, the Biggest iOS Release Ever|acessodata=16 de junho de 2016|website=Apple}}</ref>
* 2017: Microsoft, para telemetria no Windows.
* 2017: Microsoft, para telemetria no Windows.<ref name="DpWinTelemetry"/>
* 2019: Privitar Lens é uma API que usa privacidade diferencial.<ref>{{Citar web|url=https://www.privitar.com/privitar-lens|titulo=Privitar Lens|acessodata=20 February 2018}}</ref>
* 2019: Privitar Lens é uma API que usa privacidade diferencial.<ref>{{Citar web|url=https://www.privitar.com/privitar-lens|titulo=Privitar Lens|acessodata=20 de fevereiro de 2018}}</ref>
* 2020: LinkedIn, para consultas de anunciantes.
* 2020: LinkedIn, para consultas de anunciantes.<ref name="DpLinkedIn"/>


== Considerações de propósito público ==
== Considerações de propósito público ==
Linha 150: Linha 152:
== Ver também ==
== Ver também ==


* Quase-identificador
* [[Quase-identificador]]
* Mecanismo exponencial (privacidade diferencial) - uma técnica para projetar algoritmos diferencialmente privados
* [[Mecanismo exponencial (privacidade diferencial)]] - uma técnica para projetar algoritmos diferencialmente privados
* k-anonimato
* [[k-anonimato]]
* Análise diferencialmente privada de gráfos
* [[Análise diferencialmente privada de gráfos]]
* Informações de saúde protegidas
* [[Informações de saúde protegidas]]
* Privacidade diferencial local
* [[Privacidade diferencial local]]


== Referências ==
== Referências ==
<references group="" responsive="1">
<references group="" responsive="1">


<ref name="DKMMN06">
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.</ref>

<!-- unused refs<ref name="CABP13">
Chatzikokolakis, Konstantinos, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. "Broadening the scope of Differential Privacy using metrics." In Privacy Enhancing Technologies, pp. 82–102. Springer Berlin Heidelberg, 2013.</ref>

<ref name="HRW11">
Hall, Rob, Alessandro Rinaldo, and Larry Wasserman. "Random differential privacy." arXiv preprint arXiv:1112.2680 (2011).</ref>-->


<ref name="MachanavajjhalaKAGV08">
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.</ref>


<ref name="RAPPOR">
Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. [https://dl.acm.org/doi/10.1145/2660267.2660348 "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}}</ref>


<ref name="DMNS06">
[https://link.springer.com/chapter/10.1007%2F11681878_14 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 [https://journalprivacyconfidentiality.org/index.php/jpc/article/view/405 full version] appears in Journal of Privacy and Confidentiality, 7 (3), 17-51. {{doi|10.29012/jpc.v7i3.405}}</ref>


<ref name="PINQ">
[http://research.microsoft.com/pubs/80218/sigmod115-mcsherry.pdf 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}}</ref>


<ref name="Dwork, ICALP 2006">
[http://research.microsoft.com/pubs/64346/dwork.pdf Differential Privacy] by Cynthia Dwork, International Colloquium on Automata, Languages and Programming (ICALP) 2006, p.&nbsp;1–12. {{doi|10.1007/11787006_1}}</ref>


<ref name="DPBook">
[http://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf 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.&nbsp;211‐407, Aug. 2014. {{doi|10.1561/0400000042}}</ref>


<ref name="Eland">[https://europe.googleblog.com/2015/11/tackling-urban-mobility-with-technology.html Tackling Urban Mobility with Technology] by Andrew Eland. Google Policy Europe Blog, Nov 18, 2015.</ref>


<ref name="DpWinTelemetry">[https://www.microsoft.com/en-us/research/publication/collecting-telemetry-data-privately/ Collecting telemetry data privately] by Bolin Ding, Jana Kulkarni, Sergey Yekhanin. NIPS 2017.</ref>


<ref name="DpLinkedIn">[https://arxiv.org/abs/2002.05839 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.</ref>


<ref name="DP19">[https://arxiv.org/abs/1906.01337 SoK: Differential Privacies] by Damien Desfontaines, Balázs Pejó. 2019.</ref>
</references>
</references>


Linha 186: Linha 212:
* Erlingsson, Úlfar, Vasyl Pihur e Aleksandra Korolova. 2014. RAPPO: Resposta Ordinal de Preservação de Privacidade Agregada Aleatória. In Actas da Conferência ACM SIGSAC 2014 sobre Segurança Informática e das Comunicações (CCS '14). ACM, Nova York, NY, EUA, 1054-1067. {{DOI|10.1145/2660267.2660348}} .
* Erlingsson, Úlfar, Vasyl Pihur e Aleksandra Korolova. 2014. RAPPO: Resposta Ordinal de Preservação de Privacidade Agregada Aleatória. In Actas da Conferência ACM SIGSAC 2014 sobre Segurança Informática e das Comunicações (CCS '14). ACM, Nova York, NY, EUA, 1054-1067. {{DOI|10.1145/2660267.2660348}} .
* Abowd, John M. e Ian M. Schmutte. 2017. Revisitando a economia da privacidade: Estatísticas populacionais e proteção da confidencialidade como bens públicos. Labor Dynamics Institute, Cornell University, Labor Dynamics Institute, Cornell University, em https://digitalcommons.ilr.cornell.edu/ldi/37/
* Abowd, John M. e Ian M. Schmutte. 2017. Revisitando a economia da privacidade: Estatísticas populacionais e proteção da confidencialidade como bens públicos. Labor Dynamics Institute, Cornell University, Labor Dynamics Institute, Cornell University, em https://digitalcommons.ilr.cornell.edu/ldi/37/
* Abowd, John M. e Ian M. Schmutte. Próximo. Uma Análise Econômica da Proteção da Privacidade e Precisão Estatística como Escolhas Sociais. American Economic Review, {{Arxiv|1808.06303}}
* Abowd, John M. e Ian M. Schmutte. Próximo. Uma Análise Econômica da Proteção da Privacidade e Precisão Estatística como Escolhas Sociais. American Economic Review, {{Arxiv|1808.06303}}
* Apple, Inc. 2016. A Apple apresenta o iOS 10, o maior lançamento de iOS de todos os tempos. Comunicado de imprensa (13 de junho). https://www.apple.com/newsroom/2016/06/apple-previews-ios-10-biggest-ios-release-ever.html .
* Apple, Inc. 2016. A Apple apresenta o iOS 10, o maior lançamento de iOS de todos os tempos. Comunicado de imprensa (13 de junho). https://www.apple.com/newsroom/2016/06/apple-previews-ios-10-biggest-ios-release-ever.html .
* Ding, Bolin, Janardhan Kulkarni e Sergey Yekhanin 2017. Coletando dados de telemetria de forma privada, NIPS 2017.
* Ding, Bolin, Janardhan Kulkarni e Sergey Yekhanin 2017. Coletando dados de telemetria de forma privada, NIPS 2017.

Revisão das 18h29min de 24 de julho de 2022

A privacidade diferencial (DP) é 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

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

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

(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

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 é 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

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

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

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

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

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

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

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

  • 2008: Departamento do Censo dos Estados Unidos, para mostrar padrões de deslocamento.[19]
  • 2014: RAPPORT do Google, para telemetria, como aprender estatísticas sobre softwares indesejados que sequestram as configurações dos usuários.[20][21]
  • 2015: Google, para compartilhar estatísticas históricas de tráfego.[22]
  • 2016: A Apple anunciou sua intenção de usar privacidade diferencial no iOS 10 para melhorar sua tecnologia de assistente pessoal inteligente.[23]
  • 2017: Microsoft, para telemetria no Windows.[24]
  • 2019: Privitar Lens é uma API que usa privacidade diferencial.[25]
  • 2020: LinkedIn, para consultas de anunciantes.[26]

Considerações de propósito público

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

Referências

  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

Ligações externas