Democracia não é um voto, é uma contagem de votos.
Tom StoppardPara os pesquisadores de criptografia, a votação eletrônica não está principalmente conectada à máquina de votação e não à votação on-line - é apenas um
campo para pesquisa matemática . A pesquisa de votação eletrônica se preocupa com a criação de protocolos, componentes matemáticos essenciais,
sistemas de votação seguros e
verificáveis ou sistemas nos quais auditores independentes e eleitores podem verificar com segurança a exatidão da contagem de votos. Esses sistemas não são simples trabalhos teóricos, mas já são tecnologias reais usadas para eleições reais: em Tacoma Park, Maryland, os eleitores confiaram no sistema
Scantegrity II , com base em cédulas de papel invisíveis, e os próprios criptografadores usaram os sistemas de votação on-line da
Helios . para a
eleição da liderança.
A votação eletrônica é um tópico extremamente complicado, portanto, neste artigo, vou me limitar a conceitos-chave: o que significa verificação de voz segura significa, como posso contar votos sem abordar cada um individualmente e o que impede que os eleitores trapaceiem. Não darei a você uma descrição completa de todo o protocolo de votação eletrônica com todas as suas nuances, mas aqueles que desejarem poderão procurar de forma independente trabalhos sobre esse tópico, dos
quais existem muitos .
Confirmação segura
O que esperar de um sistema de votação seguro?
Primeiro, e mais óbvio: você precisa verificar se as cédulas são contadas corretamente, ou seja, para que todos possam confirmar que a contagem final é feita de acordo com o número de cédulas concluídas pelos eleitores. A verificação não deve fornecer nenhuma informação adicional, exceto os totais. Em particular, o revisor não deve ser capaz de adivinhar quem votou. Isso é equivalente à contagem manual clássica das cédulas em papel.
Em segundo lugar, é necessário que qualquer eleitor possa garantir que seu voto seja contado e contado corretamente. Isso deve ser feito sem divulgar seu voto e, em um caso mais geral, o eleitor não deve poder provar em quem votou. Isso é feito para eliminar a coerção e para permitir que os eleitores escolham livremente um candidato sem medo das consequências de sua escolha.
Finalmente, o sistema de votação deve ser protegido contra fraudes: o eleitor não deve poder votar mais de uma vez e não deve haver a capacidade de alterar ou copiar a cédula. Além disso, apenas os eleitores registrados devem poder votar.
Para resumir: precisamos de escrutínio público, confiança dos eleitores, resistência à coerção e integridade das eleições. Esses princípios foram apresentados em um estudo fundamental de Chaum, Neff e outros, publicado no início dos anos 2000.
Princípios básicos
A maioria dos protocolos clássicos de votação eletrônica funciona da seguinte maneira:
- O eleitor recebe um token na forma de boletim, que muda de acordo com sua escolha. Diferentes eleitores recebem cédulas diferentes.
- O eleitor criptografa a votação (usando um tipo especial de criptografia que permite que a mágica da votação eletrônica funcione, e a envia para que os organizadores da votação recebam uma votação criptografada.
- Os organizadores publicam boletins criptografados no quadro de avisos, o "canal público de transmissão com memória", no jargão dos criptógrafos - para simplificar, algo como Pastebin.
- Os organizadores combinam cédulas criptografadas para calcular um resultado em cache. Então eles decodificam (mas não as próprias cédulas!) E publicam os resultados.
- Depois de receber o resultado e as vozes criptografadas, qualquer pessoa pode verificar sua correção.
Contagem Segura: Criptografia Homomórfica
Na quarta etapa, os organizadores combinam criptogramas para criar um novo criptograma que criptografa a soma dos votos individuais. Para isso, os esquemas de votação eletrônica usam o esquema de criptografia Enc (), no qual você pode calcular o Enc (v1 + v2), tendo apenas o Enc (v1) e o Enc (v2) em mãos e sem conhecer a chave de criptografia. Esses esquemas de criptografia são chamados de
homomórficos .
Por exemplo, se bastante simplificado, os eleitores dos EUA fazem o seguinte em 8 de novembro:
- Eles recebem o boletim de notícias de Clinton e Trump dos organizadores (por simplicidade, consideraremos apenas dois candidatos).
- Eles escrevem Enc (1) em uma cédula e Enc (0) na outra, usando a chave pública emitida pelos organizadores como chave.
As cédulas criptografadas são então publicadas no quadro de avisos junto com a identificação do eleitor. Conheço todos que votaram, mas é impossível entender quem exatamente, porque cada Enc (0) e Enc (1) são únicos e usamos criptografia forte e aleatória. Se a criptografia fosse determinística, o eleitor poderia ser forçado a revelar sua voz computando Enc (0) novamente e comparando-o com o valor do quadro.
Finalmente, os organizadores combinam todas as cédulas de voto para Clinton e obtêm o resultado de Enc (o número de votos para Clinton) e, em seguida, fazem o mesmo com as cédulas para Trump e obtêm Enc (o número de votos para Trump). Em seguida, eles pegam a chave de descriptografia e descriptografam esses dois valores, declarando o vencedor.
Como encontrar um esquema de criptografia homomórfica? Bastante fácil - circuitos como RSA e ElGamal são homomórficos em sua forma básica porque satisfazem a equação
Enc (v1) × Enc (v2) = Enc (v1 × v2)
Mas não é exatamente disso que precisamos - é um homomorfismo multiplicativo, mas precisamos de um aditivo. Existem truques que transformam os esquemas RSA e ElGamal em esquemas aditivamente homomórficos, mas, em vez disso, mostrarei um esquema menos conhecido que é imediatamente aditivamente homomórfico:
o sistema de criptografia Paye criptografa a mensagem v1 para
Enc (v1) = g
v1 r1
n mod n
2Onde n = pq e g são fixos e r1 é um número inteiro aleatório de] 1; n
2 [. Portanto, temos:
Enc (v1) × Enc (v2) = (g
v1 r1
n ) × (g
v2 r2
n ) mod n
2 = g
v1 + v2 (r1r2)
n mod n
2 = Enc (v1 + v2)
Ou seja, o esquema Peye pode ser usado para calcular votos criptografados.
Para trapacear, um eleitor pode escrever Enc (10000) em vez de Enc (1) na cédula para adicionar votos ao candidato. No caso de más intenções, você pode escrever Enc (número_muito_large) para que isso leve a um estouro do todo e a uma falha do sistema inteiro. Como garantir a validade da voz (0 ou 1) sem descriptografia?
A solução é o
conhecimento zero não interativo (NIZK). A prova do NINR é um objeto criptográfico muito complexo e extremamente poderoso: no nosso caso, permitirá ao eleitor provar que seu criptograma contém 0 ou 1, mas sem mostrar a mensagem criptografada. No caso geral, as provas do NINR permitem ao provador convencer o verificador da verdade da declaração, enviando a ele apenas um conjunto de dados sem outros tipos de interação.
Talvez o sistema mais simples com divulgação zero seja
o esquema de Schnorr : digamos que você conhece a solução para o problema do logaritmo discreto (a tarefa difícil por trás do
DSA e criptografia nas curvas elípticas), e você deseja provar que conhece a solução sem divulgar a solução em si. Ou seja, você conhece x de modo que g
x = y mod p, e o examinador conhece apenas g, ye ep. Para convencer o revisor, você joga o seguinte jogo:
- Escolha um número aleatório r e envie o valor g r para o testador (obrigação).
- Você obtém um número aleatório s do testador (chamada).
- Enviar para o verificador s = r + cx.
- O revisor calcula g s = g r + cx e verifica se é igual a g r × y c = g r × (g x ) c .
Nesse protocolo interativo, o provador não divulga o valor de x, pois envia apenas números aleatórios. No entanto, somente o provador que conhece x pode enviar s, passando no último teste.
Para transformar esse protocolo interativo em um não interativo (que pode ser enviado com um conjunto de dados), são construídas provas NINR. Jogamos esse jogo por conta própria e fingimos ser um testador, para que o testador real garanta que não possamos criar a prova de NINR sem conhecer a declaração comprovada.
Conclusão
Idéias principais discutidas neste artigo:
- O principal problema de um sistema de votação eletrônica seguro é a audibilidade pública. Isso é possível através da publicação de boletins criptografados em um fórum acessível ao público. Os eleitores também devem descrever o mecanismo que conduz a confirmação em si.
- A correção do voto é confirmada, autorizando cada eleitor com uma identificação única e dando aos eleitores acesso que lhes permite verificar se sua cédula 1) foi contada e 2) não foi alterada.
- Os eleitores não podem ser punidos por votar em candidatos "errados" devido à resistência à coerção, que, em particular, é alcançada por meio de criptografia imprevisível e probabilística.
- A privacidade das cédulas é garantida pelo fato de que os votos criptografados não são descriptografados e apenas o resultado criado usando a criptografia homomórfica é descriptografado.
- O golpe não funciona se forçarmos os eleitores a publicar evidências criptográficas da validade de sua votação usando o NINR.
Os conceitos e tecnologias descritos aqui podem parecer profundos e complexos, mas, na realidade, isso é apenas a ponta do iceberg. Você não pode criar um sistema de votação eletrônica que funcione com segurança simplesmente seguindo a descrição. Por exemplo, omiti detalhes como a maneira como os eleitores verificam suas cédulas na prática, o motivo do uso do servidor NINR e assim por diante. O ponto principal é que qualquer protocolo de votação eletrônica segura é uma coisa muito complicada e cheia de nuances, e a implementação real acrescenta complexidade adicional devido a fatores humanos e organizacionais.
Para saber mais sobre criptografia relacionada ao tópico da votação eletrônica, você pode estudar estes materiais de qualidade: