# Privacidade diferencial

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. 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 ${\mathcal {A}}$ 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 ${\textrm {im}}\ {\mathcal {A}}$ a imagem de ${\mathcal {A}}$. Diz-se que o algoritmo ${\mathcal {A}}$ fornece $\varepsilon$-privacidade diferencial se, para todos os conjuntos de dados $D_{1}$ e $D_{2}$ que diferem em um único elemento (ou seja, os dados de uma pessoa), e todos os subconjuntos $S$ de ${\textrm {im}}\ {\mathcal {A}}$:
$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp \left(\varepsilon \right)\cdot \Pr[{\mathcal {A}}(D_{2})\in S],$
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 $t$ vezes, e a randomização do mecanismo é independente para cada consulta, então o resultado seria $\varepsilon t$-diferencialmente privado. No caso mais geral, se houver $n$ mecanismos independentes: ${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$, cujas garantias de privacidade são $\varepsilon _{1},\dots ,\varepsilon _{n}$ privacidade diferencial, respectivamente, então qualquer função $g$ deles: $g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})$ é $\left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)$-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 $g$ seria $(\max _{i}\varepsilon _{i})$-diferentemente privada em vez disso.

### Robustez ao pós-processamento

Para qualquer função determinística ou aleatória $F$ definida sobre a imagem do mecanismo ${\mathcal {A}}$, se ${\mathcal {A}}$ satisfaz a privacidade ε-diferencial, o mesmo acontece com $F({\mathcal {A}})$.
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 $c$ linhas, o que equivale a um adversário com informações auxiliares arbitrárias que saberem se $c$ participantes em particular enviaram suas informações. Isso pode ser alcançado porque se $c$ itens mudam, a dilatação da probabilidade é limitada por $\exp(\varepsilon c)$ ao invés de $\exp(\varepsilon )$, ou seja, para D$_1$ e D$_2$ diferindo em $c$ items:
    $\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!$
Assim, utilizando ε em vez de $\varepsilon /c$ atinge-se o resultado desejado (proteção de $c$ Itens). Em outras palavras, em vez de ter cada item ε-diferencialmente privado protegido, agora cada grupo de $c$ itens são protegidos de forma ε-diferencialmente privada (e cada item é $(\varepsilon /c)$-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 e a amostragem posterior amostram de uma família de distribuições dependente do problema.

### Sensibilidade

Seja $d$ um número inteiro positivo, ${\mathcal {D}}$ uma coleção de conjuntos de dados, e $f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}$ uma função. A sensibilidade de uma função, denotada $\Delta f$, é definida por
    $\Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},$
em que o máximo é sobre todos os pares de conjuntos de dados $D_{1}$ e $D_{2}$ em ${\mathcal {D}}$ diferindo em no máximo um elemento e $\lVert \cdot \rVert _{1}$ denota a norma $\ell _{1}$.
No exemplo do banco de dados médico abaixo, se considerarmos que $f$ é a função $Q_{i}$, 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 ${\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!$, que tem média zero e desvio padrão ${\sqrt {2}}\lambda \,\!$ ). Agora, no nosso caso, definimos a função de saída de ${\mathcal {A}}\,\!$ como uma função a valores reais (chamada de saída de transcrição por ${\mathcal {A}}\,\!$) como ${\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!$, em que $Y\sim {\text{Lap}}(\lambda )\,\!\,\!$ e $f\,\!$ é a consulta/função de valor real original que planejamos executar no banco de dados. Agora claramente ${\mathcal {T}}_{\mathcal {A}}(x)\,\!$ pode ser considerada uma variável aleatória contínua, onde
    ${\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!$
que é no máximo $e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!$. Podemos considerar ${\frac {\Delta (f)}{\lambda }}\,\!$ como sendo o fator de privacidade $\varepsilon \,\!$. Desta forma, ${\mathcal {T}}\,\!$ 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 ${\mathcal {A}}\,\!$ como o algoritmo $\varepsilon \,\!$-diferencialmente privado, precisamos ter $\lambda =1/\varepsilon \,\!$. 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.
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 $D_{1}$ no qual cada registro é um par (Nome, X), em que $X$ é 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 $Q_{i}$ que retorna a soma parcial do primeiro $i$ linhas de coluna $X$ no banco de dados. Para descobrir o status de diabetes de Chandler, o adversário executa $Q_{5}(D_{1})$ e $Q_{4}(D_{1})$, então calcula sua diferença. Neste exemplo, $Q_{5}(D_{1})=3$ e $Q_{4}(D_{1})=2$, 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 $D_{2}$ substituindo (Chandler, 1) por (Chandler, 0), então esse adversário malicioso será capaz de distinguir $D_{2}$ de $D_{1}$ calculando $Q_{5}-Q_{4}$ para cada conjunto de dados. Se o adversário fosse obrigado a receber os valores $Q_{i}$ através de um algoritmo $\varepsilon$-diferencialmente privado, então para um $\varepsilon$ 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, é pedir a uma pessoa que responda à pergunta "Você possui o atributo A ?", de acordo com o seguinte procedimento:
* Jogue uma moeda.
* Se der cara, jogue a moeda novamente (ignorando o resultado) e responda à pergunta honestamente.
* 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.

### Transformações estáveis

Uma transformação $T$ é $c$-estável se a distância de Hamming entre $T(A)$ e $T(B)$ é no máximo $c$-vezes a distância de Hamming entre $A$ e $B$ para quaisquer dois bancos de dados $A,B$. O Theorem 2 de afirma que se existe um mecanismo $M$ que é $\varepsilon$-diferentemente privado, então o mecanismo composto $M\circ T$ é $(\varepsilon \times c)$-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 $h$ entre $A$ e $B$ (Onde $A$ contém o grupo e $B$ não). Nesse caso $M\circ T$ é $(\varepsilon \times c\times h)$-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. 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.

## 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.
* 2014: RAPPORT do Google, para telemetria, como aprender estatísticas sobre softwares indesejados que sequestram as configurações dos usuários.
* 2015: Google, para compartilhar estatísticas históricas de tráfego.
* 2016: A Apple anunciou sua intenção de usar privacidade diferencial no iOS 10 para melhorar sua tecnologia de assistente pessoal inteligente.
* 2017: Microsoft, para telemetria no Windows.
* 2019: Privitar Lens é uma API que usa privacidade diferencial.
* 2020: LinkedIn, para consultas de anunciantes.

## 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:
* 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.