Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

Este trabalho propõe algoritmos otimizados de multiplicação de matrizes esparsas em computação multipartidária (MPC) que superam as limitações de memória e comunicação das abordagens densas, permitindo a aplicação prática de aprendizado de máquina com privacidade em dados esparsos de alta dimensão, como em sistemas de recomendação e genômica.

O essencial

Imagine que você e seus amigos querem descobrir qual é o filme favorito do grupo, mas ninguém quer revelar o que eles assistiram. Vocês querem fazer essa conta juntos sem que ninguém saiba o segredo dos outros. Isso é o que chamamos de Computação Multi-Parte (MPC): fazer cálculos com dados secretos sem que os dados sejam expostos.

O problema é que, na vida real, esses "dados secretos" (como o histórico de filmes de milhões de pessoas) são extremamente esparsos. Isso significa que a maioria das informações é zero. Por exemplo, se você tem 1 milhão de filmes, você provavelmente assistiu a apenas 50. O resto é "nada".

O Problema: A "Caixa Cheia de Palha"

Até agora, os sistemas de segurança funcionavam como se você tivesse que guardar todos os filmes em uma caixa gigante, mesmo os que ninguém assistiu.

• A abordagem antiga (Matriz Densa): É como tentar organizar uma biblioteca onde você coloca um livro em cada estante, mesmo que 99% das estantes estejam vazias. Isso ocupa um espaço absurdo (memória) e gasta muito tempo (comunicação) apenas para mover caixas vazias. Em sistemas seguros, isso é tão pesado que o computador "explode" de memória antes de terminar a conta.

A Solução: O "Sistema de Lista de Presentes"

Os autores deste artigo criaram um novo método inteligente para lidar com essa "esparsidade" (muitos zeros). Em vez de guardar tudo, eles guardam apenas o que existe.

Imagine que, em vez de uma lista de 1 milhão de filmes, cada pessoa entrega apenas um bilhete com os 50 filmes que assistiu.

1. O Truque da Ordenação Cega: O sistema pega todos esses bilhetes de todas as pessoas, embaralha-os de forma que ninguém saiba de quem é o quê, e os organiza (ordena) por título.
2. A Multiplicação: Quando dois bilhetes com o mesmo título aparecem juntos, o sistema multiplica os valores e soma. Se não há bilhete para aquele título, o sistema simplesmente ignora (não gasta energia).
3. O Resultado: No final, vocês têm a resposta (quem gosta do mesmo filme) sem nunca ter visto a lista completa de ninguém.

Por que isso é um milagre?

Os autores mostram que, ao usar esse método de "apenas o que importa":

• Economia de Espaço: Em vez de precisar de um caminhão de caminhões (19 Terabytes) para guardar os dados, eles precisam de apenas uma mochila pequena (60 Gigabytes).
• Velocidade: A comunicação entre os computadores fica até 1.000 vezes mais rápida. É como trocar de enviar uma carta por correio para enviar um SMS instantâneo.

Onde isso é usado?

O papel mostra dois exemplos reais onde o método antigo falharia:

1. Sistemas de Recomendação (como Netflix): Para sugerir um filme, o sistema precisa comparar o que você assistiu com o que milhões de outros assistiram. Como ninguém assiste a tudo, os dados são cheios de "buracos". O novo método consegue fazer essa comparação sem travar o servidor.
2. Controle de Acesso Médico: Hospitais querem treinar uma IA para detectar acessos suspeitos aos prontuários dos pacientes. Os dados de acesso são muito específicos e esparsos. O novo método permite treinar essa IA protegendo a privacidade dos pacientes, algo que antes era impossível devido ao tamanho dos dados.

O Segredo Final: "O que precisamos saber?"

Para que esse truque funcione, o sistema precisa saber quantos bilhetes cada pessoa tem (a "esparsidade"), mas não precisa saber quais são os bilhetes.

• O Dilema: Saber exatamente quantos filmes cada pessoa assistiu pode ser um segredo.
• A Solução Criativa: Os autores propõem três formas de esconder isso:
  1. Anonimato: Esconder quem é quem (como usar um capuz).
  2. Preenchimento (Padding): Fingir que todos têm o mesmo número de bilhetes, adicionando "bilhetes falsos" (zeros) para esconder o número real.
  3. Modelos de Template: Criar "caixas" de tamanhos diferentes baseadas em estatísticas gerais (ex: "a maioria das pessoas tem poucos filmes, algumas têm muitos"), e encaixar os dados nessas caixas sem revelar o número exato de cada um.

Resumo

Este artigo é como inventar um novo tipo de caixa de transporte para segredos. Em vez de carregar o caminhão inteiro cheio de ar (dados vazios), eles inventaram uma caixa que se contrai para caber apenas nos dados reais. Isso permite que a Inteligência Artificial aprenda com dados privados e gigantes (como os de redes sociais ou genética) sem que os computadores explodam e sem que a privacidade das pessoas seja violada.

É a diferença entre tentar contar estrelas olhando para o céu todo (e se cansar) e usar um telescópio que só foca onde há estrelas, ignorando o espaço vazio.

Resumo técnico

Resumo Técnico: Multiplicações de Matrizes Esparsas Seguras e Aplicações em Aprendizado de Máquina Preservando Privacidade

1. O Problema

O Cálculo Multi-Partes (MPC) permite executar algoritmos de Aprendizado de Máquina (ML) sobre dados privados sem revelá-los. No entanto, os frameworks de MPC existentes carecem de operações otimizadas para dados esparsos (dados com uma grande maioria de valores zero).

• Limitações Atuais: A maioria dos protocolos de MPC trata os dados como matrizes densas. Em aplicações do mundo real (como sistemas de recomendação, genômica e processamento de linguagem natural), os dados são extremamente esparsos (ex: 99,99% de zeros).
• Consequências:
  • Inviabilidade de Memória: Armazenar dados esparsos em formato denso no MPC exige quantidades proibitivas de memória (ex: 19 TB em alguns cenários experimentais), tornando o processamento impossível.
  • Custo de Comunicação: Algoritmos densos geram custos de comunicação excessivos, pois processam todos os zeros desnecessariamente.
  • Limitação de Escala: Protocolos existentes para multiplicação esparsa geralmente exigem que os proprietários dos dados participem ativamente da computação ou que uma das partes conheça os dados em texto claro, o que não é compatível com o cenário de "treinamento terceirizado" (outsourced training) comum em ML moderno, onde milhares de proprietários de dados enviam dados para servidores de computação e se desconectam.

2. Metodologia

Os autores propõem dois novos algoritmos seguros para multiplicação de matrizes esparsas compartilhadas secretamente (secret-shared), focando no cenário de computação terceirizada (onde os dados são compartilhados com servidores de computação que não têm acesso aos dados brutos).

• Representação de Dados: Utilizam o formato de tuplas (COO - Coordinate Format), onde cada vetor esparsa é uma lista de pares (índice, valor) contendo apenas os elementos não nulos.
• Primitivas Criptográficas: Os algoritmos baseiam-se em:
  • Adição e multiplicação seguras.
  • Ordenação Cega (Oblivious Sorting): Para ordenar as tuplas por coordenada sem revelar a ordem ou os valores.
  • Embaralhamento Cego (Oblivious Shuffling): Para remover placeholders sem vazar informações.
• Algoritmos Propostos:
  1. Multiplicação Vetor-Esparsa: Concatena as listas de tuplas, ordena-as por coordenada e multiplica os valores correspondentes.
  2. Multiplicação Matriz-Esparsa: Agrupa os elementos por linha/coluna, realiza multiplicações escalares entre os elementos não nulos correspondentes e agrega os resultados usando ordenação cega.
• Conhecimento Público: Reconhecem que algum conhecimento sobre a esparsidade (número de não zeros) é necessário para eficiência. Propõem técnicas para minimizar e proteger esse conhecimento (ver abaixo).

3. Principais Contribuições

1. Algoritmos Eficientes para MPC: Desenvolvimento de dois algoritmos dedicados para multiplicação de matrizes esparsas secretas que evitam os problemas de memória das abordagens densas.
2. Compatibilidade com Cenário Terceirizado: Diferente de trabalhos anteriores que exigiam interação contínua dos donos de dados, esta solução suporta um número ilimitado de proprietários de dados que compartilham dados e se desconectam.
3. Minimização de Conhecimento Público: Propõem três técnicas para reduzir a informação pública necessária (que poderia ser sensível):
   • Anonimização de Linhas: Oculta qual dono de dados possui quantos não zeros, revelando apenas a distribuição global.
   • Preenchimento (Padding) Máximo: Adiciona "não zeros fictícios" (dummies) para que todas as linhas tenham o mesmo tamanho, revelando apenas o limite superior.
   • Modelagem de Matriz (Matrix Templating): Uma técnica mais sofisticada que divide a matriz em sub-matrizes baseadas em quantis da distribuição de esparsidade, reduzindo drasticamente a quantidade de dados fictícios adicionados em comparação ao preenchimento máximo.
4. Estimativa Privada: Apresentam protocolos para estimar esses limites de esparsidade usando MPC ou Diferencial de Privacidade (DP), garantindo que o conhecimento público necessário seja obtido sem violar a privacidade dos dados individuais.

4. Resultados Experimentais

Os autores validaram seus algoritmos em dois cenários de ML do mundo real e compararam com abordagens densas:

• Redução de Custos:
  • Memória: Enquanto a abordagem densa falha devido à falta de memória (ex: requerendo 19 TB), a abordagem esparsa consome apenas ~60 GB para os mesmos dados.
  • Comunicação: Redução de custos de comunicação de até 1000x (fator ×1000) para matrizes com 99,99% de esparsidade em comparação com a multiplicação densa.
• Aplicações de Caso de Uso:
  1. Sistema de Recomendação: Utilizando o dataset Bookcrossing (99,998% de zeros). O algoritmo denso causou estouro de memória; o algoritmo esparsa completou o treinamento em ~48 minutos.
  2. Controle de Acesso (ML): Utilizando dados de acesso da Amazon (99,95% de zeros) para treinar um modelo de Análise Discriminante Linear. O cálculo da matriz de covariância (que exige multiplicação matriz-matriz) foi inviável com métodos densos, mas executado em 5 horas com o método esparsa.
• Eficiência das Técnicas de Minimização: A técnica de "Matrix Templating" reduziu o overhead de memória (devido a dados fictícios) de quase 100x (no caso de preenchimento máximo) para apenas 2x em datasets como MovieLens.

5. Significância e Impacto

Este trabalho é fundamental para viabilizar o Aprendizado de Máquina Preservando Privacidade (PPML) em escala real.

• Viabilidade Prática: Demonstra que aplicações com dados de alta dimensionalidade e extrema esparsidade (comuns em indústria e saúde) podem ser processadas de forma segura, algo que era considerado impraticável com as tecnologias de MPC atuais.
• Escalabilidade: Resolve o gargalo de memória e comunicação que limitava o uso do MPC a conjuntos de dados pequenos ou densos.
• Privacidade Aprimorada: Ao introduzir métodos para minimizar e estimar privadamente o conhecimento sobre a esparsidade, o trabalho aborda uma lacuna crítica: como obter a eficiência necessária sem expor metadados sensíveis sobre os usuários ou a estrutura dos dados.

Em suma, o artigo preenche uma lacuna crítica na literatura de criptografia aplicada, fornecendo as ferramentas necessárias para que o MPC seja utilizado em cenários de ML do mundo real que envolvem dados esparsos massivos. O código-fonte foi disponibilizado publicamente para facilitar a adoção em frameworks existentes.