💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

Este artigo apresenta o Sparse Roots of Unity (SPRU), um novo algoritmo de bootstrapping para o esquema de criptografia homomórfica CKKS que incorpora aritmética modular em raízes da unidade complexas para reduzir significativamente a profundidade multiplicativa e alcançar uma melhoria de até 5x na latência em comparação com métodos tradicionais.

Autores originais: Jean-Sebastien Coron, Robin Koestler

Publicado 2026-07-31

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Jean-Sebastien Coron, Robin Koestler

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 enviar uma mensagem secreta para um amigo, mas não pode confiar nos correios. Você tranca sua carta em uma caixa, mas os correios precisam triá-la, empilhá-la e talvez até abri-la para verificar o endereço sem nunca ver o que está dentro. Isso é a magia da Criptografia Totalmente Homomórfica (FHE). Ela permite que computadores realizem cálculos sobre dados que ainda estão em sua forma criptografada. Pense nisso como uma cozinha mágica onde você pode assar um bolo usando ingredientes que ainda estão em suas embalagens lacradas e fechadas; o forno faz o trabalho, e quando você finalmente abre a caixa no final, você tem um bolo fresco, mas o forno nunca soube quais eram os ingredientes.

No entanto, há um porém. Cada vez que o computador realiza uma operação matemática nesses dados trancados, um pouco de "ruído" ou estática é adicionado à caixa, como poeira assentando sobre uma lente. Se você fizer muitos cálculos, o ruído ficará tão alto que a mensagem se tornará confusa e ilegível. Para corrigir isso, os cientistas usam um processo chamado bootstrapping. É como um botão de reset mágico: o computador pega a caixa trancada e ruidosa, realiza um truque complexo para limpar a poeira e coloca a mensagem de volta em uma caixa nova e limpa para que os cálculos possam continuar. O problema é que esse truque de limpeza é incrivelmente lento e pesado, como tentar lavar um carro com uma escova de dentes. Ele exige tanto poder de computação que torna tudo mais lento, fazendo com que as aplicações do mundo real pareçam lentas.

É aqui que um novo artigo de Jean-Sébastien Coron e Robin Köstler entra em cena. Eles introduzem uma nova maneira inteligente de realizar esse processo de "limpeza", chamada bootstrapping de Raízes da Unidade Esparsas (SPRU). Em vez de usar o método antigo, pesado, que tenta aproximar uma curva complexa (como uma onda senoidal), eles descobriram uma maneira de mapear os dados diretamente em um círculo de números chamados "raízes da unidade". Imagine que, em vez de esfregar o carro com uma escova de dentes, você apenas desliza o carro para um carrossel gigante que naturalmente limpa a poeira enquanto gira. O método deles é muito mais rápido e leve, especialmente quando você está lidando com um pequeno número de itens de dados de uma só vez. Ao usar essa nova abordagem, eles mostraram que o tempo necessário para resetar a criptografia pode ser reduzido em até 5 vezes em comparação ao método padrão, fazendo com que a magia da computação secreta pareça muito mais uma realidade do que um sonho distante.

O Jeito Antigo: O Carregador de Peso

Para entender por que esse novo truque é tão especial, vamos observar como o método antigo funcionava. No esquema de criptografia CKKS padrão (o mais popular para fazer matemática com decimais), o processo de bootstrapping era como tentar adivinhar a forma de uma montanha desenhando uma linha suave sobre ela. O computador tinha que avaliar um polinômio complicado (uma fórmula matemática sofisticada) que aproximava uma "redução modular". Pense na redução modular como uma forma de envolver uma linha numérica longa em um círculo para que ela caiba de volta em uma caixa pequena. O método antigo tentava desenhar uma onda senoidal (uma linha ondulada) para imitar esse processo de envolvimento.

Embora isso funcionasse, era um esforço pesado. Exigia uma pilha profunda de operações matemáticas, o que significava que o computador tinha que usar uma "dimensão de anel" muito grande (uma medida do tamanho do parquinho matemático). Isso era como tentar correr uma maratona carregando uma mochila pesada; isso atrasava tudo e limitava quanto trabalho útil poderia ser feito após o reset. Os autores apontam que essa alta "profundidade multiplicativa" (o número de camadas de matemática pelas quais você tem que passar) era o principal gargalo, tornando o processo muito lento para uso prático, especialmente quando você só precisa processar alguns números de cada vez.

O Novo Jeoco: O Carrossel de Raízes

A nova ideia dos autores, o bootstrapping SPRU, muda o jogo ao pular a aproximação pesada inteira. Em vez de tentar desenhar uma linha ondulada para imitar o envolvimento, eles perceberam que poderiam simplesmente incorporar os dados diretamente nas "raízes da unidade".

Aqui está uma analogia simples: Imagine que o método antigo era como tentar traduzir um código secreto escrevendo uma entrada de dicionário longa e complicada para cada letra. Demorava muito. O novo método é como perceber que o código secreto é, na verdade, um conjunto de chaves que se encaixam perfeitamente em uma fechadura específica. Em vez de traduzir, você apenas gira a chave.

Em termos técnicos, eles mapeiam o grupo aditivo (a forma como os números se somam) diretamente nas raízes da unidade complexas (pontos em um círculo no sistema de números complexos). Como o esquema de criptografia CKKS entende nativamente esses números complexos, o computador pode realizar a operação de "limpeza" diretamente, sem a necessidade de aproximar uma onda senoidal. É como mudar de construir uma ponte feita de tijolos individuais para usar um arco pré-fabricado que se encaixa perfeitamente.

O Ingrediente Secreto: Esparsidade e Empacotamento

O artigo não se limita apenas ao novo mapa; eles também introduziram duas otimizações inteligentes para torná-lo ainda mais rápido, especialmente ao lidar com um pequeno número de slots de dados (como alguns números em uma lista).

Empacotando os Bits: Nos velhos tempos, se você tivesse uma chave secreta de 1.000 bits, o computador teria que lidar com cada bit um por um. Os autores perceberam que poderiam "empacotar" esses bits nos slots da criptografia, como colocar 1.000 cartas em uma única caixa de correio super eficiente. Isso reduziu o número de cálculos pesados necessários de uma quantidade massiva para uma quantidade logarítmica (pense nisso como reduzir uma lista longa para um resumo curto).
O Truque do Bloco Esparso: Eles também assumiram que a chave secreta tinha uma estrutura especial: em vez de bits aleatórios, a chave era dividida em blocos onde apenas um bit em cada bloco era "1" e o restante eram "0". Isso é como ter uma fileira de interruptores de luz onde apenas um está ligado em cada grupo de dez. Ao usar essa estrutura "esparsa", eles pudreram substituir muitas etapas de multiplicação difíceis por etapas simples de adição. É a diferença entre multiplicar uma longa lista de números e apenas somar alguns deles. Isso reduziu a "profundidade" do cálculo ainda mais, de uma torre alta para uma pequena escada.

Os Resultados: Acelerando a Magia

Os autores testaram seu novo método usando a biblioteca OpenFHE, uma ferramenta popular para construir software de criptografia. Eles compararam o bootstrapping SPRU com o método antigo e pesado.

Os resultados foram impressionantes para cenários específicos. Ao realizar o bootstrapping de criptogramas com um pequeno número de slots (o que é comum em muitas aplicações do mundo real), o novo método deles foi até 5 vezes mais rápido (uma redução de 5x na latência). Isso é um grande feito porque significa que o "botão de reset" não precisa esperar tanto tempo, permitindo que o computador volte a fazer trabalho útil muito mais rápido.

No entanto, o artigo observa cuidadosamente que isso não é uma solução mágica para todas as situações. Se você estiver tentando processar um número massivo de slots (uma lista enorme de dados), o método original pode ainda ser mais eficiente. Mas para os muitos casos em que lidamos com lotes menores de dados, essa nova abordagem oferece uma aceleração significativa.

Por Que Isso Importa

A beleza deste trabalho é que ele não apenas ajusta os números; ele muda fundamentalmente a forma como pensamos sobre o processo de bootstrapping. Ao se afastar das aproximações polinomiais pesadas e abraçar as capacidades nativas do esquema de criptografia, os autores mostraram que podemos tornar a criptografia totalmente homomórfica muito mais prática.

Eles provaram que, ao usar essas "raízes da unidade" e técnicas de empacotamento inteligente, podemos reduzir significamente o tempo e o poder de computação necessários para manter os dados criptografados utilizáveis. Embora o artigo foque nos detalhes técnicos e na matemática por trás das cenas, a conclusão é clara: podemos tornar a computação de dados secretos muito mais prática. Eles forneceram uma maneira mais leve e rápida de manter a magia viva, tornando possível imaginar um futuro onde seus dados privados podem ser processados na nuvem sem nunca serem vistos, e sem esperar eternamente pelo resultado.

Resumo Técnico: Bootstrapping de Baixa Latência para CKKS usando Raízes da Unidade

Declaração do Problema

O esquema de criptografia homomórfica CKKS suporta aritmética aproximada em números complexos, tornando-o adequado para aprendizado de máquina seguro e computação em nuvem. No entanto, um gargalo crítico no CKKS é o procedimento de bootstrapping, que é necessário para atualizar os criptogramas e permitir uma profundidade de computação ilimitada.

O método original de bootstrapping do CKKS [CHK+18a] baseia-se na avaliação homomórfica de uma aproximação polinomial da função de redução modular (especificamente, uma função seno escalonada). Esta abordagem sofre de dois principais inconvenientes:

Alta Profundidade Multiplicativa: A aproximação polinomial requer um circuito profundo, necessitando de um módulo de criptograma grande.
Ineficiência para Pequenas Contagens de Slots: A complexidade do método original escala com o número de slots ( $n$ ) e a dimensão do anel ( $N$ ), frequentemente exigindo $O(\log n + \log N)$ operações. Esta alta profundidade força o uso de dimensões de anel maiores para manter a segurança, levando ao aumento da latência.

Os autores identificam a necessidade de um algoritmo de bootstrapping que reduza a profundidade multiplicativa, permitindo assim dimensões de anel menores e uma latência significativamente inferior, particularmente para criptogramas com um pequeno número de slots.

Metodologia: Raízes da Unidade Esparsas (SPRU)

O artigo introduz o bootstrapping por Raízes da Unidade Esparsas (SPRU), um novo algoritmo que altera fundamentalmente a forma como a redução modular é realizada no CKKS.

Conceito Central: Embedding Nativo

Em vez de aproximar a redução modular via uma função seno, o bootstrapping SPRU incorpora diretamente o grupo aditivo $\mathbb{Z}_q$ no grupo multiplicativo das raízes da unidade complexas. Os autores utilizam o homomorfismo:
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

Para uma equação de decriptação do tipo LWE $m = \langle s, c \rangle \pmod q$ , os autores observam que:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
Como os bits da chave secreta $s_k \in \{0, 1\}$ atuam como seletores, este produto pode ser reescrito como:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
Ao isolar a parte imaginária e aplicar um fator de escala linear, a mensagem original $m$ pode ser recuperada. Esta equação pode ser avaliada homomorficamente dentro do esquema CKKS sem a aproximação polinomial da função seno.

Principais Otimizações

Para tornar esta abordagem prática, os autores introduzem duas otimizações críticas:

Empacotamento de Bits da Chave Secreta:
Em vez de criptografar cada bit da chave secreta individualmente, os $N$ bits são empacotados nos $N/2$ slots de dois criptogramas CKKS. Os termos $(\exp(2i\pi \cdot c_k/q) - 1)$ são similarmente empacotados. O produto destes termos é computado usando o Operador de Produto ( $Pr_{N/2 \to 1}$ ), que reduz o número de multiplicações homomórficas de $O(N)$ para $O(\log N)$ .
Chave Secreta de Bloco Esparso:
Os autores assumem uma chave secreta estruturada $s$ dividida em $h$ blocos de tamanho $B = N/h$ , onde cada bloco contém exatamente um bit não nulo (um '1'). Esta estrutura permite que o produto dentro de cada bloco seja substituído por uma soma.
- A soma dentro dos blocos é computada usando o Operador de Traço ( $Tr_{N/2 \to h}$ ), que envolve apenas adições e automorfismos (sem profundidade multiplicativa).
- O produto final é tomado sobre os $h$ resultados dos blocos.
- Resultado: A profundidade multiplicativa é reduzida de $\log_2 N + 2$ para $\log_2 h + 1$ . Como $h \ll N$ , isto reduz significativamente o tamanho do módulo necessário.

Extensão para Múltiplos Slots

O método é generalizado para lidar com $n$ slots (onde $n \le N/2$ ). A matriz de decriptação é extraída e a equação de bootstrapping é aplicada em paralelo a cada um dos $n$ componentes da mensagem. A complexidade é $O(n + \log N)$ , que é assintoticamente superior ao bootstrapping original do CKKS ( $O(\log n + \log N)$ ) para grandes $n$ . No entanto, para pequenos $n$ , a redução da profundidade multiplicativa produz um desempenho prático superior.

Principais Contribuições

Algoritmo de Bootstrapping SPRU: Uma nova técnica de bootstrapping para CKKS que substitui a aproximação da função seno pela avaliação nativa de raízes da unidade.
Redução da Profundidade Multiplicativa: Ao alavancar chaves secretas de blocos esparsos e o operador de traço, o algoritmo alcança uma profundidade multiplicativa de $O(\log h)$ , significativamente menor que o $O(\log N)$ do método original.
Implementação Otimizada: Os autores fornecem uma implementação de código aberto usando a biblioteca C++ OpenFHE, demonstrando compatibilidade com aritmética de Sistema de Número Residuo (RNS) e otimizações existentes de transformação linear (SlotToCoeff).
Análise de Segurança: Uma análise formal da distribuição da chave binária de bloco, mostrando que não enfraquece a segurança do problema RLWE contra ataques conhecidos (ataques híbridos duais e meet-in-the-middle), desde que os parâmetros sejam ajustados corretamente.

Resultados

Os autores testaram o bootstrapping SPRU contra o bootstrapping original do CKKS usando a biblioteca OpenFHE com parâmetros de segurança de 128 bits.

Redução de Latência: Para criptogramas com um pequeno número de slots, o bootstrapping SPRU alcança uma redução de até 5x na latência.
Eficiência: A redução na profundidade multiplicativa permite o uso de dimensões de anel menores, contribuindo ainda mais para o aumento de velocidade.
Paralelismo: O método é altamente paralelizável; com $n$ processadores, pode atingir uma complexidade $O(\log N)$ comparável ao método original.

Significância e Alegações

O artigo afirma que o bootstrapping SPRU oferece uma alternativa prática ao bootstrapping original do CKKS, visando especificamente cenários onde a baixa latência é crítica e o número de slots é pequeno. Ao evitar aproximações polinomiais dispendiosas e reduzir a profundidade multiplicativa, o método permite a atualização mais eficiente dos criptogramas.

Os autores posicionam o seu trabalho como um passo significativo para tornar a criptografia totalmente homomórfica mais viável para aplicações do mundo real que exigem bootstrapping frequente. Eles observam que, embora o seu método seja otimizado para contagens de slots pequenas, ele complementa o trabalho existente (como o trabalho independente de Cheon et al. [CHKS25] que se foca no bootstrapping de $N/2$ -slots completo) ao oferecer um compromisso diferente que favorece a latência em vez de paralelismo massivo para pequenos conjuntos de dados.

O artigo conclui que a redução da profundidade multiplicativa é o principal motor de eficiência, libertando mais níveis computacionais para operações úteis após o bootstrapping e permitindo dimensões de anel menores e mais rápidas.