Efficient Privacy-Preserving Sparse Matrix-Vector Multiplication Using Homomorphic Encryption

Este artigo apresenta o primeiro framework eficiente para multiplicação esparsa matriz-vetor (SpMV) com preservação de privacidade usando criptografia homomórfica, introduzindo o formato CSSC para otimizar o processamento e reduzir significativamente o custo computacional e de armazenamento em dados sensíveis.

O essencial

Imagine que você tem um livro de receitas gigante (uma matriz) e uma lista de ingredientes (um vetor). O objetivo é calcular o custo total de fazer várias receitas ao mesmo tempo.

Normalmente, esse livro de receitas é "esparso". Isso significa que a maioria das páginas está em branco! Você só precisa somar os ingredientes que realmente existem. Se você tentar somar todos os zeros, vai perder um tempo terrível e gastar muita energia.

Agora, imagine que essa receita é um segredo de estado. Você não pode mostrar o livro de receitas ou a lista de ingredientes para ninguém, nem mesmo para o cozinheiro (o servidor na nuvem) que vai fazer a conta. Você precisa que ele faça a matemática sem nunca ver os números reais.

É aqui que entra a Criptografia Homomórfica (HE). É como uma caixa de vidro mágica e blindada. Você coloca os ingredientes dentro, o cozinheiro mexe a caixa (faz a conta) e, quando você abre, o resultado está lá, mas o cozinheiro nunca viu o que estava dentro.

O Problema:
Os métodos antigos de fazer essa conta com a caixa blindada eram como tentar ler um livro de receitas onde todas as páginas (mesmo as em branco) foram preenchidas com zeros para caber na caixa. O cozinheiro gasta horas somando zeros, a caixa fica pesada demais e o processo é lentíssimo. Além disso, os formatos antigos de organizar esses dados (como CSR ou CSC) não funcionam bem dentro dessa caixa mágica, exigindo que o cozinheiro gire a caixa milhares de vezes para encontrar o ingrediente certo.

A Solução do Artigo: O Formato "CSSC"
Os autores criaram um novo jeito de organizar o livro de receitas, chamado CSSC (Coluna Ordenada Compacta Esparsa). Pense nisso como uma reorganização inteligente do armário:

1. Limpeza e Ordenação: Eles reorganizam o livro para que as receitas com mais ingredientes fiquem juntas e os espaços vazios sejam empurrados para o lado, criando uma estrutura limpa.
2. Empilhamento Perfeito: Em vez de tentar encaixar tudo de qualquer jeito, eles organizam os ingredientes de forma que, quando colocados na caixa blindada, cada ingrediente da receita se alinha perfeitamente com o ingrediente correspondente da lista de compras.
3. O "Truque" da Caixa: Graças a essa organização, o cozinheiro (o servidor) só precisa fazer uma multiplicação mágica para cada par de ingredientes que realmente importa. Ele não precisa girar a caixa milhares de vezes nem somar zeros inúteis.

Como funciona na prática?

• Cliente A (dono da receita) pega o livro, faz essa reorganização inteligente, coloca os números na caixa blindada e manda para a nuvem. Ele envia apenas um "mapa" (que não revela os valores, apenas a estrutura) para o Cliente B.
• Cliente B (dono da lista de compras) usa esse mapa para reorganizar sua lista de ingredientes, coloca na caixa blindada e manda para a nuvem.
• O Servidor (Nuvem) recebe as duas caixas. Como os ingredientes estão perfeitamente alinhados graças ao formato CSSC, ele faz a conta rapidamente, somando apenas o que importa.
• Resultado: O servidor devolve a caixa com o resultado final. Os clientes abrem e veem o custo total, sem que o servidor tenha aprendido nada sobre as receitas ou os preços.

Os Resultados Mágicos:
Os testes mostraram que essa nova abordagem é absurdamente mais rápida (até 5.000 vezes mais rápida em alguns casos) e usa muito menos memória do que os métodos antigos.

• Velocidade: É como trocar de andar a pé para usar um foguete.
• Memória: Em vez de carregar um caminhão cheio de areia (zeros inúteis), você carrega apenas uma mochila com os ingredientes reais.

Por que isso importa?
Isso abre portas para o futuro da privacidade. Imagine fazer diagnósticos médicos em hospitais diferentes sem que os dados dos pacientes saiam dos seus computadores, ou analisar dados financeiros de bancos rivais sem que eles revelem seus segredos. O CSSC torna possível fazer essas contas complexas de forma rápida e segura, mesmo com dados que têm muitos "espaços vazios".

Em resumo: Eles inventaram um novo formato de "embalagem" para dados secretos que permite que computadores façam contas complexas em segredo, sem desperdiçar tempo somando zeros, tornando a privacidade na nuvem uma realidade prática e rápida.

Resumo técnico

Título: Multiplicação Eficiente de Matriz-Vetor Esparsa Preservando Privacidade Usando Criptografia Homomórfica

1. Problema e Motivação

A multiplicação de matriz-vetor esparsa (SpMV) é uma operação fundamental em computação científica, análise de dados e aprendizado de máquina. No entanto, em muitos cenários (como registros médicos, transações financeiras ou dados de simulação proprietária), os dados são sensíveis, exigindo proteção de privacidade rigorosa.

A Criptografia Homomórfica (HE) permite realizar cálculos sobre dados criptografados sem descriptografá-los, garantindo confidencialidade. Apesar disso, a aplicação da HE ao SpMV enfrenta desafios críticos:

• Incompatibilidade de Formatos: Formatos esparsos clássicos (CSR, CSC, COO) são projetados para computação em texto claro. Quando aplicados diretamente à HE, eles exigem operações desnecessárias sobre elementos zero, inflam o custo de armazenamento e degradam drasticamente o desempenho devido à necessidade excessiva de rotações e adições de ciphertexts (textos cifrados).
• Falta de Otimização Específica: Métodos existentes de HE focam em matrizes densas ou assumem que a matriz está em texto claro (modelo plaintext-ciphertext), o que não atende a cenários onde ambos a matriz e o vetor devem permanecer criptografados (modelo ciphertext-ciphertext) para máxima privacidade.

2. Metodologia Proposta

Os autores propõem o primeiro framework que integra eficientemente a HE com SpMV, introduzindo uma nova estrutura de dados e um pipeline de computação otimizado.

A. Novo Formato de Matriz: CSSC (Compressed Sparse Sorted Column)
Para resolver a incompatibilidade entre formatos esparsos e HE, foi desenvolvido o formato CSSC. As etapas de transformação incluem:

1. Reordenação de Linhas: As linhas da matriz são reordenadas em ordem decrescente baseada no número de elementos não nulos (NNZ).
2. Alinhamento à Esquerda: Os elementos não nulos de cada linha são deslocados para a esquerda, preservando suas posições originais de coluna.
3. Extração em Ordem de Coluna: Os dados são extraídos em ordem de coluna (column-major), gerando quatro componentes:
   • VA (Value Array): Valores não nulos.
   • CI (Column Index): Índices de coluna originais.
   • RM (Row Map): Mapeamento das linhas originais para a nova ordem.
   • CP (Column Pointer): Ponteiros para o início de cada coluna.

B. Pipeline de Computação Segura
O sistema opera em um modelo de três partes (Cliente A, Cliente B e Servidor Nuvem):

1. Cliente A (Matriz): Converte a matriz esparsa para o formato CSSC, criptografa o array de valores e envia para a nuvem. O array de índices de coluna (não criptografado) é enviado ao Cliente B.
2. Cliente B (Vetor): Reorganiza seu vetor denso com base nos índices recebidos do Cliente A, criptografa o vetor reorganizado e envia para a nuvem.
3. Servidor Nuvem:
   • Chunking: Divide a matriz criptografada em "chunks" (blocos) que cabem no tamanho de um único ciphertext.
   • Multiplicação: Realiza multiplicações ciphertext-ciphertext entre os chunks da matriz e o vetor reorganizado.
   • Agregação: Utiliza uma técnica de árvore binária (gadget totalSum) para somar os produtos parciais dentro de cada chunk e depois entre os chunks, minimizando a profundidade multiplicativa e o número de rotações.

C. Otimizações Chave

• Alinhamento de Slots: O CSSC alinha os elementos não nulos da matriz com os slots correspondentes do vetor criptografado, permitindo uma única multiplicação por par alinhado.
• Redução de Profundidade: O pipeline garante uma profundidade multiplicativa de apenas 1 (uma multiplicação ct-ct e uma ct-pt por par), mantendo o ruído baixo e evitando a necessidade de bootstrapping.
• Mascaramento: Uso de máscaras para eliminar slots preenchidos com zeros durante a agregação entre chunks de tamanhos diferentes.

3. Contribuições Principais

1. Primeiro Framework Ciphertext-Ciphertext para SpMV: Apresenta a primeira solução que realiza SpMV onde ambos a matriz e o vetor estão criptografados, garantindo confidencialidade de ponta a ponta.
2. Formato CSSC: Introduz um formato de matriz esparsa consciente de HE que resolve o desalinhamento dos formatos tradicionais (CSR/CSC), reduzindo drasticamente rotações e adições desnecessárias.
3. Pipeline de Baixa Profundidade e Lote: Desenvolveu um pipeline de ponta a ponta com chunking de ciphertexts, reorganização de vetores e agregação logarítmica, mantendo a profundidade multiplicativa fixa e amortizando custos através do processamento em lote.

4. Resultados Experimentais

Os experimentos foram realizados em um conjunto diversificado de matrizes esparsas reais (SuiteSparse Matrix Collection) usando o esquema BFV (128 bits de segurança).

• Desempenho (Tempo de Execução):
  • O método proposto alcançou acelerações (speedup) de 100x a mais de 5.000x em comparação com métodos de base (como diagonal, HEGMM, HETAL e Rhombus).
  • Em matrizes grandes (ex: p2p-Gnutella31), métodos concorrentes falharam em completar a tarefa em 3 dias, enquanto o método proposto terminou em minutos.
• Eficiência de Memória:
  • Redução de uso de memória de 2,4x a 18x em comparação com as melhores alternativas.
  • A compactação do CSSC e a estratégia de chunking evitam a inflação de memória causada pelo preenchimento de slots vazios em abordagens densas.
• Complexidade:
  • A análise teórica e empírica confirma que o tempo de execução na nuvem escala linearmente com o número de elementos não nulos (NNZ), com complexidade de agregação de $O(n_{ct} \cdot \log C_{max})$.

5. Significado e Impacto

Este trabalho preenche uma lacuna crítica na computação segura, permitindo a execução eficiente de SpMV em ambientes não confiáveis (como nuvens públicas) sem expor dados sensíveis.

• Aplicações Práticas: O framework viabiliza aplicações em aprendizado federado (onde modelos e dados são privados), bancos de dados criptografados e computação científica segura.
• Viabilidade: Demonstra que é possível realizar operações esparsas complexas com criptografia homomórfica sem sacrificar a privacidade ou enfrentar custos computacionais proibitivos, estabelecendo uma base para futuros sistemas de álgebra linear segura.

Em resumo, a proposta transforma a SpMV de um gargalo de desempenho em criptografia homomórfica em uma operação viável e escalável, através de uma reestruturação inteligente dos dados esparsos (CSSC) e otimizações algorítmicas específicas para o modelo de ameaça ciphertext-ciphertext.