Somar números trancados sem abrir a caixa.

Imagine uma caixa de vidro trancada com luvas embutidas. Você põe as joias dentro, tranca e entrega ao joalheiro. Ele consegue polir, cortar e montar pelas luvas, mas nunca segura as joias na mão, porque não tem a chave. Quando termina, devolve a caixa, e só você abre.

É isso que a criptografia homomórfica (FHE) faz com números: o servidor soma e multiplica o dado trancado e devolve o resultado trancado. Só o dono da chave lê. A matemática abaixo explica como as "luvas" funcionam e por que elas têm limite.

No relógio, 11 horas mais 2 horas dá 1 hora, não 13: passou do 12, recomeça. Os matemáticos chamam isso de conta "módulo 12". Toda conta do FHE é feita assim, num relógio enorme, e isso é o que deixa os números trancados sempre do mesmo tamanho, por mais contas que você faça.

Para guardar uma mensagem, o relógio é dividido em fatias, uma por valor possível. No espécime lá em cima são 64 posições e 4 fatias de 16: guardar o número 2 é apontar para o meio da terceira fatia. Ler é ver em que fatia o ponteiro caiu. Enquanto o ponteiro não sai da fatia, a leitura é exata.

O cadeado se apoia num problema de geometria. Pense numa grade de pontos inclinada, como as estacas de um pomar plantado torto. Alguém escolhe um ponto da grade em segredo e publica um ponto um pouco deslocado dele. A pergunta: qual era o ponto da grade?

Com duas dimensões, qualquer um acha no olho. Com centenas de dimensões, ninguém conhece um jeito rápido, nem com computador quântico. O nome técnico é "reticulado" (e o problema, "aprender com erros", em inglês LWE). As novas fechaduras pós-quânticas do NIST se apoiam no mesmo tipo de problema.

b = a·s + e + Δ·m

Lida em voz alta: "o número publicado b é um número aleatório a vezes o segredo s, mais um pouco de ruído e, mais a mensagem m esticada até o meio da sua fatia (Δ)." Quem tem s subtrai a·s e sobra só a mensagem com um pouco de ruído. Quem não tem vê um número que parece sorteado.

O ruído e é o que torna o cadeado seguro, mas ele não some: vai junto nas contas. Somar dois números trancados soma os ruídos, e o ponteiro anda um pouquinho para fora do centro. Multiplicar multiplica os ruídos, e o ponteiro dá um salto.

Por isso, na prática, o que limita um cálculo cifrado não é a quantidade de somas, é quantas multiplicações seguidas cabem antes de o ponteiro sair da fatia. Quando sai, a chave lê o número da fatia vizinha. Experimente no espécime: cifre 1 e multiplique por 3 duas vezes.

Na nossa bancada, com parâmetros de 128 bits de segurança, o dialeto de inteiros (BFV) acerta a 7ª multiplicação seguida e erra a 8ª sem avisar: devolve 28323 no lugar de 282. Nenhum erro, nenhuma exceção, só um número plausível e errado.

A mesma ideia vira três "dialetos", e cada um é bom numa coisa:

Inteiros exatos (BGV/BFV): contas com números inteiros num relógio, sem arredondar. É o que conta votos.

Números com vírgula (CKKS): aqui o ruído é tratado como os últimos dígitos de um arredondamento, como numa calculadora. Serve para médias e modelos de IA. Na bancada, perde cerca de 0,58 bit de precisão por nível de multiplicação.

Bit a bit (TFHE): tranca cada bit e monta portas lógicas (E, OU, NÃO). É o que sabe comparar e decidir. É o inverso do CKKS: compara 8 bits em ~2 s (o CKKS leva ~5 min), mas um produto interno de 2.048 números levaria ~190 h (o CKKS faz em 115 ms).

Um único cadeado guarda não um número, mas uma fileira inteira: na nossa votação, 16.384 casas na mesma caixa. Uma soma de caixas soma todas as casas de uma vez, como uma planilha em que uma fórmula vale para a coluna inteira.

Um voto vira uma fileira com 1 na casa do candidato escolhido e 0 no resto. Somar mil fileiras trancadas dá, em cada casa, o total de cada candidato, sem abrir nenhum voto.

O caro não é somar nem multiplicar: é mover dado entre casas, por exemplo para somar a fileira inteira num número só. Na bancada, uma multiplicação levou 2,7 ms e juntar a fileira (12 rotações) levou 112,8 ms, cerca de 40 vezes mais.

Quando o ruído chega perto do limite, dá para fazer uma "faxina" (bootstrap): o servidor roda, ainda trancado, o próprio procedimento de abrir o cadeado, usando uma versão trancada da chave. Sai o mesmo número com ruído pequeno de novo. Em princípio, isso permite contas de qualquer tamanho.

O preço, medido na nossa bancada a 128 bits reais: 1 min 18 s ± 8 s por faxina e 10,26 GB de chaves guardadas no servidor. Com parâmetros de brinquedo são 1,92 s e 840 MB, cerca de 40 vezes menos. Muita comparação publicada não diz qual dos dois está medindo.

Um atalho que medimos: em vez da faxina, o servidor devolve o número cansado ao dono, que abre, tranca de novo e manda de volta. Leva 1,04 s a 100 Mbps, sem chave de faxina nenhuma (75 vezes mais barato), mas exige o dono online.

E um aviso: com os parâmetros honestos de 128 bits no tamanho menor (logN=13), cabem 2 multiplicações seguidas, não 8, como sugeriam configurações mais fracas.

Uma eleição cifrada precisa de mais quatro ideias, todas com a mesma cara de "provar sem mostrar":

Prova de conhecimento zero. O eleitor prova que a fileira dele tem exatamente um 1 e o resto 0, sem mostrar onde está o 1. É como provar que você sabe a senha do cofre abrindo e fechando o cofre atrás de uma cortina.

Assinatura cega. O cartório carimba o direito de votar dentro de um envelope com papel carbono: o carimbo passa para o papel, mas o cartório não vê o que carimbou. Depois não consegue ligar o carimbo ao eleitor.

Chave dividida, 3 de 5. A chave que abre o resultado é partida entre cinco pessoas; quaisquer três juntas abrem, duas não aprendem nada. É a curva ao lado: três pontos refazem a curva e revelam o segredo no zero.

A urna que embaralha e a corrente de impressões digitais. Três etapas embaralham e re-trancam os votos, para ninguém ligar voto a ordem de chegada (basta uma etapa honesta). E cada voto entra numa corrente em que cada elo leva a impressão digital do anterior: mudar um voto antigo quebra todos os elos seguintes.