Resumo Técnico: Busca de Embedding Privada com Consultas Compactas Criptografadas sob Criptografia Totalmente Homomórfica

Declaração do Problema

Na aprendizagem automática preservadora de privacidade (PPML) utilizando Criptografia Totalmente Homomórfica (FHE), surge um gargalo crítico durante a inferência de modelos que dependem de entradas discretas, como Processamento de Linguagem Natural (NLP) e sistemas de recomendação. Esses modelos tipicamente começam com uma camada de embedding, que mapeia um índice discreto (ex: um token de palavra) para um vetor contínuo.

Sob FHE, o servidor não pode realizar o acesso padrão à memória baseado em um índice criptografado. Em vez disso, a busca deve ser realizada através de aritmética homomórfica. As abordagens existentes enfrentam um compromisso (trade-off):

1. Busca no lado do cliente: O cliente envia o vetor de embedding criptografado. Isso acarreta um overhead de comunicação massivo proporcional à dimensão do embedding ($d$), o que é proibitivo para tabelas grandes (ex: GloVe com 1,9M de tokens).
2. Busca no lado do servidor com Geração de One-Hot: O cliente envia um índice escalar compacto criptografado. O servidor deve então construir homomorficamente um vetor one-hot para selecionar o embedding. Trabalhos anteriores (Kim et al., ICML 2024) alcançam isso usando uma Função Indicadora Criptografada (EIF), mas isso requer $O(p \log p)$ operações homomórficas (onde $p$ é o tamanho da tabela), consumindo uma profundidade multiplicativa significativa e tornando-se o custo dominante no pipeline de inferência.

O objetivo é alcançar uma Busca de Embedding Privada (PEL) que mantenha a comunicação compacta do cliente (enviando apenas um índice escalar) enquanto minimiza o custo de computação homomórfica no lado do servidor, evitando a etapa dispendiosa de geração de one-hot.

Metodologia: Avaliação de Vetor Independente (IVE)

Os autores propõem a Avaliação de Vetor Independente (IVE), um método que ignora completamente a construção de um vetor one-hot.

Insight Central

O servidor não exige estritamente um vetor one-hot ($e_j$) para recuperar o embedding $M_j$. Ele apenas requer uma representação do índice $j$ que seja linearmente independente entre diferentes índices. Se um conjunto de vetores $\{v_j\}$ é linearmente independente, existe uma matriz de mudança de base $L$ tal que $L v_j = e_j$. Consequentemente, a recuperação do embedding pode ser reescrita como:
$$M_j = M e_j = M (L v_j) = (M L) v_j$$
Como $M$ e $L$ são conhecidos em texto plano, o servidor pode pré-computar a matriz $M' = ML$. A tarefa online então muda de gerar um vetor one-hot para avaliar o vetor $v_j$ homomorficamente.

Construção de Vetor e Estabilidade

Para garantir eficiência e estabilidade numérica sob o esquema CKKS (que suporta aritmética aproximada):

1. Eficiência: Os vetores $v_j$ são construídos usando potências sucessivas de um único valor criptografado $\alpha_j$. Isso permite que o servidor gere os componentes do vetor usando operações aritméticas padrão (multiplicações) em vez de testes de igualdade complexos.
2. Estabilidade: Para evitar a amplificação de erro durante a mudança de base, a matriz $L$ deve ser bem condicionada (idealmente ortogonal). Os autores utilizam uma matriz de Transformada Discreta de Cosseno (DCT). Ao utilizar raízes da unidade e separar as partes real e imaginária, eles constroem uma base ortogonal que se alinha com as capacidades de aritmética complexa do CKKS.

Fluxo Algorítmico

1. Cliente: Criptografa o índice $j$ em um valor $\alpha_j$ (derivado de raízes da unidade) e o transmite como uma consulta escalar compacta.
2. Servidor (Fase IVE):
   • Recebe o $\alpha_j$ criptografado.
   • Computa as potências $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ usando uma árvore de multiplicação (profundidade logarítmica).
   • Separa as partes real e imaginária via conjugação para formar o vetor $v_j$.
   • Este processo requer $O(p)$ operações homomórficas, uma redução significativa em relação ao $O(p \log p)$ exigido pela geração de one-hot.
3. Servidor (Fase PCMM):
   • Realiza uma Multiplicação de Matriz Texto-Plano-Criptografia (PCMM) entre a matriz pré-computada $M' = ML$ e o vetor gerado $v_j$.
   • Isso resulta no vetor de embedding criptografado.

Principais Contribuições

1. Avaliação de Vetor Independente (IVE): Um novo algoritmo que substitui a geração de one-hot criptografada pela avaliação de uma família de vetores linearmente independentes. Isso reduz a complexidade de geração de vetores de $O(p \log p)$ para $O(p)$ operações homomórficas.
2. Base Ortogonal via DCT: A instanciação do IVE usando uma matriz ortogonal baseada em DCT garante estabilidade numérica, mitigando a amplificação de erro inerente à aproximação CKKS ao realizar a mudança de base.
3. Pipeline PEL Integrado: Os autores integram o IVE com o PCMM para lidar com consultas em lote (batch) de forma eficiente. Este pipeline suporta múltiplas consultas de tokens simultaneamente, amortizando o custo através dos slots SIMD do CKKS.
4. Implementação de Ponta a Ponta: O método é implementado dentro de um pipeline de classificação de texto estilo FastText, demonstrando sua viabilidade para tarefas de inferência práticas e sensíveis à privacidade.

Resultados Experimentais

Os autores avaliaram o IVE-PEL contra o estado da arte anterior (Kim et al.) usando três conjuntos de dados de embedding (GloVe.6B.50d, GloVe.42B.300d e GPT-2) e uma inferência FastText de ponta a ponta no dataset Enron-Spam.

• Aceleração na Geração de Vetor: O IVE-PEL reduz significativamente o tempo gasto na geração de vetores. Para um tamanho de subtabela de $\log p = 10$, o tempo de VecGen caiu de ~424 ms (Kim et al.) para ~3,15 ms (IVE-PEL) no GloVe.6B.50d, representando uma aceleração de 134,6× nesta etapa específica.
• Aceleração do Pipeline Total: O tempo de busca amortizado melhorou de 18,5× a 78,4× dependendo do dataset e da dimensão do embedding. Os maiores ganhos foram observados em cenários onde a geração de vetor era o custo dominante.
• Profundidade Multiplicativa: O IVE-PEL consome aproximadamente 1/3 da profundidade multiplicativa exigida pelo método de geração de one-hot, permitando tamanhos de subtabela maiores e melhor qualidade de compressão sem esgotar o orçamento de ruído do CKKS.
• Impacto de Ponta a Ponta: Na tarefa de classificação Enron-Spam, substituir o método one-hot pelo IVE reduziu a participação da geração de vetor no tempo total de inferência criptografada de 99,6% para 66,3%, reduzindo substancialmente a latência geral.

Significância e Alegações

O artigo afirma que o IVE-PEL aborda o "ponto de design ausente" na busca de embedding privada: alcançar comunicação compacta do cliente (índices escalares) sem incorrer no custo proibitivo de geração de one-hot homomórfica no lado do servidor.

Ao desacoplar a necessidade de uma base one-hot do processo de recuperação, os autores demonstram que a busca de embedding privada pode ser tornada prática para clientes leves e modelos de grande escala. Os resultados sugerem que o IVE-PEL torna a busca de embedding no lado do servidor uma alternativa viável, permitindo inferência preservadora de privacidade eficiente para modelos de NLP e sistemas de recomendação sem sacrificar a confidencialidade dos índices de entrada do usuário. O método mantém a precisão dos modelos subjacentes (como evidenciado pelos resultados de classificação de sentimento IMDB e detecção de spam) enquanto melhora drasticamente a eficiência computacional.