Este tutorial percorre cada algoritmo usado nos exemplos de votação FHE: da álgebra de anéis que sustenta a encriptação até as provas de conhecimento zero que garantem a integridade. Cada seção constrói sobre a anterior.
Fundamento 1
Todos os esquemas FHE modernos (BGV, BFV, CKKS) se baseiam no problema RLWE, que é considerado seguro mesmo contra computadores quânticos.
Trabalhamos no anel de polinômios:
Onde $N$ é uma potência de 2 (tipicamente 16384) e $q$ é um inteiro grande (produto de primos). Cada elemento é um polinômio de grau $< N$ com coeficientes mod $q$.
Dados:
A amostra RLWE é o par:
Problema: distinguir $(a, a \cdot s + e)$ de $(a, u)$ onde $u$ é aleatório. Ninguém conhece algoritmo eficiente (clássico ou quântico) para resolver isso.
Chave pública: $pk = (a, b = a \cdot s + e)$. Para cifrar uma mensagem $m$:
// Encriptar
$r \leftarrow \chi$ (aleatório pequeno)
$ct_0 = b \cdot r + e_1 + \Delta \cdot m$
$ct_1 = a \cdot r + e_2$
// Decriptar
$m' = ct_0 - ct_1 \cdot s \approx \Delta \cdot m + \text{ruído}$
Onde $\Delta = \lfloor q/t \rfloor$ é o fator de escala e $t$ é o módulo do plaintext. O ruído acumulado deve ser menor que $\Delta/2$ para decodificação correta.
Esquema 1
BGV (Brakerski-Gentry-Vaikuntanathan) e BFV (Fan-Vercauteren) operam sobre inteiros módulo $t$ (plaintext modulus). No Lattigo v6, BFV é implementado como modo "scale-invariant" do BGV.
O anel $R_t = \mathbb{Z}_t[X]/(X^N+1)$ se decompõe via CRT (Chinese Remainder Theorem) em $N/2$ slots independentes quando $t \equiv 1 \pmod{2N}$:
Isso significa que uma única operação sobre o ciphertexto executa a mesma operação em $N/2 = 8192$ inteiros simultaneamente (SIMD grátis). No nosso exemplo: $t = 65537$ (primo de Fermat, ideal para NTT).
Soma dos polinômios componente a componente. Ruido cresce linearmente.
Produto tensorial dos ciphertexts. Grau sobe de 2 para 3 — requer relinearização.
$rlk$ é uma encriptação de $s^2$ que permite "comprimir" o ciphertexto expandido.
Cada voto é codificado como vetor one-hot nos slots SIMD:
// Candidato 2 de 4:
voto = [0, 0, 1, 0, 0, 0, ..., 0] // 8192 slots
// Soma de 1000 votos cifrados:
$\sum_{i=1}^{1000} \text{Enc}(\text{voto}_i) = \text{Enc}([374, 247, 218, 161, 0, ...])$
// Cada slot acumula votos de um candidato
Esquema 2
Em BGV, o ruído é inimigo — deve ser eliminado. Em CKKS, o ruído é tratado como erro de arredondamento, como em ponto flutuante IEEE 754.
O vetor complexo $z \in \mathbb{C}^{N/2}$ é mapeado via DFT inversa para um polinômio em $R_q$, escalado por $\Delta$. A decodificação aplica DFT e divide por $\Delta$.
Apos multiplicação, a escala dobra ($\Delta^2$). O rescaling divide por $\Delta$ e remove um primo da cadeia modular:
// Antes: escala = $\Delta^2$, modulo = $q_0 \cdot q_1 \cdot q_2$
$ct' = \lfloor ct / q_2 \rceil$
// Depois: escala = $\Delta$, modulo = $q_0 \cdot q_1$
// Cada rescaling consome 1 nível
// LogQ: [55, 45, 45, 45, 45, 45, 45, 45] → 7 níveis disponíveis
Para somar todos os slots em um único valor (ex: calcular média), usamos rotações com Galois keys:
// InnerSum via rotações log2(N) vezes:
$\text{result} = \sum_{k=0}^{N/2-1} \text{Rotate}(ct, k)$
// Otimizado: apenas $\log_2(N/2) = 12$ rotações
// Cada rotacao usa uma Galois key especifica
Esquema 3
Diferente de BGV/CKKS que empacotam milhares de valores, TFHE cifra um único bit por ciphertexto usando LWE (não RLWE):
Onde $m \in \{0, 1\}$, $\vec{a} \in \mathbb{Z}_q^n$, $\vec{s}$ é a chave secreta, e $e$ é ruído gaussiano. O fator $q/4$ separa as codificações de 0 e 1.
Cada gate (AND, OR, XOR) aumenta o ruído. Sem tratamento, após ~10 gates o ruído ultrapassa o limiar e a decifração falha. Bootstrapping reseta o ruído avaliando homomorficamente a própria função de decifração:
// Bootstrapping em alto nível:
1. ct_ruídoso = Enc(m) com ruído alto
2. Avaliar Dec(ct_ruidoso) homomorficamente
3. ct_limpo = Enc(m) com ruído baixo
// Custo: ~13ms por gate em CPU moderna
// Beneficio: profundidade ILIMITADA
O comparador de 4 bits usa cascata do MSB ao LSB. Para cada bit $i$:
// gt_i = A[i]=1 AND B[i]=0
$gt_i = \text{AND}(A_i, \text{NOT}(B_i))$
// eq_i = A[i] = B[i]
$eq_i = \text{NOT}(\text{XOR}(A_i, B_i))$
// Resultado final (MSB tem prioridade):
$A > B = gt_3 \;\text{OR}\; (eq_3 \;\text{AND}\; gt_2) \;\text{OR}\; \ldots$
// Total: ~30 gates por comparação de 4 bits
ZKP — Parte 1
Um commitment é uma "promessa criptográfica": você se compromete com um valor sem revelá-lo, e depois pode provar que não mudou de ideia.
Para cada candidato $i$, criamos um commitment:
// 4 candidatos → 4 commitments
$C_0 = 0 \cdot G + r_0 \cdot H$ // não votou no candidato 0
$C_1 = 0 \cdot G + r_1 \cdot H$ // não votou no candidato 1
$C_2 = 1 \cdot G + r_2 \cdot H$ // VOTOU no candidato 2
$C_3 = 0 \cdot G + r_3 \cdot H$ // não votou no candidato 3
// Verificador ve C0, C1, C2, C3 mas NAO sabe qual e 1
ZKP — Parte 2
Para cada commitment $C_i$, precisamos provar que $v_i \in \{0, 1\}$ sem revelar qual. Usamos a técnica CDS (Cramer-Damgard-Schoenmakers) de OR-composition:
// Se v=0 (C = r*H): provar conhecimento de r tal que C = r*H
// Branch 0 (real): Schnorr proof honesta
k $\leftarrow$ random; A_0 = k*H
// Branch 1 (simulada): gerar resposta primeiro, calcular commitment
e_1, s_1 $\leftarrow$ random; A_1 = s_1*H - e_1*(C-G)
// Fiat-Shamir: e_total = Hash(contexto || C || A_0 || A_1)
e_0 = e_total - e_1 mod n
s_0 = k + e_0 * r mod n
Simulabilidade: A branch simulada (falsa) é estatisticamente indistinguivel da branch real. O verificador ve $(e_0, s_0, A_0)$ e $(e_1, s_1, A_1)$ mas não consegue distinguir qual foi simulada — ambas satisfazem as equações de verificação.
Soundness: Um prover desonesto (que não conhece $r$) precisaria prever o hash Fiat-Shamir antes de calcular os commitments — impossível pela propriedade de pre-imagem do SHA-256.
Alem de provar que cada $v_i \in \{0,1\}$, precisamos provar que $\sum v_i = 1$ (exatamente um candidato escolhido):
// C_total = C_0 + C_1 + C_2 + C_3
// Se sum(v_i) = 1:
$C_{total} = 1 \cdot G + (\sum r_i) \cdot H$
$C_{total} - G = (\sum r_i) \cdot H$
// Schnorr proof: provar conhecimento de $\sum r_i$
// tal que $C_{total} - G = (\sum r_i) \cdot H$
Anonimato
O cartório precisa autenticar que o eleitor tem direito de voto (verificar título). Mas se o cartório vê o token, ele pode depois ligar o token ao eleitor quando o token aparecer na urna. Blind signatures resolvem isso.
// Setup: cartório tem (N, e, d) onde e*d = 1 mod phi(N)
// Passo 1: Eleitor prepara token
token = SHA-256("TITULO-000042")
// Passo 2: Eleitor BLINDA (cartório não verá o token)
r $\leftarrow$ random coprimo com N
blind = token $\cdot$ r$^e$ mod N
// Passo 3: Cartório assina CEGO (vê apenas "blind")
sig_blind = blind$^d$ mod N
// = (token * r^e)^d = token^d * r^(e*d) = token^d * r
// Passo 4: Eleitor DESBLINDA
sig = sig_blind $\cdot$ r$^{-1}$ mod N
// = token^d * r * r^{-1} = token^d
// Passo 5: Qualquer pessoa verifica
sig$^e$ mod N == token // TRUE!
O cartório viu apenas $\text{blind} = \text{token} \cdot r^e \bmod N$. Como $r$ é aleatório e desconhecido pelo cartório, $\text{blind}$ é uniformemente distribuído em $\mathbb{Z}_N^*$ — não carrega nenhuma informação sobre o token. Quando o token aparece na urna, o cartório não tem como ligar ao $\text{blind}$ que assinou.
Threshold
Para dividir um segredo $s$ entre $n=5$ autoridades com threshold $t=3$, construimos um polinômio aleatório de grau $t-1 = 2$:
Cada autoridade $i$ recebe o ponto $(i, f(i))$. Com $t=3$ pontos, o polinômio é unicamente determinado por interpolação de Lagrange. Com $t-1=2$ pontos, há infinitos polinômios possíveis — nenhuma informação sobre $s$ vaza.
// Dados 3 pontos: (1, f(1)), (2, f(2)), (3, f(3))
// Coeficientes de Lagrange:
$\lambda_1 = \frac{(0-2)(0-3)}{(1-2)(1-3)} = \frac{6}{2} = 3$
$\lambda_2 = \frac{(0-1)(0-3)}{(2-1)(2-3)} = \frac{3}{-1} = -3$
$\lambda_3 = \frac{(0-1)(0-2)}{(3-1)(3-2)} = \frac{2}{2} = 1$
// Segredo recuperado:
$s = f(0) = \lambda_1 f(1) + \lambda_2 f(2) + \lambda_3 f(3)$
No Lattigo, o segredo compartilhado é a chave secreta do anel polinomial $s \in R_q$. Cada coeficiente do polinômio $s$ é compartilhado independentemente:
// Protocolo CKS (Collective Key Switching):
1. Cada autoridade gera share: $h_i = ct_1 \cdot (sk_i^{aditivo}) + e_i$
2. Servidor agrega: $h = \sum h_i$
3. KeySwitch: $ct_{novo} = (ct_0 + h, \; 0)$
// Resultado: ct cifrado com sk=0 → plaintext exposto
// Noise flooding ($\sigma = 2^{30}$) garante segurança estatística
Integridade
Cada voto é publicado em um log append-only com encadeamento SHA-256:
$H_0 = \text{SHA-256}(\text{"genesis"})$
$H_1 = \text{SHA-256}(H_0 \| \text{hash}_{voto_1})$
$H_2 = \text{SHA-256}(H_1 \| \text{hash}_{voto_2})$
$H_i = \text{SHA-256}(H_{i-1} \| \text{hash}_{voto_i})$
// Alterar qualquer entrada quebra TODA a cadeia dali em diante
// Verificação: O(n) — qualquer pessoa pode auditar
Para destruir o link entre a ordem dos votos e a identidade do eleitor:
// Cada mix node faz:
1. $\pi \leftarrow$ permutação aleatória (Fisher-Yates)
2. Para cada voto $ct_i$:
$ct'_{\pi(i)} = ct_i + \text{Enc}(0)$ // re-randomiza
// Enc(0) tem randomness fresca → ciphertext totalmente diferente
// Mas Dec(ct') = Dec(ct) → mesmo voto, aparencia diferente
// Com 3 mix nodes: basta 1 honesto para garantir privacidade
Visão Geral