Proteger a Privacidade em Compartilhamento de Dados com Várias Partes

No mundo digital de hoje, a privacidade é super importante. A galera muitas vezes precisa compartilhar informações enquanto mantém seus dados em sigilo. Uma situação comum acontece quando vários grupos querem encontrar itens em comum em suas listas privadas, sem revelar suas listas inteiras uns para os outros. Esse problema é conhecido como interseção de conjuntos privados (PSI).

Tradicionalmente, encontrar informações compartilhadas entre dois grupos é mais fácil do que envolver muitos grupos. Quando mais de dois grupos estão envolvidos, a parada fica mais complicada. O objetivo é criar um método que permita a muitos grupos encontrar itens em comum, mantendo seus dados privados e seguros.

#Visão Geral do Problema

Imagina uma situação onde três empresas querem saber quais clientes elas têm em comum, sem compartilhar suas listas de clientes inteiras. Se cada empresa compartilhar sua lista completa, pode acabar expondo informações sensíveis. Então, é preciso encontrar uma solução que proteja a privacidade delas, mas que ainda permita descobrir os clientes em comum.

Para resolver isso, precisamos de um método seguro que permita a cada empresa calcular a interseção de suas listas de clientes, enquanto mantém a privacidade. Essa é a essência do nosso trabalho.

#Tipos de Interseção de Conjuntos

Existem dois tipos principais de PSI: de duas partes e multi-partes.

1. PSI de Duas Partes: Envolve duas partes que querem encontrar itens comuns em suas listas. Elas podem usar métodos existentes que são eficientes e seguros.

2. PSI Multi-Partes: É uma situação mais complexa, onde três ou mais partes colaboram para encontrar itens em comum. É mais desafiador porque cada parte precisa proteger seus dados enquanto ainda participa do processo.

#Métodos de Cálculo Seguro

Para realizar esses tipos de PSI, podemos usar métodos de cálculo seguro. Esses métodos permitem que as partes calculem resultados com base em suas entradas, sem expor essas entradas. Existem várias abordagens para implementar o cálculo seguro:

1. Circuitos Embaralhados: Essa técnica transforma o cálculo em uma forma que mantém os valores de entrada escondidos. Só os resultados são revelados no final. Esse método torna possível executar cálculos complexos sem revelar os dados reais.

2. Compartilhamento Secreto: Nesse método, um item de dado é dividido em partes, chamadas de shares. Somente um certo número de shares pode reconstruir o dado original. Assim, as partes individuais não conseguem acessar o dado todo.

#Nossas Soluções Propostas

No nosso trabalho, focamos em PSI multi-partes e desenvolvemos duas abordagens principais para enfrentar esse problema:

1. Protocolo de Bitwise-AND Multi-partes (mBWA): Esse protocolo usa vetores de bits, que são arrays de bits, para representar os conjuntos de entrada. Cada parte distribui seus vetores de bits para duas partes designadas para o cálculo. A interseção é encontrada usando operações simples de AND nos vetores de bits.

2. Protocolo Sort-Compare-Shuffle Multi-partes (mSCS): Esse método estende a técnica Sort-Compare-Shuffle para várias partes. Cada parte ordena seus dados antes de distribuí-los. Depois de ordenar, as partes podem mesclar suas listas ordenadas e identificar elementos comuns.

Ambos os métodos garantem privacidade enquanto permitem que as partes calculem a interseção.

#O Protocolo de Bitwise-AND Multi-partes

O protocolo mBWA é feito para situações onde o universo de itens é pequeno. Cada parte representa seu conjunto de entrada como um vetor de bits. O cálculo segue assim:

1. Cada parte tem uma lista de itens representada por bits, com cada bit indicando se um item está presente.
2. As partes enviam seus vetores de bits para duas partes designadas.
3. As partes designadas combinam os vetores de bits usando a operação AND, que encontra efetivamente os itens comuns.

Embora esse método seja eficiente, ele é limitado a conjuntos de dados pequenos, porque o tamanho do vetor de bits cresce exponencialmente com o número de itens.

#O Protocolo Sort-Compare-Shuffle Multi-partes

O protocolo mSCS é mais adequado para conjuntos de dados maiores. Esse protocolo funciona por meio de ordenação e embaralhamento:

1. Cada parte ordena seus dados localmente.
2. Os conjuntos ordenados são distribuídos entre duas partes, que então mesclam as listas ordenadas.
3. Assim que as listas são mescladas, as partes podem identificar itens comuns comparando-os.

Para manter a privacidade, depois de identificar os itens comuns, os resultados são embaralhados. Esse processo de embaralhamento oculta qualquer informação posicional, garantindo que os conjuntos de entrada de cada parte permaneçam confidenciais.

#Usando Hashing para Eficiência

Para melhorar ainda mais nossos protocolos, usamos Técnicas de Hashing. O hashing ajuda mapeando itens em bins. Isso permite:

1. Comunicação Reduzida: Ao invés de enviar todos os itens, as partes só enviam itens dentro de seus respectivos bins, reduzindo a quantidade de dados trocados.

2. Processamento Paralelo: Como os bins operam de forma independente, o cálculo pode ser realizado simultaneamente para cada bin. Isso acelera o processo geral.

#Etapas de Hashing

1. Hashing Simples: Cada parte hash os itens em bins. Se os itens ultrapassarem a capacidade de um bin, eles podem ser ignorados ou remapeados. Cuidados são tomados para minimizar a chance de falhas no mapeamento de itens para bins.

2. Hashing Baseado em Permutação: Essa técnica permite uma representação mais eficiente dos itens nos bins, reduzindo o comprimento de bits necessário para armazenar os dados. Garante que se dois itens compartilham a mesma representação em um bin, eles são de fato os mesmos itens.

Ao empregar esses métodos de hashing, melhoramos significativamente a eficiência da comunicação e reduzimos a complexidade de nossos protocolos.

#Considerações de Segurança

Ao desenhar esses protocolos, é crucial garantir a segurança. Focamos principalmente no modelo semi-honesto. Nesse modelo, assume-se que todas as partes seguem o protocolo como pretendido. Contudo, elas podem tentar aprender o máximo possível sobre os dados dos outros.

Para proteger contra possíveis brechas de privacidade:

1. Compartilhamento Secreto: Usamos técnicas de compartilhamento secreto para distribuir os conjuntos de forma segura, para que nenhuma parte única possa aprender sobre os dados da outra.

2. Embaralhamento Oblivioso: Após revelar os resultados da interseção, embaralhamos os dados para evitar qualquer inferência sobre os conjuntos de entrada individuais com base na sua ordem.

#Resultados Experimentais

Para validar nossos protocolos, realizamos experimentos para avaliar seu desempenho em cenários práticos. Usando computadores conectados via uma rede local, testamos vários tamanhos de entrada. Os resultados mostram que:

• O protocolo mBWA funciona de forma eficiente em cenários de dados pequenos, mas se limita à medida que os dados escalam.
• O protocolo mSCS, com seus mecanismos de ordenação e embaralhamento, se saía efetivamente mesmo com conjuntos de dados maiores.
• A implementação de técnicas de hashing reduz efetivamente a sobrecarga de comunicação e permite uma melhor utilização de recursos.

#Conclusão

A necessidade de compartilhamento de dados privados continua crescendo em vários setores, incluindo negócios, saúde e pesquisa. Nossos protocolos propostos para interseção de conjuntos privados multi-partes fornecem uma base para o cálculo seguro e eficiente de informações compartilhadas entre várias partes.

Ao utilizar técnicas como operações bitwise, ordenação, embaralhamento e hashing, criamos métodos que protegem a privacidade dos participantes enquanto permitem que eles descubram informações compartilhadas. Este trabalho contribui para uma melhor compreensão de como proteger dados sensíveis, permitindo ao mesmo tempo colaboração e extração de insights de conjuntos de dados compartilhados. À medida que a tecnologia avança, a necessidade de protocolos que preservem a privacidade se tornará cada vez mais significativa, tornando nossa pesquisa oportuna e relevante.

No futuro, pretendemos aprimorar ainda mais a eficiência e escalabilidade de nossos protocolos, abordando novos desafios de privacidade que possam surgir em um cenário digital em constante evolução.