Privacidade Diferencial saltou de artigos de pesquisa para manchetes de notícias tecnológicas no ano passado, quando, na introdução da WWDC, o VP da Apple de Engenharia Craig Federighi anunciou o uso do conceito da Apple para proteger a privacidade do usuário em iOS.

foi a última instância de uma tendência geral: usuários e engenheiros despertando para a importância da proteção de privacidade no software. Violações de privacidade de alto nível, como o “Modo Deus” da Uber, têm demonstrado em termos estrondosos a facilidade com que os funcionários de uma empresa podem abusar de dados sensíveis recolhidos de seus clientes.

a quantidade de dados sensíveis que está a ser registada digitalmente está a aumentar rapidamente. As pessoas agora dependem de serviços digitais para mais de seus pagamentos, transporte, navegação, compras e saúde do que nunca. Esta nova coleta de dados cria formas cada vez maiores de violar a privacidade.mas também cria oportunidades interessantes-para melhorar as redes de transporte, para reduzir o crime, para curar doenças—se disponibilizado aos cientistas e investigadores de dados certos. Existe uma tensão natural entre proteger a privacidade dos indivíduos no conjunto de dados e permitir análises que possam levar a um mundo melhor.algoritmos diferentes privados são uma solução técnica promissora que pode aliviar esta tensão, permitindo aos analistas realizar análises agregadas benignas, garantindo proteção significativa da privacidade de cada indivíduo.este campo de tecnologia em desenvolvimento vale a pena considerar em qualquer sistema que busca analisar dados sensíveis. Embora a garantia de Privacidade Diferencial tenha sido concebida há apenas dez anos, ela tem sido bem sucedida na academia e na indústria. Pesquisadores estão inventando e melhorando rapidamente algoritmos diferentes privados, alguns dos quais foram adotados tanto no iOS da Apple quanto no Google Chrome.

Este artigo discute os fatores históricos que levam à privacidade diferencial na sua forma atual, juntamente com uma definição de Privacidade Diferencial e exemplo de algoritmos diferencialmente privados. Ele então olha para algumas implementações recentes de alto perfil de algoritmos diferentes privados pelo Google, Apple, e outros.

Background

Differentially private algorithms are the latest in a decades-old field of technologies for privacy-preserving data analysis. Dois conceitos anteriores influenciaram directamente a privacidade diferencial:

1. tamanho mínimo do conjunto de consultas
2. definição de divulgação estatística de Dalenius.

vamos explicar estes em primeiro lugar, uma vez que eles fornecem um fundo útil para a privacidade diferencial.

Tamanho mínimo de conjunto de consulta o primeiro conceito é um tamanho mínimo de conjunto de consulta, que—como algoritmos privados diferentes-visa garantir a segurança das consultas agregadas. As consultas agregadas são aquelas em que o valor retornado é calculado através de um subconjunto de registros no conjunto de dados, tais como contagens, médias ou somas. Pode ser útil pensar em consultas agregadas como consultas SQL que começam com “selecionar soma”, “selecionar contagem”, ou “selecionar AVG”. Outros tipos de consultas agregadas incluem tabelas de contingência e histogramas.

um tamanho mínimo de conjunto de consulta é uma restrição que procura garantir que as consultas agregadas não podem vazar informações sobre indivíduos. Dado algum Número de limiar configurado T, Ele garante que cada consulta agregada é conduzida em um conjunto de pelo menos t registros. Um tamanho mínimo de conjunto de consultas bloquearia consultas agregadas que visavam menos de T indivíduos. Por exemplo, se T=2, bloquearia o seguinte:

“selecione AVG(salário) onde nome = ‘Troy Brown’;”.

porque esta consulta conduziria uma média sobre um registro (nós assumimos que existe apenas um Troy Brown).

Usando tamanhos mínimos de conjuntos de consultas previne certos ataques, mas não vem com uma garantia de Privacidade e, na prática, pode ser contornado por atacantes qualificados. Por exemplo, o atacante poderia realizar o ataque acima com:

“selecionar soma(salário);”.

“seleccione a soma (salário) em que nome != ‘Troy Brown’;”.”SELECT SUM (salary) WHERE position = ‘WR’;”.

“seleccionar a soma (salário) em que posição = ‘WR’ e idade != 45;

tais ataques são chamados de ataques de rastreador, e eles não podem ser parados por uma restrição de tamanho de conjunto de consulta mínima. Devido a estes ataques, os tamanhos mínimos de conjuntos de consultas foram considerados uma defesa inadequada para proteger sistemas de Consulta (ver Trabalho de Denning). Algo melhor, com uma garantia, era necessário para garantir a privacidade.em 1977, o estatístico Tore Dalenius propôs uma definição estrita de privacidade de dados: que o atacante não deveria aprender nada sobre um indivíduo que não conhecia antes de usar o conjunto de dados sensível. Embora esta garantia tenha falhado (e veremos porquê), é importante compreender porque é que a privacidade diferencial é construída como é.A definição de Dalenius falhou porque, em 2006, A cientista da computação Cynthia Dwork provou que esta garantia era impossível de dar—por outras palavras, qualquer acesso a dados sensíveis violaria esta definição de Privacidade. O problema que ela encontrou foi que certos tipos de informações de fundo sempre poderia levar a uma nova conclusão sobre um indivíduo. Sua prova é ilustrada na anedota seguinte: Sei que a Alice é cinco centímetros mais alta que a lituana. Então eu interajo com um conjunto de dados de mulheres lituanas e computo a altura média, que eu não conhecia antes. Agora sei exactamente a altura da Alice, apesar de ela não estar no conjunto de dados. É impossível contabilizar todos os tipos de informação de fundo que possam levar a uma nova conclusão sobre um indivíduo a partir da utilização de um conjunto de dados.

Dwork, depois de provar o acima, propôs uma nova definição: Privacidade Diferencial.o que é privacidade diferencial?a privacidade diferencial garante o seguinte:: que o atacante pode aprender praticamente nada mais sobre um indivíduo do que eles aprenderiam se o registro dessa pessoa estivesse ausente do conjunto de dados. Embora seja mais fraca do que a definição de privacidade de Dalenius, a garantia é suficientemente forte porque se alinha com incentivos do mundo real—os indivíduos não têm incentivo para não participarem num conjunto de dados, porque os analistas desse conjunto de dados tirarão as mesmas conclusões sobre esse indivíduo, quer o indivíduo se inclua ou não no conjunto de dados. Como as suas informações pessoais sensíveis são quase irrelevantes nas saídas do sistema, os utilizadores podem ter a certeza de que a organização que trata os seus dados não está a violar a sua privacidade.os analistas que aprendem “praticamente nada mais sobre um indivíduo” significa que estão limitados a uma pequena e insignificante mudança na crença sobre qualquer indivíduo. (Aqui e abaixo, “alteração” refere-se à alteração entre usar um conjunto de dados e usar o mesmo conjunto de dados menos o registo de qualquer pessoa.) A extensão desta mudança é controlada por um parâmetro conhecido como ϵ, que define o limite na alteração na probabilidade de qualquer resultado. Um valor baixo de ϵ, como 0.1, significa que muito pouco pode mudar nas crenças sobre qualquer indivíduo. Um alto valor de ϵ, como 50, significa que as crenças podem mudar substancialmente mais. A definição formal é a seguinte.

um algoritmo A É ϵ-differentially private if and only if:

Pr ≤ e^ ^ * Pr

para todos OS X e para todos os pares de conjuntos de dados D, D’ where D’ is D with any one record—i.e. one person’s data—missing. O símbolo e refere-se à constante matemática. Note que esta definição só faz sentido para algoritmos randomizados. Um algoritmo que dá saída determinística não é um candidato para a privacidade diferencial.

O principal apelo da garantia de privacidade diferencial é a sua limitação sobre a quantidade que qualquer analista pode aprender sobre um indivíduo. Além disso, ele tem as seguintes propriedades úteis:

• Composição: se duas questões são respondidas com diferencial de privacidade garantias de nível de ϵ1 e ϵ2, a par de consultas é coberto por uma garantia de nível (ϵ1 + ϵ2). Lembre-se que um valor mais elevado de ϵ significa uma garantia mais fraca.
• Strength against arbitrary background information: the guarantee does not rely in any way on what background information the attacker knows. Esta propriedade é uma das principais razões pelas quais a privacidade diferencial é mais forte do que uma garantia de Privacidade anterior, K-anonimato.
• Segurança em pós-processamento: não há restrições sobre o que pode ser feito com um diferencial privado resultado – não importa o que é combinado com, ou como ele é transformado, ele ainda é diferencialmente privado.

Como é que esta garantia é obtida no software? Algoritmos diferentes privados são algoritmos randomizados que adicionam ruído em pontos chave dentro do algoritmo. Um dos algoritmos mais simples é o mecanismo de Laplace, que pode pós-processamento resultados de consultas agregadas (por exemplo, contagens, somas e meios) para torná-las diferencialmente privadas. Abaixo está um exemplo de código Java para o mecanismo Laplace específico para contar consultas:

As principais partes desta função são

1. instanciar uma distribuição de probabilidade Laplace (ver Figura 1) centrada em 0 e escalado por 1 / ϵ. Nós usamos a implementação do Apache Commons, “LaplaceDistribution”, que é construída com dois argumentos: a média da distribuição, e a escala da distribuição. Note que epsilon mais baixo (mais Privacidade) leva a uma maior escala e, portanto, uma distribuição mais ampla e mais ruído.Retire uma amostra aleatória desta distribuição. Esta função de amostra() leva um número aleatório entre 0 e 1 e aplica a função de distribuição cumulativa inversa da distribuição Laplace (CDF) a este número. Este processo resulta em um número aleatório tal que sua probabilidade de ser qualquer valor específico corresponde à distribuição. Como uma forma alternativa de pensar sobre isso, se esta função de amostra foi invocada um milhão de vezes para obter um milhão de amostras, a forma do histograma dessas amostras iria coincidir de perto com a forma da distribuição de Laplace.
2. perturba o valor real adicionando o valor aleatório do Passo 2.

vamos considerar por que este algoritmo é diferencialmente privado, tomando o ponto de vista de um atacante chamado Eve. Digamos que o conjunto de dados são dados de saúde mental, e Eva concebeu um ataque de rastreador (ver acima) que irá revelar se seu alvo, Bob, recebe aconselhamento para o alcoolismo ou não. Se o resultado da consulta é 48, Eve sabe que Bob recebe aconselhamento; se é 47, Eve sabe o contrário.se a resposta é 47 ou 48, O mecanismo de Laplace irá retornar um resultado ruidoso em torno de 47 ou 48. Pode retornar 49, 46, ou mesmo, com menor probabilidade, 44 ou 51 (ver Figura 2 para um histograma). Na prática, é impossível para Eva ter certeza se a verdadeira resposta foi 47 ou 48 e, portanto, suas crenças sobre se Bob está no aconselhamento para o alcoolismo ou agora não vai mudar significantemente.

Figura 1: a distribuição de Laplace centrada em 0 com escala de 1. Pictured é a função densidade de probabilidade (PDF) da distribuição—o eixo y é a probabilidade relativa de que a variável terá o valor no eixo x.

Figura 2: os resultados prováveis da consulta de contagem para os dois cenários, onde a resposta real é 47 e quando é 48. Um pequeno número de saídas não seria suficiente para distinguir de que distribuição vieram. Epsilon está definido para 0,67.

Você pode ter observado por este ponto que Eva poderia cortar através do ruído repetindo a consulta muitas vezes, e vendo se as respostas se agrupam em torno de 47 ou 48. Para evitar esta tática, os sistemas privados diferencialmente devem ter um “orçamento de privacidade”, um limite na soma dos ϵ’s usados em cada consulta. Esta tampa funciona devido à propriedade de compostabilidade da privacidade diferencial descrita acima. Eles podem fazer algumas perguntas relativamente baixas, ou muitas centenas de perguntas de alto ruído, mas de qualquer forma, eles não serão capazes de estabelecer com confiança se a resposta verdadeira é 47 ou 48.

Finalmente, note que o mecanismo de Laplace para contagens é apenas um simples algoritmo privado diferente. O mecanismo Laplace pode ser estendido para trabalhar para somas e outras consultas agregadas. Além disso, existem algoritmos fundamentalmente diferentes que provaram satisfazer a garantia de Privacidade Diferencial. A few worth exploring are the Private Multiplicative Weights algorithm, the Multiplicative Weights Exponential Mechanism, and DualQuery.

Privacidade Diferencial em ação

Em junho de 2016, A Apple anunciou que iria começar a usar diferentes algoritmos privados para coletar estatísticas comportamentais de iPhones. Este anúncio, além de causar um enorme aumento no interesse de Privacidade Diferencial, mostrou que a privacidade diferencial pode ajudar as grandes organizações a obter novos valores a partir de dados que anteriormente não tocavam devido a preocupações de Privacidade.

embora a Apple tenha até agora feito poucos detalhes públicos, o algoritmo usado no iPhone parece semelhante ao projeto rapport do Google. O Google implementou um recurso no Chrome que recolhe estatísticas comportamentais de navegadores do Chrome através de um algoritmo de resposta Aleatório privado diferente.

em resposta aleatória, ruído aleatório é adicionado às estatísticas antes de serem submetidos ao coletor. Por exemplo, se a estatística real for 0, o navegador irá com alguma probabilidade substituir 0 por um 0 ou 1 seleccionado aleatoriamente. Cada usuário tem um grande grau de negação sobre o valor que seus relatórios de software, porque pode ser um valor aleatório. Mas coletivamente, o sinal se destaca sobre o ruído aleatório e a organização que coleta as Estatísticas (ou seja, Google ou Apple) pode observar com precisão as tendências.curiosamente, nem o Google nem a Apple, tanto quanto sabemos, revelaram o valor de ϵ que combina com a garantia de Privacidade Diferencial. Precisamos deste valor para compreender a protecção oferecida pela Garantia. Se eles usam um valor alto o suficiente de ϵ, Os analistas ainda podem aprender fatos sensíveis sobre os usuários com alta confiança. Um valor baixo de ϵ É necessário para proteção significativa da privacidade.

algoritmos diferentes privados também foram implementados em produtos de análise de preservação de privacidade, tais como os desenvolvidos pelo meu empregador Privitar. Estes produtos permitem que as empresas que trabalham com dados valiosos e sensíveis incorporem diferentes algoritmos privados em sua arquitetura de dados, fornecendo garantias de privacidade para seus usuários enquanto ainda realizam análises significativas sobre os dados.ambas as comunidades de engenharia e pesquisa têm caminhos para a frente com privacidade diferencial. Para os engenheiros, a tarefa é tornar-se educado sobre a privacidade diferencial e garantir que ele é usado quando apropriado para a proteção da privacidade do Usuário. Para os pesquisadores, é encontrar mais e melhor algoritmos privados diferentes, melhorando o conjunto de ferramentas com o qual podemos permitir a preservação da privacidade-análise de dados.todos temos a ganhar com o estabelecimento de garantias de Privacidade e com o sucesso da análise de dados. Por ambas as razões, estamos ansiosos para mais organizações abraçando a privacidade diferencial.

sobre o autor

Charlie Cabot é um cientista sênior de dados em Privitar, uma inicialização de privacidade de dados que constrói software de alto desempenho para anonimização de dados, incluindo algoritmos de perturbação e generalização e mecanismos diferencialmente privados, para facilitar o uso seguro de conjuntos de dados sensíveis. Charlie se concentra em garantias de Privacidade demonstráveis e no impacto estatístico da anonimização na análise e ciência dos dados. Anteriormente, trabalhando em segurança cibernética, Charlie projetou abordagens baseadas no aprendizado de máquinas para detecção de malware e modelou ataques cibernéticos em redes de computadores.