Protocolos criptográficos para votación electrónica.

La democracia no es un voto, es un recuento de votos.
Tom Stoppard

Para los investigadores de criptografía, la votación electrónica no está relacionada principalmente con la máquina de votación y no con la votación en línea: es solo un campo para la investigación matemática . La investigación de votación electrónica crea protocolos, componentes matemáticos clave, sistemas de votación seguros y verificables , o sistemas en los que los auditores independientes y los votantes pueden verificar con seguridad la exactitud del recuento de votos. Estos sistemas no son simples trabajos teóricos, sino tecnologías reales utilizadas para elecciones reales: en Tacoma Park, Maryland, los votantes confiaron en el sistema Scantegrity II , basado en papeletas de tinta invisibles, y los propios criptógrafos utilizaron los sistemas de votación en línea de Helios para la elección de liderazgo.

La votación electrónica es un tema extremadamente complicado, por lo que en este artículo me limitaré a conceptos clave: qué significa la verificación de voz segura, cómo puedo contar los votos sin abordarlos individualmente y qué impide que los votantes hagan trampa. No le daré una descripción completa de todo el protocolo de votación electrónica con todos sus matices, pero aquellos que lo deseen pueden buscar trabajo de forma independiente sobre este tema, del cual hay muchos .

Confirmación segura

¿Qué esperar de un sistema de votación seguro?

Primero, y lo más obvio: debe verificar que las papeletas se cuenten correctamente, es decir, para que todos puedan confirmar que el conteo final se realiza de acuerdo con el número de papeletas completadas por los votantes. El cheque no debe proporcionar información adicional, excepto los totales. En particular, el revisor no debería poder adivinar quién votó. Esto es equivalente al clásico conteo manual de papeletas.

En segundo lugar, es necesario que cualquier votante pueda asegurarse de que su voto se cuente y se cuente correctamente. Esto debe hacerse sin revelar su voto, y en un caso más general, el votante no debería poder probar por quién votó. Esto se hace para eliminar la coerción y para permitir a los votantes elegir libremente a un candidato sin temor a las consecuencias de su elección.

Finalmente, el sistema de votación debe estar protegido contra el fraude: el votante no debe poder votar más de una vez, y no debe haber la posibilidad de cambiar o copiar la boleta. Además, solo los votantes registrados deben poder votar.

Para resumir: necesitamos escrutinio público, confianza de los votantes, resistencia a la coerción e integridad de las elecciones. Estos principios fueron presentados en un estudio fundamental de Chaum, Neff y otros, publicado a principios de la década de 2000.

Principios básicos

Los protocolos de votación electrónica más clásicos funcionan de la siguiente manera:

1. El votante recibe una ficha en forma de boletín, que cambia según su elección. Los diferentes votantes reciben diferentes boletas.
2. El votante encripta la boleta (utilizando un tipo especial de encriptación que permite que funcione la magia de la votación electrónica, y la envía para que los organizadores de la votación reciban una boleta encriptada.
3. Los organizadores publican boletines encriptados en el tablón de anuncios, el "canal de transmisión pública con memoria", en la jerga de criptografía, en términos simples, en algo como Pastebin.
4. Los organizadores combinan las papeletas encriptadas para calcular un resultado en caché. Luego lo decodifican (¡pero no las papeletas en sí!) Y publican los resultados.
5. Habiendo recibido el resultado y las voces encriptadas, cualquiera puede verificar su corrección.

Cuenta segura: cifrado homomórfico

En el cuarto paso, los organizadores combinan criptogramas para crear un nuevo criptograma que encripta la suma de los votos individuales. Para esto, los esquemas de votación electrónica utilizan el esquema de cifrado Enc (), en el que puede calcular Enc (v1 + v2), teniendo solo Enc (v1) y Enc (v2) a mano, y sin conocer la clave de cifrado. Dichos esquemas de cifrado se denominan homomórficos .

Por ejemplo, si se simplifica enormemente, los votantes estadounidenses hacen lo siguiente el 8 de noviembre:

1. Reciben el boletín de Clinton y el boletín de Trump de los organizadores (por simplicidad, consideraremos solo dos candidatos).
2. Escriben Enc (1) en una boleta y Enc (0) en la otra, utilizando la clave pública emitida por los organizadores como la clave.

Las boletas encriptadas se publican en el tablón de anuncios junto con la identificación del votante. Conozco a todos los que votaron, pero es imposible entender exactamente quién, porque cada Enc (0) y Enc (1) son únicos, y utilizamos cifrado fuerte y aleatorio. Si el cifrado fuera determinista, el votante podría verse obligado a revelar su voz calculando Enc (0) nuevamente y comparándola con el valor en la pizarra.

Finalmente, los organizadores combinan todas las papeletas para Clinton y obtienen el resultado de Enc (la cantidad de votos para Clinton), y luego hacen lo mismo con las papeletas para Trump y obtienen Enc (la cantidad de votos para Trump). Luego toman la clave de descifrado y descifran estos dos valores, declarando el ganador.

¿Cómo encontrar un esquema de cifrado homomórfico? Bastante fácil: los circuitos como RSA y ElGamal son homomórficos en su forma básica porque satisfacen la ecuación

Enc (v1) × Enc (v2) = Enc (v1 × v2)

Pero esto no es exactamente lo que necesitamos: es un homomorfismo multiplicativo, pero necesitamos uno aditivo. Hay trucos que convierten los esquemas RSA y ElGamal en aditivos homomórficos, pero en su lugar mostraré un esquema menos conocido que es inmediatamente adictivamente homomórfico: el criptosistema Paye encripta el mensaje v1 a

Enc (v1) = g ^v1 r1 ⁿ mod n ²

Donde n = pq yg son fijos, y r1 es un entero aleatorio de] 1; n ² [. Por lo tanto, tenemos:

Enc (v1) × Enc (v2) = (g ^v1 r1 ⁿ ) × (g ^v2 r2 ⁿ ) mod n ² = g ^{v1 + v2} (r1r2) ⁿ mod n ² = Enc (v1 + v2)

Es decir, el esquema de Peye se puede usar para calcular votos cifrados.

Prevención del fraude: evidencia de divulgación cero

Para hacer trampa, un votante puede escribir Enc (10000) en lugar de Enc (1) en la boleta para agregar votos al candidato. En caso de malas intenciones, puede escribir Enc (very_large_number) para que esto provoque un desbordamiento del conjunto y un fallo de todo el sistema. ¿Cómo garantizar la validez de voz (0 o 1) sin descifrado?

La solución es el conocimiento cero no interactivo (NIZK). La prueba NINR es un objeto criptográfico muy complejo y extremadamente poderoso: en nuestro caso, permitirá al votante probar que su criptograma contiene 0 o 1, pero sin mostrar el mensaje cifrado. En el caso general, las pruebas NINR permiten al probador convencer al verificador de la verdad de la declaración enviándole solo un conjunto de datos sin ningún otro tipo de interacción.

Quizás el sistema más simple con cero divulgación es el esquema Schnorr : supongamos que conoce la solución al problema del logaritmo discreto (la tarea difícil detrás del DSA y el cifrado en curvas elípticas), y desea demostrar que conoce su solución sin revelar la solución en sí. Es decir, sabes x tal que g ^x = y mod p, y el examinador solo sabe g, y y p. Para convencer al crítico, juegas el siguiente juego:

1. Elija un número aleatorio r y envíe el valor g ^{r al probador} (obligación).
2. Obtiene un número aleatorio s del probador (llamada).
3. Enviar al verificador s = r + cx.
4. El revisor calcula g ^s = g ^{r + cx} y verifica que es igual a g ^r × y ^c = g ^r × (g ^x ) ^c .

En este protocolo interactivo, el probador no revela el valor de x, ya que solo envía números aleatorios. Sin embargo, solo el probador que sabe x puede enviar s, pasando la última prueba.

Para convertir dicho protocolo interactivo en uno no interactivo (uno que se puede enviar con un conjunto de datos), se crean pruebas NINR. Jugamos este juego por nuestra cuenta y pretendemos ser un probador para que el probador real se asegure de que no podamos encontrar una prueba NINR sin conocer la declaración comprobada.

Conclusión

Ideas clave discutidas en este artículo:

• El principal problema con un sistema de votación electrónica seguro es la audibilidad pública. Esto se logra mediante la publicación de boletines cifrados en un foro de acceso público. Los votantes también deben describir el mecanismo que lleva a cabo la confirmación en sí.
• La exactitud del voto se confirma al autorizar a cada votante con una identificación única y darles acceso a los votantes que les permite verificar que su boleta 1) se haya contado y 2) no se haya cambiado.
• Los votantes no pueden ser castigados por votar por candidatos "incorrectos" debido a la resistencia a la coerción, que, en particular, se logra mediante un cifrado impredecible y probabilístico.
• La privacidad de las boletas está garantizada por el hecho de que los votos cifrados no se descifran, y solo se descifra el resultado creado con cifrado homomórfico.
• La estafa no funciona si forzamos a los votantes a publicar evidencia criptográfica de la validez de su boleta usando NINR.

Los conceptos y tecnologías descritos aquí pueden parecer profundos y complejos, pero en realidad esto es solo la punta del iceberg. No puede crear un sistema de votación electrónica que funcione de manera segura simplemente siguiendo la descripción. Por ejemplo, omití detalles como la forma en que los votantes revisan sus boletas en la práctica, la razón por la que usan el servidor NINR, etc. La conclusión es que cualquier protocolo seguro de votación electrónica es algo muy complicado y lleno de matices, y la implementación real agrega complejidad adicional debido a factores humanos y organizacionales.

Para obtener más información sobre la criptografía relacionada con el tema de la votación electrónica, puede estudiar estos materiales de calidad:

• Artículo de David Chaum 2004 en IEEE S&P
• Informe El futuro de la votación patrocinado por la US Vote Foundation
• Charla de Ben Adida en GoogleTech
• Cómo los factores humanos y operativos pueden comprometer los esquemas de votación electrónica
• Apuntes sobre pruebas de conocimiento cero