Quando você se inscreve em uma nova rede social, como o WhatsApp, é perguntado com frequência se deseja descobrir quem dentre seus contatos já faz parte dessa rede social ( descoberta de contatos ). Mas se você não deseja fornecer sua lista completa de contatos, como saber se alguém está na rede social sem compartilhar sua agenda?

Países em metade do mundo estão desenvolvendo COVID-19 monitoramento infecção aplicativos . Na Espanha, por exemplo, o piloto Radar COVID foi lançado na ilha de La Gomera no final de junho. Esses aplicativos levantam muitas suspeitas em relação à privacidade. Seria possível descobrir se você esteve em contato com alguém que foi infectado sem você ou o servidor sabendo exatamente quem eles são?

Ou imagine que um laboratório tenha descoberto um medicamento contra o COVID-19 que funciona apenas com pessoas que possuem certos genes. Como o laboratório pode saber se você possui esses genes sem revelar todo o seu genoma para eles ou o laboratório revelando quais são esses genes específicos?

O que está acontecendo?

O Big Data e a computação em nuvem estão dando origem a uma infinidade de situações nas quais duas partes têm um conjunto de dados que desejam compartilhar com a outra para encontrar a interseção entre os dois conjuntos. Claro, apenas revelando os dados em comum. Esse é um antigo problema criptográfico conhecido como PSI ( Private Set Intersection ) que está enfrentando um forte ressurgimento. Além dos três cenários já mencionados, existem muitos outros casos de uso:

• Uma empresa desenvolve um aplicativo de diagnóstico remoto para COVID-19 com precisão extraordinária a partir de uma lista de sintomas fornecidos pelo paciente. O paciente não deseja divulgar seus sintomas para a empresa, nem deseja divulgar a ninguém quais sintomas eles usam para o diagnóstico.
• A mesma pessoa recebe atendimento médico em locais diferentes. Diferentes administrações querem saber quais pacientes visitaram centros de saúde em outras comunidades sem divulgar sua lista de pacientes.
• Para realizar uma operação internacional, várias agências nacionais de segurança cibernética desejam encontrar a interseção entre seus bancos de dados de IPs criminais sem divulgar suas listas de IPs completas.
• Uma agência de publicidade envia um anúncio on – line a um grupo de usuários. Alguns desses usuários compram o produto posteriormente em uma loja física. A agência deseja encontrar a interseção entre o grupo de usuários que viram o anúncio do produto e aqueles que o compraram em lojas físicas ( conversões de anúncios online para offline ).
• Uma empresa de alimentos saudáveis ​​serve refeições para muitos funcionários de outra empresa, que realiza exames médicos duas vezes por ano. A empresa de restaurantes deseja saber se os funcionários que reduziram o colesterol no último ano consumiram seus alimentos, mas a outra empresa não deseja (nem deve) divulgar os dados de saúde de seus funcionários. 

Quanto mais força a nuvem e o Big Data ganham, mais novos casos de uso surgem todos os dias: detecção de botnets , identificação de truques em jogos online , compartilhamento de localizações, descoberta de credenciais comprometidas etc.

A necessidade de realizar essa interseção de conjuntos em particular tornou-se clara, mas a questão é: como alcançá-lo? A criptografia oferecia inúmeras técnicas de PSI, desde a solução ingênua de hash até protocolos de terceiros semi-confiáveis ​​e protocolos envolvendo apenas duas partes. Vamos ver brevemente como eles funcionam.

A solução ingênua com funções hash

Consiste em comparar os hashes de cada elemento dos dois conjuntos. Se dois hashes coincidirem, ocorreu um ajuste. Essa abordagem, que era usada pelo WhatsApp na época, é simples e rápida, mas não é segura porque, com um pequeno conjunto de dados ou com baixa entropia, como números de telefone, é perfeitamente viável realizar um ataque de força bruta. , calculando os hashes de todos os elementos possíveis. Dessa forma, armado com a lista de hash de todos os telefones, o WhastApp não apenas saberia os contatos que você compartilha, mas também os números de telefone de todos os seus contatos!

Da mesma forma, essa abordagem não serve para comparar DNIs, identificadores simples, nomes etc. Ele fornece segurança apenas quando os dados a serem comparados são aleatórios ou possuem uma entropia alta.

PSI baseado em terceiros semi-confiáveis

Outra abordagem mais robusta é passar cada um dos elementos dos conjuntos pela mesma função HMAC com uma chave secreta com a qual as duas partes, Alice e Bob, concordaram anteriormente. Eles enviam seus dados aleatórios para o terceiro, Trent, que retorna o conjunto de interseções para cada um deles. Como Alice e Bob mantiveram uma tabela particular com as saídas da função HMAC para cada dado em seus respectivos conjuntos, eles podem procurar nessa tabela as configurações e determinar quais elementos eles compartilham.

A informação máxima vazada para Trent é a cardinalidade do conjunto de interseções, ou seja, quantos elementos Alice e Bob têm em comum; e a cardinalidade dos sets de Alice e Bob, já que Trent saberá se Alice tem mais elementos em seu set que Bob ou vice-versa. É claro que Trent pode ser malicioso e tentar enganar Alice e Bob, por exemplo, retornando um conjunto de interseções diferente do real. Felizmente, existem ajustes simples neste protocolo para impedir esse tipo de manipulação por Trent. O que você nunca descobrirá são os dados de Alice e Bob.

PSI baseado em duas partes

E se você não quiser depender de terceiros? Não há problema. Existem muitas abordagens alternativas nas quais apenas as duas partes envolvidas que desejam encontrar a interseção entre seus conjuntos interagem.

Uma das primeiras abordagens propostas e conceitualmente mais simples é baseada nas premissas criptográficas do famoso protocolo Diffie-Hellman para acordar chaves de sessão entre duas partes através de um canal inseguro. Nesse caso, Alice e Bob aplicam o protocolo DH para compartilhar uma chave de sessão para cada dado em seus respectivos conjuntos. Qualquer chave compartilhada encontrada nos dois conjuntos indica que o elemento correspondente é um membro dos conjuntos originais de ambas as partes. Vamos ver com mais detalhes como funciona:

1. Alice e Bob concordam com um grande número primo, p , usando um canal público.
2. Alice gera aleatoriamente uma chave privada, a .
3. Alice calcula o haxixe , g _i , de cada um dos valores no seu conjunto original. Na verdade, essa etapa é um pouco mais complicada, pois é necessário repetir o hash até que g seja um módulo raiz primitivo p , mas não entraremos em detalhes matemáticos.
4. Para cada uma destas g _i valores , Alice calcula o g _i ^uma modificação valor de p .
5. Alice envia esses valores para Bob.
6. Bob gera aleatoriamente uma chave privada, b .
7. Bob calcula repetidamente a de hash , h _i , de cada um dos valores no seu conjunto original, até que eles são raízes primitivas modulo p .
8. Para cada um desses valores de hash , Bob calcula h _i ^b mod p .
9. Bob calcula as chaves compartilhadas para cada elemento no conjunto original de Alice, elevando os valores recebidos de Alice ao poder de sua chave privada, ou seja, g _i ^ab mod p .
10. Bob envia seus valores calculados, h _i ^b mod p , para Alice, bem como as chaves compartilhadas calculadas correspondentes aos elementos do conjunto original de Alice, g _i ^ab mod p .
11. Alice calcula as chaves compartilhadas para cada elemento do conjunto original de Bob, elevando os valores recebidos de Bob ao poder de sua chave privada, ou seja, h _i ^ba = h _i ^ab mod p , para cada um dos valores recebidos de Bob .
12. Alice compara as chaves compartilhadas calculadas a partir dos elementos de seu próprio conjunto original, g _i ^ab , com as chaves compartilhadas calculadas com os elementos de Bob, h _i ^ab . A interseção consiste nos elementos do conjunto original de Alice cuja chave compartilhada também pode ser encontrada no conjunto de chaves compartilhadas calculado a partir dos elementos do conjunto original de Bob, g _i ^ab = h _i ^ab .

Desde a publicação deste protocolo, surgiram dezenas de alternativas que usam primitivas criptográficas cada vez mais sofisticadas. Protocolos muito elaborados com base em outros algoritmos de chave pública foram propostos, como operações com RSA cego ; baseado em filtros Bloom ; em criptografia totalmente homomórfica ; na transferência inconsciente (OT) para transmitir os dados dos conjuntos; ou em variantes do  circuito confuso de Yao , capaz de simular qualquer função matemática com um circuito booleano usando exclusivamente portas lógicas AND e XOR.

Desafios de segurança e escalabilidade PSI

Os desafios de segurança e escalabilidade enfrentados por todos esses protocolos para calcular a interseção privada de conjuntos são muito variados:

• Os protocolos mais eficientes funcionam para pequenos conjuntos de algumas centenas a milhares de elementos. No entanto, em muitas aplicações reais, conjuntos de bilhões de dados precisam ser comparados, exigindo alternativas mais rápidas.
• Além de exigir poucas operações para sua operação, é importante minimizar as comunicações para troca de dados entre as partes.
• Nem todos os oficiais envolvidos cumprirão as regras. Na computação segura multipartidária , dois tipos de adversários são considerados: semi-honesto (ou passivo) e malicioso (ou ativo). O adversário semi-honesto tenta obter o máximo de informações possível sobre a execução de um determinado protocolo, sem se desviar das etapas do protocolo. Mais perigoso e realista é o adversário malicioso, porque ele se desvia arbitrariamente das etapas do protocolo para jogar com vantagem e obter mais informações do que os outros. Protocolos PSI robustos contra adversários mal-intencionados são consideravelmente mais pesados ​​e menos eficientes que os protocolos semi-honestos resistentes a adversários.
• O PSI mais simples aborda as informações de filtro: no mínimo, o número de elementos em cada conjunto e o número de elementos no conjunto de interseção. Em aplicativos em que nem sequer é aceitável filtrar essas informações, são necessários protocolos mais seguros, que infelizmente exigem mais operações e mais largura de banda.

Quanto mais a nuvem e o Big Data avançam, maior a demanda por PSI

À medida que as leis e os regulamentos de proteção de dados evoluem em um esforço para proteger a esfera privada da vida dos cidadãos, a interseção privada de conjuntos permitirá que organizações públicas e privadas continuem a gerar conhecimento do Big Data que beneficia ao cidadão, cumprindo os regulamentos de privacidade.

Em junho de 2019, o Google anunciou uma ferramenta para executar operações na interseção do conjunto chamada Participe e computação privadas. De acordo com o comunicado de imprensa:

Usando esse protocolo criptográfico, duas partes podem criptografar seus identificadores e dados associados e, em seguida, juntá-los em uma consulta. Eles podem fazer certos tipos de cálculos no conjunto de dados sobreposto para obter informações úteis dos dois conjuntos de dados juntos. Todas as entradas (identificadores e seus dados associados) permanecem totalmente criptografadas e ilegíveis durante todo o processo. Nenhuma das partes nunca divulga seus dados brutos, mas pode continuar respondendo às perguntas feitas usando a saída de cálculo. Esse resultado final é a única coisa que é descriptografada e compartilhada na forma de estatísticas agregadas, como contagem, soma ou média dos dados nos dois conjuntos.

O Private Join and Compute combina interseção de conjuntos privados com criptografia totalmente homomórfica para proteger dados individuais. O vídeo a seguir dá uma idéia de como funciona:

O PSI pressupõe a interseção entre a voracidade dos dados das grandes organizações e o direito à privacidade dos cidadãos. Gigantes de tecnologia como Google , Microsoft ou Baidu estão investindo enormes somas de dinheiro e neurônios criptografados nessas tecnologias. Nos próximos meses, veremos onde os aplicativos massivos de análise de dados se voltam, seja para favorecer o cidadão com melhores serviços ou corroer ainda mais sua privacidade prejudicada. Porque, como afirmou o criptógrafo Phil Rogaway:

A vigilância que preserva a privacidade ainda é vigilância.