Os oito testes
Cada teste tem um veredito declarado antes de rodar e um número medido depois.
T1
Camada linear sobre embedding cifrado
Funciona
Produto interno de 2048 dimensões — o padrão que o Google demonstra para recomendação e que
a indústria já usa: a CNN pesada roda em claro no dispositivo, só o embedding é cifrado.
CKKS, logN=14, 8192 slots, embedding no formato ResNet-50
| Etapa | Medido |
|---|
| Multiplicação ct × pt + rescale | 1,6 ms |
| InnerSum — 12 rotações | 62,8 ms |
| Precisão do resultado | 28,2 bits |
| Slowdown sobre o claro | ~27.500× |
| Amortizado em lote de 4 | 16 ms/item |
| Chaves Galois + relinearização | 97,5 MB |
O achado
A rotação custa 40× mais que a multiplicação. "FHE é lento
porque multiplicar cifrado é caro" está errado — multiplicar é barato. O que é caro é
mover dados entre slots, e é disso que qualquer redução, soma de vetor ou
convolução é feita.
Otimizar FHE é, na prática, minimizar rotações. É a reescrita mais valiosa que o HEIR automatiza.
T2
Orçamento de profundidade multiplicativa
Custa
Cada multiplicação consome um nível do módulo. Quando os níveis acabam, o ciphertexto vira
ruído. Rodamos quadrados sucessivos até quebrar — e os dois modos de BGV quebram de formas
muito diferentes.
| Modo | Morre em | Como morre |
|---|
| BGV (com rescale) | profundidade 4 | Erro explícito: sem nível para rescalar |
| BFV (scale-invariant) | profundidade 8 | Silenciosamente — resultado errado |
| CKKS | 8 multiplicações | Gradual: 0,6 bits de precisão por nível |
│ depth nível esperado obtido status
│ 7 4 15028 15028 ✅ exato
│ 8 4 282 28323 ❌ RUÍDO — resultado errado, sem aviso
O achado
O BFV dá mais profundidade e
falha sem aviso. É a combinação mais perigosa que existe em produção: nenhum erro, nenhuma
exceção, um número plausível que está simplesmente errado.
Consequência de projeto: o circuito precisa ser conhecido antes das chaves. É por
isso que agregação funciona tão bem — somar é profundidade zero.
T3
Não-linearidades: onde o custo explode
Não funciona
FHE oferece exatamente dois operadores: soma e produto. Todo o resto vira polinômio — e
polinômio custa profundidade, o recurso escasso de T2.
(a) Ativações suaves — funciona, com uma ressalva
Sigmoid por Chebyshev em [−8, 8]: grau 31 dá erro de 4,7e−5 em 5 níveis; grau 63 dá 4,4e−8 em 6.
Mas fora do intervalo o polinômio não degrada — explode:
│ x = 7.9 sigmoid real 0.999629 polinômio 0.999629 ✅
│ x = 10.0 sigmoid real 0.999955 polinômio -74.773.876 ❌
│ x = 15.0 sigmoid real 1.000000 polinômio -9,2e22 ❌
O servidor computa sobre cifrado e portanto não tem como detectar
isso. Garantir o domínio vira cláusula contratual do cliente.
(b) Comparação e sinal — o penhasco
O polinômio composto padrão para sign(): nove
polinômios encadeados, graus 15/15/15/17/31/31/31/31/7, com
profundidade somada de 40 níveis — contra os 4 a 8 de um
conjunto de parâmetros normal. Sem bootstrapping não é lento: é impossível.
A zona cega, medida. O limiar documentado é 2⁻³⁰ ≈ 9,31e−10.
| Entrada | Sinal correto | Sinal sob FHE |
|---|
| ±1e−9 | ±1 | ±1,000000 |
| ±1e−10 | ±1 | +0,553 / −0,680 |
| ±1e−12 | ±1 | −0,004 / −0,009 |
| 0 | 0 | −0,059 |
A fronteira medida cai exatamente entre 1e−9 e 1e−10, cercando 2⁻³⁰.
Comparar dois valores cifrados que diferem por menos de 2⁻³⁰ é uma
operação sem resultado definido.
(c) Divisão — barata, se o intervalo for declarado
Goldschmidt para 1/x em [0,25 · 1]: 52 ms, 31 bits, zero
bootstraps. O que encarece não é dividir — é dividir sem saber o intervalo.
O achado
O padrão de projeto correto não é fazer argmax sob cifra — é
devolver os scores cifrados ao cliente e deixar a decisão
acontecer em claro, do lado de quem tem a chave. Custo: zero.
Isso também explica por que redes profundas sob FHE trocam ReLU por x² e são
retreinadas com essa ativação: ReLU exato tem o custo do sinal.
T4
O custo real do bootstrapping
Custa
Bootstrapping é o que transforma "leveled HE" em fully homomorphic. Todo texto de
divulgação cita Gentry (2009). Quase nenhum publica o custo.
| Medida |
logN=13 brinquedo |
logN=16 128 bits reais |
| Keygen | 1,5 s | 20,2 s |
| Chaves de bootstrapping | 840 MB | 10,26 GB |
| Instanciar o avaliador | 0,7 s | 23,1 s |
| Um bootstrap | 1,25 s | 1 min 14 s |
| Precisão de saída | 25,0 bits | 24,6 bits |
| Níveis gastos para recuperar 10 | 15 | 15 |
Duas leituras que costumam ficar de fora dos diagramas. Primeiro: o bootstrapping
gasta 15 níveis para devolver 10 — o ganho é líquido, mas
modesto. Segundo: a diferença entre o conjunto de brinquedo e o de segurança real é de
60×, e a maior parte do material publicado não diz qual dos
dois está citando.
Combinando os contadores medidos em T3 com o bootstrap real de 1 min 14 s
| Operação | Bootstraps | Tempo |
|---|
| 1 sign() | 4 | 5 min |
| argmax de 10 | 36 | 45 min |
| argmax de 100 | 396 | 8 h 12 min |
| argmax de 1000 | 3.996 | 82 horas |
O achado
Um argmax sobre mil candidatos — a operação final de qualquer classificador — custa
três dias e meio de CPU sob cifra. Do lado do cliente,
que tem a chave: microssegundos.
Por isso a arquitetura que funciona hoje é leveled: dimensione o módulo para caber
o circuito inteiro e nunca bootstrappe. E por isso as parcerias de hardware anunciadas pelo
Google importam mais que o compilador — o gargalo é este número, e ele não cai por software.
T5
Lookup em tabela de embeddings
Não funciona
O problema central do HE-LRM, e o que separa "busca privada" de ficção. Se o índice está
cifrado, o servidor não pode saltar para a linha certa — o padrão de acesso à memória vazaria
justamente o dado que se queria proteger. Toda a tabela precisa ser tocada. Custo
linear em |V|, sem escapatória possível.
Medido acima da linha; projetado a 69 µs e 2 KB por linha abaixo
| Vocabulário | Tempo | Banda cliente → servidor |
|---|
| 512 | 36 ms | 1,0 MB |
| 8.192 | 569 ms | 16 MB |
| 10⁴ — CEPs do Brasil | 0,7 s | 20 MB |
| 10⁵ — SKUs de e-commerce | 6,9 s | 195 MB |
| 10⁶ — IDs de usuário | 69 s | 1,9 GB |
| 10⁷ — escala Criteo | 11,6 min | 19 GB |
O achado
A coluna da banda é a que mata: gigabytes enviados pelo
cliente para buscar 16 números.
O modelo do Criteo tem cerca de 26 features categóricas. Pela via ingênua isso dá
~5 horas contra os 228–489 s
declarados no paper — um ganho de ordem ~45×, coerente com os 56× reivindicados.
A bancada não reproduz o método deles, mas confirma que o problema atacado é real e é
desta escala.
T6
Banda, armazenamento e chaves
Custa
O custo que raramente entra no slide. Em arquitetura real, o que inviabiliza primeiro
costuma ser a banda, não a CPU.
| logN | Slots | Ciphertexto | Expansão |
|---|
| 12 | 2.048 | 192 KB | 12× |
| 14 | 8.192 | 1,75 MB | 28× |
| 15 | 16.384 | 4,50 MB | 36× |
| Um único número | 1 de 8.192 | 1,75 MB | 229.428× |
O achado
Contra-intuitivo: a expansão melhora com logN maior,
porque os slots dobram junto com o ciphertexto. Batching não é otimização — é pré-requisito.
FHE recompensa lotes grandes e homogêneos e pune consultas
pontuais. Um cálculo sobre 10.000 registros é barato; uma consulta sobre 1 registro
é caríssima. Isso inverte a intuição de quem vem de banco de dados, e é a origem da maior
parte das arquiteturas FHE mal dimensionadas.
T7
Empacotamento: onde o compilador paga
Funciona
T1 mostrou que a rotação custa ~40× a multiplicação. Segue-se que otimizar FHE é minimizar
rotações — e isso é um problema de empacotamento, não de
criptografia. É exatamente o que o HEIR automatiza. Este teste mede quanto vale.
(A) Matriz fina — 256 produtos × 8 dimensões
A forma do scoring de catálogo e de qualquer cabeça de classificação
| Estratégia | Chamadas | Rotações | Tempo | Erro máx |
|---|
| ingênuo (1 InnerSum/produto) | 256 | 768 | 1,81 s | 5,35e−10 |
| replicado | 1 | 3 | 8 ms | 4,88e−10 |
(B) Matriz quadrada 2048×2048 — uma camada densa de verdade
| Estratégia | Rotações | Chaves | Tempo | cts saída | Erro máx |
|---|
| ingênuo | 22.528 | 9,00 MB | 15,78 s | 2048 | 1,91e−09 |
| diagonal | 2.048 | 1,50 GB | 611 ms | 1 | 5,57e−11 |
| diagonal + BSGS | 95 | 71,3 MB | 156 ms | 1 | 5,58e−11 |
O achado
232× no caso fino, 101× no quadrado. Mesma biblioteca,
mesmos parâmetros, mesma máquina — só o empacotamento mudou. O BSGS ainda reduz as chaves
em 21× e devolve 1 ciphertexto em vez de 2048, e a precisão fica melhor que a do
ingênuo: menos operações acumulam menos ruído.
Isto fecha o argumento aberto em T1 e torna o valor do HEIR concreto. A reescrita é
mecânica e fácil de errar — escolher n1·n2, montar as diagonais, gerar o conjunto exato de
chaves Galois. Ninguém deveria fazer isso à mão.
Ressalva que impede a leitura errada: o ganho vale para
este formato de problema. Não se transfere para T3 nem T5 — comparação continua
exigindo bootstrapping, lookup continua linear no vocabulário. Empacotamento melhor não
move a fronteira; faz o lado de dentro dela caber no orçamento.
T8
TFHE/CGGI: o esquema que inverte tudo
Custa
T1–T7 mediram BGV, BFV e CKKS. TFHE — chamado CGGI no HEIR —
inverte todas as propriedades desses esquemas de uma vez. Cada gate booleana faz o seu próprio
bootstrapping embutido, então não existe orçamento de níveis e a
profundidade é ilimitada. Em troca, um ciphertexto carrega um bit.
go-tfhe v0.2.2, 128 bits de segurança, Go puro
| Medida | Valor |
|---|
| Keygen (secreta + nuvem) | 145 ms |
| Chave de avaliação | 164,20 MB |
| Latência por gate | 31,95 ms |
| Um bit cifrado | 2,7 KB |
| NOT | grátis |
Todas as gates (AND, OR, XOR, NAND, NOR, XNOR) conferem em todas as entradas — cada célula da
tabela de verdade é um bootstrapping real, não simulação. Um comparador de 8 bits são 32 gates
e 1,02 s; um somador de 8 bits, 40 gates e 1,28 s.
A comparação frontal: os dois esquemas são inversos
| Operação | CKKS | TFHE | Vencedor |
|---|
| 1 comparação | 4 min 58 s | 1,02 s | TFHE por ~291× |
| produto interno 2048-dim | 64 ms | ~112 h | CKKS por ~6×10⁶ |
| profundidade máxima | 8 mults | ilimitada | TFHE |
| dados por ciphertexto | 8.192 números | 1 bit | CKKS por ~10⁴ |
| chave de avaliação | 10,26 GB | 164 MB | TFHE por ~64× |
O achado
Isto reposiciona duas conclusões dos testes anteriores.
T2 não se aplica ao TFHE — não há níveis para acabar, não há
falha silenciosa. E T3 era uma afirmação sobre CKKS, não sobre FHE:
"comparação é inviável" vale para CKKS; sob TFHE é a operação natural.
Nenhum dos dois ganha em tudo, e a diferença não é de maturidade — é estrutural. A pergunta de
projeto deixa de ser "FHE serve?" e passa a ser:
o meu circuito é aritmético ou é lógico?
E é por isso que o HEIR suporta os dois lados — BGV/BFV/CKKS via OpenFHE e Lattigo, CGGI via
tfhe-rs e Jaxite. A escolha de esquema é uma decisão de compilação, e é a mais importante do
projeto.