💻 computer science

KeyMemRT Compiler and Runtime: Unlocking Memory-Scalable FHE

O KeyMemRT é um framework de compilador e tempo de execução baseado em MLIR que utiliza análise de fluxo de dados para gerenciar automaticamente os tempos de vida das chaves de rotação de FHE, reduzindo significativamente o consumo de memória e melhorando a velocidade de execução em comparação com os compiladores de estado da arte existentes.

Autores originais: Eymen Ünay, Björn Franke, Jackson Woodruff

Publicado 2026-01-27

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Eymen Ünay, Björn Franke, Jackson Woodruff

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando resolver um quebra-cabeça massivo e complexo, mas só tem permissão para manipular as peças usando uma venda nos olhos. Você tem que manipular as peças sem vê-las, usando um conjunto especial de regras que mantém o quebra-cabeça oculto de olhos curiosos. Isso é essencialmente o que a Criptografia Totalmente Homomórfica (FHE) faz: ela permite que computadores realizem cálculos sobre dados enquanto esses dados permanecem completamente criptografados.

No entanto, há um grande problema. Para fazer essa matemática "de olhos vendados", o computador precisa de uma biblioteca gigante de "chaves mágicas" especiais (chamadas de chaves de rotação).

O Problema: O "Acumulador de Chaves"

Pense nessas chaves mágicas como uma coleção massiva de chaves físicas para um hotel com milhares de quartos.

O Jeito Antigo (ANT-ACE): Imagine um gerente de hotel que, antes mesmo de um hóspede chegar, pega todas as chaves do prédio e as despeja todas na recepção. Mesmo que o hóspede precise apenas visitar o Quarto 101, o gerente mantém as chaves dos Quartos 102 até o 5.000 ali na mesa.
- O Resultado: A mesa (memória) fica entulhada e transbordando. Se o hotel for enorme, a mesa ficará tão cheia de chaves que não sobrará espaço para mais nada. O sistema trava ou fica lento porque está tentando gerenciar uma montanha de chaves desnecessárias.
O Jeito "Lento" (Fhelipe): Outro gerente tenta economizar espaço mantendo apenas algumas "chaves mestras". Para abrir o Quarto 101, ele não tem a chave direta, então precisa usar uma chave mestra para abrir o Quarto 1, depois outra para abrir o Quarto 2, e assim por diante, encadeando-as até chegar ao 101.
- O Resultado: A mesa fica organizada, mas o hóspede tem que esperar muito tempo enquanto o gerente se atrapalha com uma longa corrente de chaves. O processo é lento.

A Solução: KeyMemRT

Os autores deste artigo construíram um novo sistema chamado KeyMemRT. Pense nele como um serviço de concierge super inteligente e automatizado que gerencia as chaves perfeitamente.

Ele Sabe Exatamente o Que Você Precisa: Em vez de pegar todas as chaves de uma vez, o KeyMemRT analisa o itinerário do hóspede (o código do programa) para ver exatamente quais quartos eles visitarão e em que ordem.
Entrega "Na Hora Certa": Ele mantém a mesa limpa. Ele só traz a chave específica para o Quarto 101 logo antes de o hóspede precisar dela.
Limpeza Instantânea: Assim que o hóspede sai do Quarto 101, o concierge imediatamente pega aquela chave de volta e a guarda, abrindo espaço para a próxima chave.
O Truque do "Prefetch": Para garantir que o hóspede nunca tenha que esperar, o concierge começa a trazer a próxima chave enquanto o hóspede ainda está no quarto atual. Isso acontece em segundo plano, para que o processo pareça rápido e fluido.

O Que Eles Alcançaram?

Os pesquisadores testaram este novo sistema contra os métodos antigos usando várias tarefas complexas (como reconhecer imagens em exames médicos ou dados financeiros).

Economia de Memória: Comparado ao método do "Acumulador de Chaves" (ANT-ACE), o KeyMemRT reduziu a quantidade de memória necessária em 1,74 vezes. É como encaixar as chaves de um hotel inteiro em uma única maleta em vez de um armazém.
Velocidade: Comparado ao "Método da Corrente Lenta" (Fhelipe), o KeyMemRT foi 1,73 vezes mais rápido. Ele não apenas economizou espaço; ele também fez o trabalho acontecer muito mais rápido porque não perdeu tempo encadeando chaves.

Por Que Isso Importa?

Atualmente, a FHE é difícil de usar porque exige computadores com quantidades enormes de memória (centenas de gigabytes) apenas para conter essas chaves. Isso a torna cara e impraticável para muitos usos do mundo real.

O KeyMemRT atua como um tradutor e um controlador de tráfego. Ele pega códigos complexos e bagunçados e os otimiza para que possam ser executados em computadores padrão sem a necessidade de um supercomputador apenas para segurar as chaves. Ele torna a computação preservadora de privacidade (como analisar dados médicos ou financeiros sensíveis sem nunca ver os números brutos) mais escalável e eficiente.

Em resumo: Eles construíram um sistema inteligente que impede que programas de FHE acumulem chaves inúteis e impede que percam tempo criando chaves do zero, permitindo que a computação privada rode de forma mais rápida e em máquinas menores e mais baratas.

Resumo Técnico: Compilador e Runtime KeyMemRT

Declaração do Problema

A Criptografia Totalmente Homomórfica (FHE) permite o processamento preservando a privacidade em dados criptografados, mas enfrenta barreiras significativas para a adoção no mundo real devido aos excessivos requisitos computacionais e de memória. Um gargalo primário é o gerenciamento de chaves de rotação. Em esquemas FHE com lote (ex: CKKS, BGV, BFV), operações de rotação são essenciais para computações intra-vetoriais e bootstrapping. No entanto, esses esquemas exigem uma chave de rotação única para cada índice de rotação específico.

À medida que os programas FHE escalam, o número de índices de rotação necessários cresce, muitas vezes exigindo centenas de gigabytes ou até terabytes de memória para armazenar todas as chaves simultaneamente. Os compiladores FHE existentes geralmente tratam as chaves de rotação como uma entidade única e estática, carregando todas as chaves na memória durante toda a execução do programa. Essa abordagem carece de escalabilidade de memória. Por outro lado, estratégias existentes que tentam reduzir a memória, como o Fhelipe, baseiam-se na decomposição de índices de rotação arbitrários em cadeias de potências de dois. Embora isso reduza o número de chaves armazenadas, aumenta significativamente a latência computacional devido ao overhead de encadeamento. Há uma carência de compiladores que ofereçam um gerenciamento de chaves automático e de granularidade fina para equilibrar o uso de memória e a velocidade de execução.

Metodologia

Os autores apresentam o KeyMemRT, um framework de compilador e runtime projetado para gerenciar os tempos de vida das chaves de rotação individualmente. O sistema é construído sobre a infraestrutura MLIR (Multi-Level Intermediate Representation) e introduz um novo dialeto e arquitetura de runtime.

1. O Dialeto MLIR `kmrt`

O KeyMemRT introduz um novo dialeto chamado kmrt para representar o gerenciamento de chaves diretamente no IR.

Novos Tipos: Ele define um tipo rot_key parametrizado pelo índice de rotação, permitindo que o compilador distinga entre chaves para diferentes índices.
Novas Operações: O dialeto inclui operações para gerenciamento explícito de chaves:
- kmrt.load_key: Carrega uma chave de rotação específica.
- kmrt.clear_key: Remove uma chave da memória.
- kmrt.prefetch_key: Fornece dicas ao runtime para carregamento assíncrono.
- kmrt.use_key / kmrt.assume_key: Gerenciam o escopo e a vivacidade (liveness) da chave.
Integração: O compilador reduz operações de alto nível (ex: do dialeto ckks via HEIR) para o dialeto openfhe, inserindo operações kmrt para gerenciar os ciclos de vida das chaves.

2. Pipeline de Otimização do Compilador

O compilador KeyMemRT realiza uma série de passagens de redução (lowering) e otimização para reduzir a pegada de memória sem sacrificar o desempenho:

Redução de CKKS para OpenFHE: Associa cada operação de rotação a um valor rot_key específico, invertendo o problema de criar intervalos de vivacidade para fundir esses intervalos.
Decomposição Baby-Step Giant-Step (BSGS): Reduz o número de chaves necessárias de $N$ para $\approx 2\sqrt{N}$ para índices de rotação consecutivos através do encadeamento de rotações. Isso é particularmente eficaz para padrões de multiplicação matriz-vetor.
Fusão de Chaves de Rotação (Merge Rotation Keys): Utiliza análise de fluxo de dados para detectar sequências onde uma chave é limpa e imediatamente recarregada com o mesmo índice, removendo pares redundantes de load/clear.
Elevação de Rotação (Rotation Hoisting): Identifica padrões de rotação aplicados a entradas comuns e os transforma em alternativas mais rápidas suportadas pela biblioteca OpenFHE.
Gerenciamento de Chave de Bootstrap: Materializa as chaves de rotação internas usadas por operações de bootstrap (que atualizam os níveis do texto cifrado) no IR. Isso permite que o compilador gerencie as chaves de bootstrap com o mesmo controle granular que as chaves de rotação explícitas, um recurso anteriormente não abordado.
Eliminação de Subexpressão Comum (CSE): Remove código morto resultante das otimizações de chave.
Posicionamento de Dicas (Hint Placement): Insere dicas de prefetch_key para permitir que o runtime sobreponha o carregamento de chaves com a computação.

3. Runtime KeyMemRT

O runtime atua como um intermediário entre o código C++ compilado e a biblioteca FHE (OpenFHE). Ele gerencia o carregamento e descarregamento dinâmico de chaves do disco para a RAM com base nas dicas inseridas pelo compilador.

Modo de Baixa Memória (Low-Memory Mode): Executa as diretivas sequencialmente, carregando as chaves apenas quando estritamente necessário para minimizar o uso de memória de pico.
Modo Equilibrado (Balanced Mode): Utiliza um mecanismo de prefetching para carregar chaves em paralelo com a computação. Mantém uma fila interna, carregando chaves antecipadamente até um limite definido pelo usuário e limpando-as quando o espaço é necessário, reduzendo assim o overhead de latência.

Principais Contribuições

Novo Dialeto MLIR (kmrt): O primeiro dialeto a expor chaves de rotação como elementos de IR com tipos específicos e operações de gerenciamento de memória, permitindo análise de granularidade fina.
Gerenciamento Automático de Chaves de Granularidade Fina: O primeiro compilador FHE a rastrear automaticamente a vivacidade das chaves, otimizar chaves de bootstrap e gerenciar os tempos de vida das chaves individualmente, em vez de como um conjunto global.
Framework de Runtime: Um runtime que suporta o carregamento e a limpeza sob demanda de chaves, utilizando dicas do compilador para sobrepor E/S (I/O) com computação.
Integração: Um toolchain de compilador pós-otimização que pode ser alvo de frontends FHE existentes (demonstrado com Orion e HEIR).

Resultados

Os autores avaliaram o KeyMemRT contra duas abordagens de última geração: ANT-ACE (que mantém todas as chaves na memória) e Fhelipe (que utiliza decomposição para reduzir chaves, mas aumenta a latência). Os benchmarks incluíram vários modelos de ML (MLP, LoLa, LeNet, variantes de ResNet, AlexNet) com parâmetros FHE definidos com uma dimensão de anel de $2^{16}$ e profundidade multiplicativa de 30.

Redução de Memória:
- Comparado ao ANT-ACE, o KeyMemRT alcançou uma redução de memória de média geométrica de 1.74x. Em casos específicos como o LeNet, o uso de memória foi reduzido em 2.59x.
- Comparado ao Fhelipe, o KeyMemRT alcançou uma redução de memória de 1.16x.
Latência/Aceleração (Speedup):
- Comparado ao ANT-ACE, o KeyMemRT (modo Balanced) alcançou um aumento de velocidade de 1.20x.
- Comparado ao Fhelipe, o KeyMemRT alcançou uma aceleração significativa de 1.73x (média geométrica), com melhorias de até 2.5x no AlexNet. Isso ocorre porque o KeyMemRT evita o overhead computacional de encadeamento de rotações exigido pelo Fhelipe.
Escalabilidade: O KeyMemRT demonstrou a capacidade de executar programas grandes (ex: ResNet-50) que excediam os requisitos de 100 GB de memória sob o ANT-ACE, mantendo o uso de memória significativamente menor.

Significância e Alegações

O artigo afirma que o KeyMemRT é o primeiro compilador FHE a fornecer gerenciamento automático e de granularidade fina de chaves e gerenciamento de chaves de bootstrap. Os autores afirmam que este trabalho desbloqueia a escalabilidade de memória para FHE, permitindo que programas arbitrariamente grandes sejam executados sem o ônus proibitivo de armazenar todas as chaves de rotação simultaneamente.

Ao desacoplar o uso de memória do número total de chaves e, em vez disso, gerenciar as chaves com base em sua vivacidade, o KeyMemRT permite que programas FHE escalem melhor em hardware existente. Os autores enfatizam que sua abordagem não compromete o desempenho; ao contrário dos métodos baseados em decomposição que trocam memória por velocidade, o KeyMemRT alcança tanto a redução de memória quanto a melhoria de latência, carregando apenas as chaves necessárias no momento exato em que são necessárias. Isso aborda uma barreira crítica para a adoção de FHE.