Resumo Técnico: HE-LRM

Definição do Problema

A Criptografia Totalmente Homomórfica (FHE) permite a inferência neural preservando a privacidade em dados criptografados, mas as soluções existentes abordam principalmente modelos com entradas densas (ex: CNNs, MLPs). Os Modelos de Recomendação de Aprendizado Profundo (DLRMs) apresentam um desafio distinto devido à sua dependência de entradas categóricas esparsas e massivas, processadas através de tabelas de embeddings gigantescas.

Em um DLRM padrão, recursos esparsos são mapeados para vetores densos via consultas em tabelas de embedding. Em um contexto de FHE (especificamente usando o esquema CKKS), o endereçamento direto não é suportado nativamente; apenas adição SIMD, multiplicação e rotação cíclica estão disponíveis. Abordagens ingênuas para consultas criptografadas enfrentam sérios problemas de escalabilidade:

1. Sobrecarga de Comunicação: Uma codificação "one-hot" de um índice para uma tabela com $k$ linhas requer um vetor de tamanho $k$. Para conjuntos de dados de escala industrial como o Criteo (33,8 milhões de linhas), isso exige o upload de mais de 1.000 criptogramas (>1 GiB) por inferência.
2. Custos de Computação no Servidor: Trabalhos anteriores (ex: Kim et al. [10]) tentam mitigar os custos de upload fazendo com que o servidor construa o seletor one-hot a partir de um índice criptografado. No entanto, isso requer circuitos aritméticos profundos (funções indicadoras) que consomem uma profundidade multiplicativa significativa, muitas vezes necessitando de operações de bootstrapping dispendiosas.
3. Vazamento de Memória e Estrutura: Técnicas de compressão existentes frequentemente exigem que o cliente armazene mapeamentos de códigos aprendidos (revelando correlações de embedding) ou resultam em utilização ineficiente de slots e altas pegadas de memória no servidor.

Metodologia: HE-LRM

Os autores propõem o HE-LRM, um sistema FHE de ponta a ponta otimizado para a inferência de DLRM. A solução aborda o gargalo da consulta de embedding através de três inovações técnicas principais:

1. Compressão por Decomposição de Dígitos no Lado do Cliente

Em vez de depender da construção de vetores one-hot no lado do servidor ou de mapeamentos de códigos aprendidos que vazam estrutura, o HE-LRM emprega uma técnica de compressão determinística no lado do cliente baseada em decomposição de dígitos.

• Mecanismo: Uma tabela de embedding original de tamanho $k \times d$ é decomposta em $\ell$ tabelas menores de tamanho $p \times d$ (onde $k \approx p^\ell$).
• Processo: O cliente pega um índice categórico $i$ e o decompõe em uma tupla de dígitos de base-$p$ $(i_0, i_1, \dots, i_{\ell-1})$.
• Privacidade: O cliente constrói localmente as codificações one-hot para esses dígitos menores e as criptografa. O servidor nunca vê o índice original, nem precisa realizar funções indicadoras homomórficas caras. A compressão é aprendida de ponta a ponta durante o treinamento sem revelar a estrutura de mapeamento ao cliente.

2. Estratégia de Empacotamento Diagonal-Bloco

DLRMs tipicamente utilizam múltiplas tabelas de embedding (ex: 26 para Criteo). O HE-LRM introduz uma estratégia de empacotamento diagonal-bloco para lidar com elas simultaneamente.

• Implementação: Múltiplas tabelas de embedding são concatenadas diagonalmente em uma única matriz de pesos de grande porte.
• Benefício: Isso permite que o cliente concatene as codificações one-hot para todos os recursos em um único vetor. O servidor pode então realizar uma única multiplicação matriz-vetor Baby-Step Giant-Step (BSGS) para recuperar os embeddings de todas as tabelas em paralelo. Isso maximiza a utilização dos slots do criptograma e evita o overhead de processar tabelas sequencialmente.

3. Transformação Linear Otimizada

O sistema utiliza o algoritmo double-hoisted BSGS para a multiplicação matriz-vetor.

• Ao contrário das abordagens anteriores de "Table-Mult" que exigem rotações separadas para cada dimensão do vetor de embedding (consumindo níveis multiplicativos extras), a abordagem BSGS trata a consulta como uma transformação linear padrão.
• Isso reduz a operação para um único nível multiplicativo, eliminando a necessidade de bootstrapping intermediário durante a fase de consulta.

Principais Contribuições

1. Primeiro DLRM FHE de Ponta a Ponta: O HE-LRM é o primeiro sistema que suporta tanto recursos densos quanto esparsos em um DLRM sob FHE, validado nos conjuntos de dados UCI Heart Disease e Croleo.
2. Aceleração de 56×: A proposta de decomposição de dígitos no lado do cliente e a consulta BSGS alcança uma aceleração de 56× sobre o estado da arte (CodedHeLUT) para dimensões de embedding grandes (768). Isso é alcançado evitando funções indicadoras no lado do servidor, reduzindo o consumo de profundidade multiplicativa (de ~10 níveis para 1) e eliminando a necessidade de bootstrapping durante a fase de consulta.
3. Consulta de Múltiplas Tabelas em Paralelo: A estratégia de empacotamento diagonal-bloco permite consultas paralelas eficientes entre múltiplas tabelas de embedding, reduzindo significativamente o overhead de comunicação e computação em comparação ao processamento individual das tabelas.
4. Perfil de Vazamento Limpo: O método adere a um modelo de ameaça semi-honesto onde o cliente conhece apenas as dimensões de entrada e os tamanhos das tabelas, mas não aprende nada sobre os valores de embedding, correlações ou parâmetros do modelo.

Resultados Experimentais

Os autores avaliaram o HE-LRM usando o framework FHE de código aberto Orion em uma CPU de thread única (Intel Xeon Gold 5218).

• UCI Heart Disease: Alcançou uma latência de inferência de ponta a ponta de 24 segundos.
• Conjunto de Dados Criteo: Alcançou latências variando de 228 a 489 segundos, dependendo da razão de compressão (variando de $10\times$ a $10^5\times$).
  • Modelos altamente comprimidos ($\approx 10^3\times$ a $10^5\times$) mostraram latências semelhantes (~230s) porque o tempo de consulta de embedding tornou-se negligenciável (3–5 segundos) em comparação ao resto da rede, e a operação BSGS pôde ser realizada em um único criptograma.
  • Modelos menos comprimidos exigiram mais criptogramas, aumentando a latência do produto matriz-vetor.
• Projeções de Hardware:
  • GPU: Projeções usando o acelerador Cheddar sugerem uma aceleração de ~200× sobre a CPU, reduzindo a inferência do Criteo para aproximadamente 1 segundo.
  • ASIC: Projeções usando o modelo de custo Osiris sugerem latências de sub-segundo (~0,037 segundos) para modelos comprimidos.

Significância e Alegações

O artigo afirma que o HE-LRM preenche uma lacuna crítica na inferência privada, demonstrando que sistemas de recomendação preservando a privacidade estão próximos da implantação prática.

• Escalabilidade: O trabalho prova que o "gargalo de embedding" em FHE pode ser resolvido sem sacrificar a privacidade ou exigir que o cliente possua os pesos do modelo.
• Eficiência do Sistema: Ao deslocar a complexidade da codificação do índice para o cliente (via decomposição determinística) e utilizar álgebra linear eficiente (BSGS) no servidor, o sistema evita os custos proibitivos de bootstrapping e o enorme overhead de comunicação associado às codificações one-hot ingênuas.
• Aplicabilidade Ampla: Os autores observam que a primitiva de consulta de embedding criptografada não se limita a DLRMs, sendo também relevante para modelos baseados em Transformer, sugerindo uma abstração reutilizável para futuros sistemas de inferência privada.

Os autores mantêm-se modestos quanto ao desempenho atual da CPU (minutos para modelos grandes), enfatizando que as acelerações demonstradas em hardware GPU e ASIC são necessárias para a implantação em produção no mundo real.