Geekly articles weekly

Matemática protegendo a privacidade: uma nova abordagem para segurança de dados

Em 1997, quando os pesquisadores médicos de Massachusetts começaram a fornecer acesso aos registros médicos dos funcionários, o governo removeu os nomes dos pacientes, seus endereços e números de previdência social das listas. William Weld, então governador, garantiu ao público que seria impossível restaurar a identidade mediante agendamento.

Alguns dias depois, uma carta chegou ao escritório de Weld enviada por um estudante do Instituto de Tecnologia de Massachusetts. Extratos do cartão médico do governador foram incluídos no envelope.

Embora os identificadores óbvios tenham sido removidos, as autoridades decidiram deixar a data de nascimento, sexo e código postal (CEP). Depois de comparar esses dados com as gravações de voz, Latanya Sweeney conseguiu calcular o prontuário médico de Weld.

O trabalho de Sweeney e outros avanços na privacidade nos últimos 15 anos levantam preocupações de segurança para dados supostamente anônimos.

"Descobrimos que a intuição das pessoas sobre quais dados considerar privados não está funcionando bem", diz Frank McSherry, da Microsoft Research Silicon Valley. "Os computadores estão constantemente aprimorando sua capacidade de extrair dados individuais de uma série de informações que o leigo consideraria seguras".

Estudar seu histórico médico pode ajudá-lo a encontrar os genes responsáveis ​​pelo risco de doença de Alzheimer, reduzir o número de erros nos hospitais ou encontrar o melhor remédio para uma doença. A única questão é como obter todos esses dados sem fornecer informações pessoais? Um estudo de dez anos sobre esse tópico já está abordando uma solução universal.

Essa abordagem é chamada de "privacidade diferencial" e permite publicar dados enquanto protege as informações pessoais. O algoritmo de diferenciação de dados permite que os pesquisadores formulem qualquer consulta em um banco de dados que contenha informações confidenciais e recebam uma resposta "borrada" de forma a não revelar nenhum dado pessoal - até mesmo a presença de dados de uma pessoa específica nesse banco de dados.

"A idéia é que você possa deixar seus dados serem utilizados sem risco", diz Cynthia Dvork, da Microsoft Research Silicon Valley. A Dvork introduziu o conceito de privacidade diferencial (RP) em 2005 com a ajuda de McSherry, Cobby Nissim e Adam Smith.

O método mantém o direito à "negação plausível", diz Avrim Blum, da Universidade Carnegie Mellon. “Se eu quiser fingir que minhas informações pessoais são diferentes daquilo que realmente tenho, posso fazê-lo. A saída do mecanismo de RP na prática não será muito diferente, independentemente de incluir o verdadeiro ou o falso - para que eu possa negar tudo o que quero. ”

Um nível tão alto de privacidade parece inatingível. E, de fato, não há algoritmo RP útil que produziria um resultado completamente idêntico quando você fornecer seus dados reais ou fictícios. Mas você pode permitir que os algoritmos produzam dados quase idênticos. O grau de diferença é calibrado e representa uma quantificação de privacidade. Pessoas ou comunidades podem decidir qual valor desse parâmetro corresponde a um grau aceitável de perda de privacidade e escolher os algoritmos apropriados.

Os especialistas em privacidade desenvolveram uma ampla gama de algoritmos de RP para processar dados diferentes e responder a perguntas diferentes sobre eles. A maior parte do trabalho é difícil de ser percebida por pessoas que não são especialistas na área, então os cientistas estão desenvolvendo linguagens de computador padronizadas que permitirão que não apenas especialistas publiquem dados confidenciais no modo RP, apenas escrevendo um programa simples. "O RP é uma tecnologia promissora e muito interessante", diz Aaron Roth, especialista em ciência da computação da Universidade da Pensilvânia.


O Comitê de Censo OnTheMap usa privacidade diferencial ao publicar dados, mas não divulgar informações pessoais

Agulha no palheiro


Parece que, para resolver problemas de privacidade, você só precisa liberar dados generalizados relacionados a grandes grupos de pessoas. Mas mesmo essa abordagem está repleta de violação da integridade dos dados pessoais.

Suponha que você precise descobrir se o autor tem diabetes e você sabe que meus dados estão no banco de dados. Pode-se subtrair os resultados de duas consultas: “Quantas pessoas têm diabetes no banco de dados” e “Quantas pessoas no banco de dados, com um nome diferente de Eric Clarreich, têm diabetes”.

A combinação de duas dessas consultas viola minha privacidade. Mas nem sempre é claro que combinações específicas de perguntas podem violar a privacidade. Encontrar essas combinações é uma tarefa completa do NP, ou seja, não existe um algoritmo de computador eficaz para rastrear esses "ataques".

Em 2008, os pesquisadores mostraram o perigo de publicar as informações agregadas obtidas na pesquisa genética geral - uma das principais ferramentas para encontrar a dependência do diabetes nos genes. Esses estudos envolvem a decodificação dos genes do grupo de teste de 100 a 1000 pacientes com a mesma doença, seguidos pelo cálculo da frequência média com a qual uma das 100.000 mutações ocorre. Se uma das mutações ocorre no grupo com muito mais frequência, ela é apontada como potencialmente associada à doença.

Uma equipe de pesquisadores liderada por Niels Homer, que era um estudante de graduação da Universidade da Califórnia na época, mostrou que, em muitos casos, conhecendo o genoma do paciente, você pode descobrir se ele fazia parte do grupo de testes do genoma. Depois disso, a associação de institutos médicos revogou o decreto de publicação dos dados obtidos em estudos genéticos.

Os pesquisadores chegaram a uma conclusão ainda mais surpreendente em 2011 - é possível extrair informações pessoais sobre compras, guiadas por um sistema de recomendação com a Amazon, que fornece resultados como “quem comprou e também comprou B e C”. Observando as alterações nas recomendações e comparando-as com as avaliações que as pessoas fazem sobre os itens comprados, em vários casos, os pesquisadores conseguiram dizer que um comprador em particular comprou um item em um dia específico - mesmo antes de publicar uma revisão desse item.

Em todos os casos, as medidas de privacidade parecem adequadas, desde que não sejam suficientes. Mas já naquele momento uma nova abordagem para proteger a privacidade estava sendo preparada, obtida pela busca da resposta para a pergunta principal: o que significa proteger a privacidade?

A privacidade de dois mundos


Se os pesquisadores examinarem o banco de dados de pacientes e encontrarem uma conexão entre fumar e algum tipo de câncer, a privacidade diferencial não protegerá uma pessoa que fuma em um local público do rótulo de uma pessoa com maior risco de adoecer. Mas se fumar é o segredo de uma pessoa, escondido na base, o RP o protegerá.

“Diferença” significa levar em consideração a diferença de dois mundos: em um deles você permite incluir seus dados pessoais no banco de dados e no outro não. Os dois mundos não serão absolutamente idênticos, mas podem ser feitos o mais semelhante possível, e será quase impossível distinguir entre eles. Esse é o objetivo do RP.

O RP se concentra em algoritmos que emitem dados, recebem consultas no banco de dados e emitem respostas - não exatas, mas modificadas aleatoriamente. Se você fizer a mesma pergunta em duas bases que diferem apenas nos dados de uma pessoa, obterá essencialmente as mesmas respostas.


Representação RP do local dos usuários que pesquisam a palavra "críquete" em um mecanismo de pesquisa

Mais precisamente, para qualquer resposta possível, a probabilidade de recebimento deve ser a mesma para os dois bancos de dados; a razão dessas duas probabilidades deve ser limitada a um número R próximo à unidade. Quanto mais R estiver próximo de 1, mais difícil é para um invasor descobrir se ele recebe informações da base A ou da base B e a pessoa mais protegida X estará. Como se o invasor não puder saber se as informações recebidas por ele incluem informações sobre X, ele não será capaz de entender quais dados se referem ao X. Os

pesquisadores de RP geralmente falam sobre o logaritmo de R e denotam-no por Ɛ. O parâmetro quantifica o vazamento de dados pessoais. Quanto mais próximo de zero, melhor o algoritmo protege a privacidade.

Para entender como o algoritmo RP pode ser construído, vejamos o exemplo mais simples de tal algoritmo. Ele usa um cenário em que o questionador pode fazer apenas consultas quantitativas. Por exemplo: “quantas pessoas no banco de dados possuem propriedade C?”

Suponha que a resposta real para uma das perguntas seja 157. O algoritmo RP adicionará "ruído" a ela - antes de emitir uma resposta, adicione ou subtraia um número aleatório. Como resultado, obtemos 153, 159 ou 292. O interlocutor conhece a distribuição de probabilidade usada pelo algoritmo; portanto, sabe aproximadamente a distorção do resultado real (caso contrário, o problema seria completamente inútil). Mas que tipo de número aleatório foi adicionado à resposta, ele não sabe.

A fórmula de distribuição deve ser escolhida com cuidado. Para entender qual distribuição garante privacidade, vamos imaginar que um solicitante persistente tente descobrir se estou no banco de dados. Ele pergunta: "Quantas pessoas chamadas Eric Clarreich estão no banco de dados?" Suponha que ele receba uma resposta de 100. Como esse nome é raro, ele percebe que a resposta era realmente 0 ou 1. Ele tem duas possibilidades:

A) a resposta é 0 e o algoritmo adicionou 100 como ruído;
B) a resposta é 1, e o algoritmo adicionou 99 A

probabilidade de escolher 100 e 99 deve ser a mesma. Então o questionador não pode distinguir entre esses dois casos. Mais precisamente, a razão dessas duas probabilidades não deve exceder um R. predeterminado. E essa condição deve ser preservada não apenas para os pares 100 e 99, mas também para quaisquer dois números consecutivos.

Esta propriedade tem a distribuição Laplace. Seu pico agudo cai para zero e, em seguida, o gráfico diminui gradualmente nas duas direções. Para isso, a condição para a existência do número R (largura da distribuição) é satisfeita, de modo que, para dois números consecutivos, a razão de suas probabilidades seja R.

Para cada largura, existe uma distribuição possível de Laplace. Portanto, você pode brincar com a largura para obter uma distribuição que forneça exatamente o grau de privacidade que precisamos. Para uma forte privacidade, a distribuição será relativamente ampla e plana. Números distantes de 0 cairão com quase a mesma probabilidade que números próximos de zero. Os dados serão borrados bastante.

Naturalmente, há um confronto entre privacidade e utilidade. Quanto mais privacidade você precisar, mais ruído precisará adicionar e menos útil será a resposta. Ao usar a distribuição Laplace, a quantidade de ruído adicionado volta Ɛ. Se o parâmetro de privacidade for 0,01, o algoritmo borrará os indicadores quantitativos em cerca de 100.

Quanto maior o conjunto de dados, menos o borrão especificado afetará o utilitário. Em um banco de dados de centenas de registros, um desfoque de 100 interferirá mais do que em um banco de dados de milhões de registros. Segundo Dvork, para dados em escala de Internet, ou seja, centenas de milhões, o algoritmo já oferece privacidade suficiente para uso prático.

E o "ruído", segundo Laplace, é apenas o primeiro estágio da implementação do PR. Os pesquisadores já criaram um grande número de algoritmos muito mais complexos, para muitos dos quais a proporção de utilidade e privacidade excede a de Laplace em determinadas situações.

"As pessoas sempre encontram maneiras de melhorar e ainda há espaço para melhorias", diz Dvork. Quanto a conjuntos de dados mais modestos que a Internet, ela disse: "existem algoritmos para muitas tarefas".

Com o algoritmo RP, não há necessidade de analisar cuidadosamente os problemas por violações da privacidade - essa proteção já está embutida no algoritmo. Como perguntas que interferem em seus próprios assuntos geralmente se resumem a pequenos números relacionados a pessoas específicas, e questões de natureza diferente estudam o comportamento de grandes grupos, a quantidade de ruído adicional que nega as características individuais terá pouco efeito nas respostas a perguntas legítimas.

Com o RP, os problemas dos pesquisadores de dados, como comparações cruzadas com fontes externas, desaparecem. A abordagem matemática não espera que o invasor tenha fontes limitadas de informações externas.

"A abordagem de RP implica que o invasor é onipotente", diz McSherry. - Mesmo que o invasor retorne após 100 anos, acumulando idéias e tecnologias de computador o tempo todo, ele ainda não conseguirá descobrir se você está no banco de dados. O RP está protegido do futuro. ”

Primitivo fundamental


Até agora, estamos considerando uma situação em que alguém faz consultas ao banco de dados com um número como resposta. Mas a realidade é mais complicada. Os pesquisadores querem fazer muitas perguntas ao banco de dados. E, com o tempo, partes de suas informações pessoais chegarão a vários bancos de dados, cada um dos quais fornecerá dados sem perguntar ao resto.

O RP fornece uma maneira fácil e precisa de avaliar a ameaça geral à privacidade quando os pesquisadores fazem a todas as bases de dados em que seus dados apresentam várias perguntas. Suponha que, se seus dados estiverem em dois bancos de dados, e esses dados forem fornecidos de acordo com algoritmos que fornecem os parâmetros de privacidade Ɛ1 e Ɛ2, a quantidade total de informações pessoais vazadas não será maior que Ɛ1 + Ɛ2. A mesma fórmula funciona para um único banco de dados com várias consultas. Para m consultas, o vazamento será delimitado acima de m * Ɛ.

Em teoria, um curador de banco de dados pode permitir que os pesquisadores façam quantas perguntas quiserem, adicionando a quantidade necessária de ruído de Laplace a cada resposta, para que a quantidade total de dados pessoais vazados não exceda um determinado limite.

Acontece que o limite de respostas numéricas não é tão crítico. Muitas outras consultas podem ser alteradas para que se tornem quantitativas. Por exemplo, se você precisar criar uma lista de centenas dos nomes mais populares para bebês nascidos em 2012, poderá, por exemplo, fazer uma sequência de perguntas como "Quantas crianças receberam nomes começando com A?" E processar os resultados.

"Um dos primeiros resultados do aprendizado de máquina afirma que qualquer coisa que possa ser aprendida em princípio pode ser aprendida usando consultas numéricas", diz Aaron Roth. “Tais solicitações não são brinquedos em si mesmas, mas uma primitiva fundamental”, isto é, tijolos, com base nos quais algoritmos mais complexos podem ser construídos.

Mas há um problema. Quanto mais perguntas pudermos fazer, mais ruído será adicionado a cada resposta. Vejamos um exemplo com nomes. Se decidirmos limitar a despesa máxima de privacidade Ɛ a 0,01, e os nomes forem 10.000, o limite de privacidade para cada problema será Ɛ / 10.000 ou 0,000001. O nível de ruído será 10.000 / Ɛ ou 1.000.000 - e esse nível simplesmente elimina os resultados reais.

Em outras palavras, a abordagem “frontal” com a adição de ruído de Laplace a cada resposta é limitada pelo número de perguntas possíveis. Para remediar a situação, os programadores tiveram que desenvolver primitivas mais adequadas - "tijolos" algorítmicos, com a ajuda de que, dada a estrutura de uma base e tarefa específica, podem responder a mais perguntas com maior precisão.

Por exemplo, em 2005, Smith descobriu que a tarefa com nomes tem uma estrutura especial: remover informações sobre uma pessoa do banco de dados altera a resposta para apenas um em cada 10.000 nomes. Portanto, não podemos adicionar mais de 1 / Ɛ ruído a cada resposta, em vez de 10.000 / Ɛ, e a privacidade da resposta permanecerá dentro do nosso limite. Tal primitivo pode ser aplicado a qualquer consulta de "histograma" - ou seja, uma consulta sobre quantas pessoas se enquadram em uma das várias categorias mutuamente exclusivas, como nomes.

Quando Smith disse ao Dwork sobre isso, "algo dentro de mim se alegrou", diz o Dwork. "Percebi que podemos usar a estrutura da solicitação ou cálculo e obter uma precisão muito maior da resposta".

Desde então, os cientistas da computação desenvolveram uma grande biblioteca de tais primitivos. E como a regra aditiva explica o que acontece com a privacidade ao combinar algoritmos, os programadores podem montar esses "tijolos" em estruturas complexas, enquanto monitoram as restrições ao vazamento de privacidade.

Para simplificar o acesso ao sistema RP para pessoas que não são especialistas, vários grupos estão trabalhando na criação de uma linguagem de programação que nos permitirá abstrair dos fundamentos matemáticos dos algoritmos.


PINQ - um dos exemplos de PL para RP

As linguagens de programação para trabalhar com privacidade diferencial, como o PINQ, fornecem uma interface para dados confidenciais e permitem que você faça perguntas sobre eles, ajustando respostas para proteger a privacidade. "Se você é responsável por um conjunto de dados, não precisa se preocupar com o que as pessoas fazem com ele enquanto as consultas são feitas usando este PL", diz McSherry, que criou o idioma PINQ. "O programa garante a segurança das consultas."

Recurso não renovável


Como a regra aditiva simples para Ɛ define o limite superior exato da perda de privacidade quando diferentes bancos de dados que contêm seus dados fornecem respostas para consultas, essa regra, de acordo com McSherry, transforma a privacidade em uma moeda.

Por exemplo, se você decidir qual restrição à perda de privacidade para você pessoalmente é aceitável para toda a sua vida, poderá decidir "gastar" essa privacidade - trocando por dinheiro ou apoiando um bom projeto de pesquisa. Sempre que você permitir o uso de seus dados em uma nova liberação de informações, você saberá qual é o saldo do seu "orçamento" de privacidade.

E o curador do conjunto de dados pode decidir como gastar a quantidade de privacidade que ele decidiu liberar - por exemplo, considere propostas de projetos de pesquisa que descrevam não apenas as solicitações disponíveis, mas também a quantidade de privacidade usada nos projetos. Em seguida, o curador poderá escolher quais projetos usarão melhor o “orçamento” existente desse conjunto de informações. Depois que o orçamento é gasto, o conjunto de dados é fechado.

"A privacidade é um recurso não renovável", diz McSherry. "Assim que você gasta, ele desaparece."

Quando perguntados sobre qual valor Ɛ representa uma restrição aceitável à perda de privacidade, a sociedade deve responder, não os programadores. E todos podem ter sua própria resposta. E embora a perspectiva de atribuir um preço a algo intangível como privacidade possa parecer assustadora, já existem análogos disso.

"Há outro recurso com as mesmas propriedades - o relógio da sua vida", diz McSherry. "O número deles é limitado e, depois que você os gasta, eles desaparecem." Mas, como temos uma moeda e um mercado de trabalho, nossa sociedade criou como atribuir um preço ao tempo humano. Pode-se imaginar como a mesma coisa acontecerá com a privacidade. ”

Source: https://habr.com/ru/post/pt398011/

More articles:


All Articles