💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

Este artigo introduz um algoritmo de varredura de prefixo otimizado para rotação para layouts de criptografia homomórfica com inversão de bits que reduz a complexidade de rotação de $O(m^2)$ para $O(m)$ ao aproveitar um invariante de replicação-agregação, reduzindo significativamente a latência computacional, o uso de memória e o armazenamento de chaves de avaliação, ao mesmo tempo em que possibilita pipelines subsequentes mais profundos.

Autores originais: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

Publicado 2026-07-07

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

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ê tem uma planilha gigante e criptografada onde cada célula contém um número secreto. Você quer realizar um truque matemático específico em todos esses números de uma só vez: para cada célula, você precisa saber o "total acumulado" de todos os números que vieram antes dela. No mundo da Criptografia Homomórfica (computação sobre dados secretos sem nunca descriptografá-los), isso é chamado de "prefix scan" (varredura de prefixo).

O problema é que os dados não estão armazenados em uma linha organizada como 1, 2, 3, 4. Devido à forma como a criptografia funciona, os dados estão embaralhados em um padrão específico chamado "ordem de reversão de bits". É como um livro onde as páginas estão embaralhadas: a página 1 é seguida pela página 8, depois pela 4, depois pela 12, e assim por diante.

O Jeito Antigo: O Problema do "Vizinho Exato"

Para calcular o total acumulado, você geralmente precisa pedir ao seu vizinho o número dele. Em uma linha normal, seu vizio está apenas um passo de distância. Mas neste livro embaralhado pela "reversão de bits", seu vizinho lógico pode estar sentado do outro lado da sala.

O método antigo tentava resolver isso enviando um mensageiro (uma "rotação") para buscar o vizinho específico exato que você precisava.

A Analogia: Imagine que você está em uma biblioteca com 8 prateleiras. Você precisa falar com a pessoa na prateleira diretamente à sua esquerda. Mas como as prateleiras estão embaralhadas, "esquerda" significa distâncias físicas diferentes para pessoas diferentes.
O Custo: Para que todos tivessem seu vizinho correto, o bibliotecário teve que enviar mensageiros por muitas rotas diferentes. Para um livro pequeno de 8 páginas, foram necessários 6 mensageiros. Para um livro maior, o número de mensageiros explodiu (cresceu como um triângulo: 1+2+3+4...). Isso era lento, caro e exigia uma enorme biblioteca de "chaves" (autorizações) para enviar mensageiros a todos esses lugares.

O Novo Jeito: A Estratégia do "Imitador"

Os autores deste artigo perceberam que estavam sendo exigentes demais. Eles não precisavam do vizinho exato; eles só precisavam de qualquer pessoa do grupo do vizinho que tivesse a mesma informação.

A Analogia: Em vez de pedir à pessoa específica à esquerda, imagine que cada pessoa em um "grupo" (um bloco de prateleiras) está segurando uma cópia idêntica do total de pontuação do grupo.
O Movimento Mágico: Os autores descobriram uma maneira de rotacionar a biblioteca inteira apenas uma vez por nível de cálculo. Essa única rotação move todo mundo para um lugar onde eles ficam ao lado de alguém do grupo adjacente. Como todos nesse grupo estão segurando uma cópia do "total do grupo", não importa qual pessoa específica você receba; a matemática funcionará perfeitamente.
O Resultado: Em vez de precisarem de 6 mensageiros para 8 páginas, eles só precisam de 1 mensageiro por nível. Para o livro inteiro, eles passaram de precisar de um número triangular de mensageiros (como 28) para apenas o número de níveis (como 7).

O Que Eles Realmente Provaram

O artigo não diz apenas que "isso é mais rápido". Eles provaram três fatos matemáticos difíceis:

Você não pode fazer melhor: Eles provaram que, não importa o quão inteligente você seja, você deve usar pelo menos tantos mensageiros quanto existam níveis no cálculo. Você não pode pular os mensageiros inteiramente.
A Rota "Perfeita": Eles mostraram que, se você usar o número mínimo de mensageiros, esses mensageiros devem seguir um padrão muito específico e rígido (relacionado a potências de 2). Não há margem de manobra; a matemática força esse caminho específico.
O Equilíbrio: Para economizar mensageiros, você tem que fazer um pouco mais de trabalho matemático localmente (mantendo dois conjuntos de números em vez de um). Mas em seus testes, economizar os mensageiros valeu a pena.

O Teste do Mundo Real (O Problema do "Carry")

Eles testaram isso em um problema matemático muito comum: Transporte de números (como quando você soma 9 + 3 e obtém 12, você tem que "transportar" o 1 para a próxima coluna).

A Configuração: Eles criptografaram uma lista de dígitos e tentaram corrigir os transportes sem desembaralhar a ordem.
O Resultado:
- Velocidade: O novo método deles foi cerca de 20% mais rápido que o antigo método do "vizinho exato" para problemas de tamanho médio.
- Memória: Usou 64% menos memória porque não precisaram armazenar tantas chaves de permissão.
- A Grande Vitória: Em uma cadeia longa de cálculos, o método deles economizou energia de criptografia suficiente para evitar um procedimento de reinicialização massivo e lento (chamado de "bootstrapping"). Isso tornou todo o processo 4,3 vezes mais rápido de ponta a ponta.

Resumo

Pense nisso como uma corrida de revezamento.

Método Antigo: Cada corredor tinha que percorrer um caminho único, longo e sinuoso para encontrar seu companheiro de equipe específico. Levava muita energia e tempo.
Novo Método: A equipe percebeu que, se apenas corressem um circuito curto e padronizado, todos acabariam ao lado de um companheiro de equipe que tivesse o mesmo bastão. Levou menos passos, menos energia e cumpriu o trabalho, embora os corredores tivessem que segurar alguns bastões extras ao longo do caminho.

O artigo prova que este atalho é a maneira absolutamente mais rápida de realizar esse tipo específico de matemática em dados embaralhados e criptografados.

Resumo Técnico: Varreduras de Prefixo Não Comutativas Otimizadas para Rotação em Layouts de Bits Revertidos

Enunciado do Problema

Na criptografia homomórfica (HE) empacotada, especificamente no esquema CKKS, operações SIMD permitem o computação paralela em vetores criptografados. No entanto, a comunicação entre slots requer rotações cíclicas (automorfismos de Galois), que são operações dispendiosas envolvendo troca de chaves (key switching). O custo de uma rotação depende do layout físico dos dados.

O artigo aborda o problema de realizar computações de prefixo ordenadas (varreduras ou scans) em $n = 2^m$ elementos de um monoide associativo, possivelmente não comutativo, quando os dados estão armazenados em uma ordem de bits revertidos (bit-reversed order). Este layout é comum em transformadas rápidas e conversões de empacotamento.

O desafio central é que uma varredura de "predecessor transportado" padrão (que dobra recursivamente a distância para os predecessores lógicos) incorre em um alto custo de roteamento em um layout de bits revertidos. Como a reversão de bits permuta os índices lógicos, um único deslocamento lógico por $2^t$ decompõe-se em múltiplas classes de deslocamento cíclico distintas. Consequentemente, uma implementação direta exige $R_{direta} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ rotações. Os autores investigam se este custo triangular é uma propriedade inerente da computação de prefixo em layouts de bits revertidos ou um artefato da topologia de roteamento específica.

Metodologia e Construção

O artigo introduz um invariante de replicação-agregação para reduzir a contagem de rotações de quadrática para linear.

Replicação Semântica: Em vez de rotear cada slot para seu predecessor lógico exato, a construção mantém um estado onde cada slot dentro de um bloco lógico alinhado armazena o agregado completo desse bloco.
Troca de Bloco-Irmão (Sibling-Block Exchange): Em cada nível $d$ $d$ da varredura (combinando blocos de tamanho $2^d$ $2^{d}$ ), o algoritmo rotaciona o estado agregado por um deslocamento específico $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ .
- Sob reversão de bits, os dois filhos de um bloco pai ocupam cosets físicos separados exatamente por $s_d$ .
- Uma rotação por $s_d$ mapeia um slot para alguma posição no bloco irmão. Como o agregado do irmão é replicado em todos os seus slots, qualquer posição no bloco irmão fornece o valor semântico correto.
- Isso permite que uma única rotação cíclica direcionada forneça agregados válidos para ambas as orientações de filhos simultaneamente, preservando a corretude para monoides não comutativos via máscaras públicas que selecionam a ordem dos operandos.
Formulação de Varredura Exclusiva: Os autores implementam uma varredura exclusiva (que retorna o prefixo antes do elemento atual). Isso evita a necessidade de um deslocamento final de predecessor lógico para recuperar o transporte (carry) de entrada para a correção de dígito, um requisito que, de outra forma, reintroduziria o roteamento sensível ao layout.
Provas de Limite Inferior: O artigo estabelece que $m$ rotações é um limite inferior global para qualquer circuito que compute uma saída dependente de todos os $2^m$ entradas neste modelo. A prova baseia-se em um argumento de soma de subconjuntos: se $R$ rotações são usadas, no máximo $2^R$ deslocamentos de entrada distintos podem alcançar uma saída fixa. Para cobrir todas as $2^m$ entradas, $R \ge m$ é necessário. Além disso, o artigo prova que atingir este limite exige que os deslocamentos de rotação formem uma base 2-ádica completa (um deslocamento para cada valoração $0, \dots, m-1$ ).

Principais Contribuições

Construção de Varredura Otimizada: Um algoritmo de varredura inclusiva e exclusiva que alcança $R = m$ rotações e $D = m$ de profundidade de monoide para layouts de bits revertidos. Isso reduz a contagem de rotações de $O(m^2)$ da topologia direta para $O(m)$ .
Rigidez da Otimalidade: Uma caracterização de todos os circuitos otimizados. Se um circuito usa exatamente $m$ rotações, os deslocamentos devem formar uma base 2-ádica completa. Isso prova que o perfil de rotação é rígido, mesmo que a topologia do circuito varie.
Fronteira de Chave de Rotação (Rotation-Key Frontier): Uma análise do compromisso entre o número de deslocamentos diretamente chaveados ( $K$ $K$ ) e o número de chamadas de rotação online ( $R$ $R$ ).
- O artigo deriva um limite inferior de produto: $\prod (c_j + 1) \ge 2^m$ , onde $c_j$ é o número de vezes que a chave $j$ é usada.
- Quando $K$ divide $m$ , a fronteira exata é provada como $R^* = K \cdot (2^{m/K} - 1)$ .
Instanciação Radix-CKKS: Aplicação da varredura exclusiva para propagação exata de transporte (carry) e empréstimo (borrow) em aritmética de base (radix-based) no CKKS. Isso permite comparação de inteiros e aritmética modular sem restaurar a ordem natural ou realizar um deslocamento final.
Eficiência de Agrupamento (Batching Efficiency): Demonstração de que a economia de rotação se mantém para interleavings de dígito-major totalmente ocupados, onde $g$ inteiros independentes são empacotados em um único texto cifrado sem multiplicar a contagem de rotação.

Resultados e Avaliação

Os autores implementaram o algoritmo no Lattigo (Go) e o compararam com duas linhas de base:

Predecessor Direto de Bits Revertidos: A abordagem ingênua de rotação $O(m^2)$ .
Normalizar–Varrer–Restaurar (Normalize–Scan–Restore): Uma linha de base que converte os dados para a ordem natural, realiza a varredura e converte de volta.

Principais Descobertas para $m=7$ (128 slots):

Rotações: Reduzidas de 28 (direta) para 7 (replicada).
Chaves de Avaliação: Armazenamento reduzido em 70,0% (908,6 MB $\to$ 272,6 MB).
Memória: Uso de pico de heap reduzido em 63,9% (2,30 GB $\to$ 830,5 MB).
Latência: A varredura replicada melhorou a latência de varredura isolada em 19,9% sobre o método de predecessor direto.
Pipeline End-to-End: Em um pipeline subsequente de profundidade 5, a varredura replicada evitou uma operação completa de bootstrapping exigida pela linha de base normalize-restaurar. Isso resultou em um ganho de velocidade médio pareado de 4,31 $\times$ (IC de 95% [3,69, 4,92]).

O artigo observa que, embora o "normalize–scan–restore" tenha menor latência isolada para $m$ pequeno devido a menos composições de monoide, a varredura replicada torna-se mais rápida para $m \ge 5$ e oferece maior eficiência de recursos (chaves, memória e níveis de módulo).

Significância e Alegações

O artigo afirma que preservar uma representação SIMD de bits revertidos não impõe um overhead de rotação inevitável para a computação de prefixo ordenado. A significância reside em:

Quebrar a Barreira Quadrática: Provar que o custo $O(m^2)$ de roteamento direto em layouts de bits revertidos não é inerente, mas pode ser reduzido para o limite teórico de $O(m)$ via replicação semântica.
Compromissos de Recursos: Estabelecer que a redução no custo de roteamento (rotações) e armazenamento de chaves vem às custas de um aumento no trabalho de monoide empacotado ( $2m-1$ composições vs. $m$ ) e um segundo vetor de estado vivo. O artigo argumenta que este compromisso é favorável para pipelines profundos, onde os níveis de módulo e o bootstrapping são gargalos.
Exatidão: Fornecer limites inferiores exatos e caracterizações de fronteira para o gerenciamento de chaves de rotação, indo além de otimizações heurísticas para limites prováveis para padrões de dependência específicos.

O trabalho é apresentado como uma otimização específica para a restrição de layout de bits revertidos, distinta da teoria geral de redes de prefixo, e é validado através de provas combinatórias rigorosas e avaliação empírica em uma implementação padrão de CKKS.