As peças da urna, rodando

Toda a criptografia da urna faz contas num grupo: um conjunto de números em que se pode multiplicar e elevar a potências, e em que desfazer uma potência é inviável. Dado g^x, ninguém consegue descobrir x. Esse é o problema do logaritmo discreto, e quase tudo nesta página depende dele.

Para rodar as provas à mão, usamos um grupo minúsculo: as potências de g = 2 módulo 23. Ele tem só 11 elementos, então os expoentes contam de 0 a 10 e "dão a volta" no 11. Neste tamanho, a tabela abaixo resolve qualquer logaritmo, e por isso o brinquedo não esconde nada. Ele serve para conferir as contas; a segurança vem do tamanho do grupo real.

Com a tabela, multiplicar vira somar expoentes: 16 · 13 = g⁴ · g⁷ = g¹¹ = g⁰ = 1. Nas bancadas, cada número do grupo aparece com o seu expoente ao lado, como 16 (g⁴), para você conferir na tabela. No grupo real, a operação se chama soma de pontos em vez de multiplicação, mas as contas têm a mesma forma.

Uma função de hash transforma qualquer texto num número de tamanho fixo, a sua impressão digital. Mudar uma letra muda o número inteiro, e é inviável achar dois textos com a mesma impressão. A urna usa hashes para três coisas: códigos de rastreamento, o mural e os desafios das provas.

Todo hash da especificação começa com uma etiqueta que diz para que ele serve, como eg/v1/code ou eg/v1/ballot. Assim, um hash calculado para um fim nunca vale para outro, mesmo que o resto da entrada seja igual. Nos desafios das provas, o hash faz o papel de um juiz que sorteia sem que ninguém controle o sorteio; esse uso tem nome, modelo do oráculo aleatório [1].

A chave pública da eleição é K = g^s, e ninguém conhece s inteiro (seção 4). Para trancar um voto m (0 ou 1), a urna sorteia um número secreto r e publica o par

α = g^r    β = g^m · K^r

O voto vai no expoente. Multiplicar duas caixas, número a número, dá uma caixa com a soma dos votos, porque expoentes se somam. Para abrir, divide-se β por α^s, o que sobra é g^m, e acha-se m por tentativa: ele é no máximo o número de eleitores.

Por que é seguro. Sem a chave, uma caixa com 0 e uma com 1 são indistinguíveis, desde que valha a hipótese de Diffie-Hellman decisional no grupo; a demonstração é de Tsiounis e Yung [32]. E uma caixa não pode ser aberta como dois votos diferentes: α fixa r, e então β fixa m. A auditoria da seção 10 depende disso.

A chave s é a altura em que uma reta secreta f(x) = s + a·x corta o eixo. O guardião j recebe o ponto z_j = f(j). Com dois pontos a reta é única; com um, qualquer altura é possível. É o "dois de três". Com limiar maior, a reta vira uma curva de grau maior, e a ideia é a mesma.

Dois detalhes tornam isso prático. Cada guardião publica g^s e g^a (os compromissos de Feldman), para que cada um confira, sem ver a reta, que o seu ponto está nela. E ninguém escolhe a reta sozinho: cada guardião sorteia a sua, e a reta da eleição é a soma de todas (a cerimônia de Pedersen).

Para abrir uma caixa, os guardiões nunca juntam os pontos. Cada um eleva α ao seu pedaço e publica M_j = α^z_j. Elevando esses resultados a pesos fixos, os coeficientes de Lagrange, e multiplicando, sai exatamente α^s, o que basta para abrir. A chave s nunca aparece.

Por que é seguro. Com menos pontos que o limiar, todos os segredos possíveis continuam igualmente prováveis: é segurança perfeita, que não depende de nenhuma hipótese [29]. Cada pedaço aplicado vem com a prova da seção 6.

É a caverna da página Início com números. Quem conhece x, com X = g^x público, prova isso em três movimentos:

1. Entra na caverna: sorteia u e publica A = g^u.
2. O juiz pergunta: um desafio c, tirado do hash de tudo o que foi escrito.
3. Sai pelo lado pedido: responde v = u + c·x.

Quem confere testa se g^v = A · X^c. As duas contas batem só se a resposta foi feita com o x certo.

Por que convence. Se alguém respondesse a dois desafios diferentes para o mesmo A, as duas respostas entregariam x; então quem responde a um desafio imprevisível precisa saber x. Por que não revela. Escolhendo c e v antes e calculando A de trás para frente, qualquer um fabrica uma conversa com a mesma cara de uma real, sem saber x. É o "vídeo combinado" da caverna. A bancada mostra as três coisas.

O juiz precisa ver a afirmação inteira

O hash do desafio tem de incluir a afirmação (X) e o contexto, e não só A. Se incluísse só A, dava para escolher A, calcular o desafio e só depois inventar um X que fizesse a conta fechar, "provando" conhecer um segredo que ninguém conhece. Esse descuido quebrou o Helios em 2012 [6]. Na especificação, todo desafio inclui a afirmação, a eleição, a cédula, o cargo e a opção (§11).

A mesma prova de Schnorr, feita em duas bases ao mesmo tempo com o mesmo segredo. Serve para o guardião mostrar que o pedaço z que aplicou à caixa (M = α^z) é o mesmo registrado na cerimônia (Z = g^z). Ele sorteia u, publica g^u e α^u, recebe o desafio e responde v = u + c·z. Quem confere testa as duas bases.

Um guardião que publica um M falso, para abrir a soma com o número errado, não consegue fazer as duas contas baterem. A parte falsa é descartada e as dos outros guardiões bastam.

São as duas cavernas da página Início. A caixa guarda 0 se β = K^r, e guarda 1 se β ÷ g = K^r. Em cada caso, o número secreto r é a "senha" de uma das duas afirmações. A urna faz uma prova de Chaum-Pedersen para cada afirmação, com uma liberdade: ela pode escolher um dos dois desafios, desde que a soma dos dois seja o desafio do hash.

Na afirmação falsa, ela escolhe o desafio e a resposta antes e calcula o compromisso de trás para frente, como o falsificador da seção 5. Na verdadeira, faz a prova honesta com o desafio que sobrou. Quem confere vê duas provas que batem e desafios que somam certo, e não sabe qual era a fingida.

Por que convence. Uma caixa com 2 não tem senha para nenhuma das afirmações. Para passar, a urna precisaria fingir as duas, o que exige adivinhar o desafio do hash antes de calculá-lo. No grupo real a chance é de uma em ≈ 7 × 10⁷⁵. No brinquedo, com só 11 desafios possíveis, é de uma em 11, e a bancada mostra a trapaça passando depois de algumas tentativas. É exatamente por isso que o grupo real é enorme.

Um cargo vira uma caixa para cada opção, inclusive branco e nulo. Cada caixa leva a prova de 0 ou 1. Depois, a urna multiplica todas as caixas do cargo e prova, com Chaum-Pedersen, que a caixa-produto guarda exatamente 1 (2 no senado, com duas vagas). A "senha" dessa prova é a soma dos números secretos das caixas. Se cada caixa tem 0 ou 1 e a soma é 1, há exatamente uma opção marcada.

Duas proteções completam a cédula. Todos os números secretos saem de uma semente única, apagada no depósito e revelada na auditoria. E cada prova inclui o identificador da cédula, de modo que copiar a caixa de outro eleitor para uma cédula própria (um ataque que, numa seção pequena, revelaria o voto da vítima) não leva junto uma prova válida. Um mesmo α que reapareça é excluído da apuração.

O código de cada cédula é o hash da cédula junto com a "cabeça" da corrente, e a cabeça seguinte é o hash do código com o desfecho (depositada, auditada ou abandonada). A primeira cabeça sai da zerésima. Assim o código de cada eleitor depende de toda a história anterior da urna naquele dia.

Consequências. Tirar, trocar ou reordenar uma cédula muda todos os códigos seguintes, que já estão nas mãos dos eleitores. Dois eleitores nunca recebem o mesmo código, o que impede a urna de dar a mesma caixa a dois eleitores com o mesmo voto e usar a vaga livre para um voto inventado [21]. Fraudar isso exigiria achar duas entradas com o mesmo SHA-256.

A urna tranca o voto e mostra o código antes de perguntar se o eleitor quer depositar ou auditar. Na auditoria, ela revela o número secreto e o voto que diz ter trancado. Um aparelho independente tranca de novo esse voto com esse número e compara com a caixa publicada. Como a caixa determina o voto (seção 3) e o código fixou a caixa (seção 9), uma urna que trancou outra coisa não tem como passar.

Quanto pega. Se a urna troca t votos e cada eleitor audita com chance p, sem que a urna saiba quem vai auditar, a chance de nenhuma troca ser auditada é (1 − p)^t. Com 5% de auditorias, trocar 100 votos escapa em 0,6% dos casos.

O mural é uma árvore de hashes. Cada folha é o hash de uma entrada (com o prefixo 00); cada nó é o hash dos dois filhos (com o prefixo 01); a raiz resume tudo. O mural assina a raiz junto com o número de entradas.

Para provar que uma entrada está no mural, basta entregar os irmãos no caminho até a raiz: com um milhão de entradas, são 20 hashes. Uma prova falsa exigiria uma colisão de SHA-256. Duas raízes assinadas para o mesmo tamanho são prova de que o mural mostrou versões diferentes a pessoas diferentes, e os espelhos comparam raízes para pegar isso.

Quando as cédulas precisam ser abertas uma a uma, cada guardião embaralha a lista e retranca cada caixa: multiplica por uma caixa de zero com número secreto novo. O conteúdo não muda, mas os números da caixa mudam por completo, e ninguém reconhece qual saída veio de qual entrada. Basta um embaralhador honesto para a ordem final não ter relação com a fila.

Por que ninguém troca um voto. Cada embaralhador publica uma prova de que a saída é a entrada permutada e retrancada, sem revelar a permutação. A prova de Terelius e Wikström se apoia num fato simples: uma tabela de números é uma permutação se e somente se cada linha soma 1 e um certo produto de somas coincide com o produto das variáveis; isso é testado num ponto sorteado [30]. A bancada mostra o embaralhamento e a conferência do conteúdo, não a prova.

No fim do dia, a urna multiplica as caixas de cada opção e imprime no pré-boletim a impressão digital dessas somas trancadas, sem nenhum número por candidato. Depois, qualquer pessoa refaz as somas a partir do mural e compara. Os guardiões abrem as somas da seção com as provas da seção 6, e o boletim final traz os números e a mesma impressão digital do papel. Seções pequenas demais para publicar sem expor eleitores são somadas a um grupo maior.

Os totais viram resultado por regras públicas, só com contas inteiras: maioria absoluta dos votos válidos para presidente (brancos e nulos não entram), os mais votados para o senado e, nos cargos proporcionais, D'Hondt ou a regra brasileira de 2021, com quociente eleitoral e sobras. Qualquer verificador refaz e chega ao mesmo eleito.

O verificador junta as peças anteriores. Recebe uma cópia do mural e uma raiz assinada, e refaz dezesseis conferências sem nenhuma chave:

Se o verificador aceita, o resultado é a contagem correta das cédulas válidas no mural, sem precisar confiar em nenhuma das partes: guardiões, urnas, mural ou autoridade eleitoral. Que essas cédulas sejam as que os eleitores escolheram depende ainda das auditorias (seção 10), dos códigos conferidos (seção 9) e dos fiscais com o pré-boletim (seção 13). As definições formais dessas propriedades estão em [11] e [5].

A contagem não depende do programa da urna: um programa adulterado é pego pelas auditorias, pelas provas e pelos códigos, como qualquer urna desonesta. É o que Rivest chama de independência de software [27]. O sigilo, porém, depende do programa, e a especificação o amarra ao código publicado em camadas:

• Compilação reproduzível: o mesmo código-fonte gera o mesmo arquivo byte a byte; pelo menos dois grupos independentes têm de chegar à mesma impressão digital.
• Assinaturas de vários blocos: uma versão só é aprovada com um número mínimo de assinaturas, e nenhum bloco tem assinaturas suficientes sozinho.
• Registro público de versões: uma árvore como a do mural, com espelhos; a lista de versões aprovadas congela na abertura.
• Medição e atestação: a zerésima e o pacote trazem a impressão digital do programa, e um chip TPM assina essa medição na abertura (sobre um número sorteado pelo mesário) e no encerramento (sobre o último código do dia). O contador de reinícios do chip denuncia um programa trocado e restaurado no meio do dia.
• Perícia por sorteio depois da eleição.

O elo mais fraco é o próprio chip: confiar na atestação é confiar no fabricante e na guarda física das urnas. A versão 0.4 define o formato da atestação, mas ainda não a torna obrigatória, nem fixa as regras de conferência do chip e de reinícios legítimos, como depois de uma queda de energia.

Das considerações de segurança da especificação (§28), as que limitam o que o sistema promete:

• Sigilo contra a própria urna (§28.7, §28.8)

  A urna vê o voto. Um programa malicioso pode vazá-lo por canais ocultos ou escolher os números secretos de um jeito combinado com alguém de fora. A auditoria não detecta isso, porque a cédula auditada é honesta. Mitigações: geradores certificados, atestação, e no futuro aleatoriedade vinda de outro aparelho.

• Conluio de guardiões (§2.1, §28.6)

  Guardiões suficientes juntos poderiam abrir cédulas individuais, nunca alterar a contagem. As cédulas não têm identidade; ligar uma a um eleitor exige também a ordem de votação na seção, o que é viável numa seção visada e não em escala nacional.

• Auditoria ao lado do voto (§28.13)

  A cédula auditada fica no mural logo antes da depositada pelo mesmo eleitor. Ela não determina o voto depositado, porque se pode auditar qualquer escolha, mas quem audita a escolha real dá uma pista a quem conhece a ordem da fila. Daí a preferência por auditorias de fiscais.

• Urna que troca o voto e mente só no papel (§14.2)

  A urna tranca B quando o eleitor escolheu A. Se o eleitor audita, ela publica no mural a revelação verdadeira, "B", que bate com a caixa, e imprime para o eleitor um recibo que diz "A". O mural fica coerente, e o verificador público, que só olha o mural, não vê nada errado: ele não sabe o que o eleitor escolheu. A trapaça aparece quando alguém compara o recibo de papel com o mural. Como o recibo é assinado pela urna, a diferença vira prova contra ela. Por isso o recibo precisa ser conferido num aparelho independente.

• Atestação humana e chaves das urnas (§28.16 a §28.18)

  Sem nenhum mesário ou fiscal honesto, uma seção pode inflar o comparecimento até o número de inscritos. A biometria reduz muito esse espaço: com cada liberação presa à digital de um eleitor inscrito, o que sobra são as liberações sem digital (falha de leitura), que podem ser publicadas por seção como indicador. A especificação deixa a identificação fora da urna (§3: o terminal do mesário nunca envia a identidade do eleitor à urna), e a biometria deve ficar do mesmo lado, para não ligar a digital ao voto. Se as chaves das urnas fossem geradas fora delas, quem as guardasse poderia forjar uma seção inteira; a defesa é gerá-las dentro dos aparelhos e exigir assinaturas de fiscais certificados pelos partidos.

• Futuro e escala (§28.12, §28.19)

  Um computador quântico grande abriria as caixas já publicadas, sem alterar contagens já conferidas. Cargos proporcionais com muitas opções custam muitas provas por cédula, e provas em lote são prioridade.

1. M. Bellare e P. Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. ACM CCS, 1993.
2. J. Benaloh. Simple Verifiable Elections. USENIX/ACCURATE EVT, 2006.
3. J. Benaloh. Ballot Casting Assurance via Voter-Initiated Poll Station Auditing. USENIX/ACCURATE EVT, 2007.
4. J. Benaloh, R. Rivest, P. Y. A. Ryan, P. Stark, V. Teague e P. Vora. End-to-End Verifiability. arXiv:1504.03778, 2015.
5. D. Bernhard, V. Cortier, D. Galindo, O. Pereira e B. Warinschi. SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions. IEEE S&P, 2015.
6. D. Bernhard, O. Pereira e B. Warinschi. How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios. ASIACRYPT, 2012.
7. C. Bormann e P. Hoffman. Concise Binary Object Representation (CBOR). RFC 8949, 2020.
8. D. Chaum. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. Communications of the ACM 24(2), 1981.
9. D. Chaum e T. P. Pedersen. Wallet Databases with Observers. CRYPTO, 1992.
10. V. Cortier e B. Smyth. Attacking and Fixing Helios: An Analysis of Ballot Secrecy. IEEE CSF, 2011.
11. V. Cortier, D. Galindo, R. Küsters, J. Müller e T. Truderung. SoK: Verifiability Notions for E-Voting Protocols. IEEE S&P, 2016.
12. R. Cramer, I. Damgård e B. Schoenmakers. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. CRYPTO, 1994.
13. R. Cramer, R. Gennaro e B. Schoenmakers. A Secure and Optimally Efficient Multi-Authority Election Scheme. EUROCRYPT, 1997.
14. H. de Valence, J. Grigg, M. Hamburg, I. Lovecruft, G. Tankersley e F. Valsorda. The ristretto255 and decaf448 Groups. RFC 9496, 2023.
15. T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31(4), 1985.
16. P. Feldman. A Practical Scheme for Non-interactive Verifiable Secret Sharing. IEEE FOCS, 1987.
17. A. Fiat e A. Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO, 1986.
18. R. Gennaro, S. Jarecki, H. Krawczyk e T. Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. Journal of Cryptology 20(1), 2007.
19. L. Goveia. eg/v1: End-to-End Verifiable Election Protocol, rascunho 0.4. Especificação técnica (SPEC.md), 2026.
20. R. Haenni, P. Locher, R. Koenig e E. Dubuis. Pseudo-Code Algorithms for Verifiable Re-Encryption Mix-Nets. FC Workshops, 2017.
21. R. Küsters, T. Truderung e A. Vogt. Clash Attacks on the Verifiability of E-Voting Systems. IEEE S&P, 2012.
22. C. Lamb e S. Zacchiroli. Reproducible Builds: Increasing the Integrity of Software Supply Chains. IEEE Software, 2022.
23. B. Laurie, E. Messeri e R. Stradling. Certificate Transparency Version 2.0. RFC 9162, 2021.
24. R. C. Merkle. A Digital Signature Based on a Conventional Encryption Function. CRYPTO, 1987.
25. T. P. Pedersen. A Threshold Cryptosystem without a Trusted Party. EUROCRYPT, 1991.
26. D. Pointcheval e J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology 13(3), 2000.
27. R. L. Rivest. On the Notion of "Software Independence" in Voting Systems. Philosophical Transactions of the Royal Society A 366(1881), 2008.
28. C.-P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology 4(3), 1991.
29. A. Shamir. How to Share a Secret. Communications of the ACM 22(11), 1979.
30. B. Terelius e D. Wikström. Proofs of Restricted Shuffles. AFRICACRYPT, 2010.
31. Trusted Computing Group. Trusted Platform Module 2.0 Library Specification.
32. Y. Tsiounis e M. Yung. On the Security of ElGamal Based Encryption. PKC, 1998.