Informe eSAMCid sobre el voto electrónico

Inicio Anterior Abajo Siguiente

2. Protocolos criptográficos para sistemas de voto electrónico

2.1 Protocolos de Pollsterless o papeletas precifradas
2.2 Modelo de las dos agencias
2.3 Protocolos de recuento homomórfico
2.4 Protocolos de Mezcla o Mixing
2.4.1 Mixnets de descifrado
2.4.2 Mixnet de recifrado

A partir de la solución básica explicada en la sección 1.5 se han ido desarrollando protocolos criptográficos más complejos con el objetivo de cumplir con los requisitos de seguridad de los procesos electorales. Estos protocolos han sido diseñados para voto electrónico o se han desarrollado a partir de herramientas utilizadas en escenarios con requisitos de seguridad similares (por ejemplo, navegación anónima con sistemas como TOR [27]). Los protocolos que explicaremos se centran en proporcionar anonimato a los votantes (o secreto de voto) al mismo tiempo que cumplen con los requisitos de autenticación y precisión de los resultados. Estos protocolos se pueden dividir en cuatro tipos básicos:

2.1. Protocolos de Pollsterless o papeletas precifradas

Estos protocolos [4564] aplican medidas criptográficas principalmente en la fase de preelección, en la fase de diseño de las papeletas: a cada opción de voto se le asigna un código resultante de cifrar la opción. Las papeletas con los valores de los precifrados de cada opción de votación se envían a los votantes antes de la fase de votación (ver figura 3).


Figura 3: Protocolo de Pollsterless.

Estos métodos reciben el nombre de Pollsterless porque, a diferencia del esquema de la sección 1.5, no necesitan que el terminal de voto tenga capacidad criptográfica para cifrar las opciones de voto del votante: en vez de que el terminal de voto cifre y firme el voto, el votante introduce el código del precifrado que aparece al lado de la opción deseada en la papeleta de voto que ha recibido, para que el terminal lo envíe al servidor remoto. La generación de los códigos y su distribución se hace de manera que sólo el votante conoce el valor de sus códigos y a qué opciones representan. Una ventaja de estos métodos es que se pueden usar para votar mediante el móvil , por ejemplo con un mensaje SMS.

El mecanismo de diseño de las papeletas es el siguiente:

Antes del periodo de votación se envían por correo las papeletas asignadas de forma aleatoria a los votantes.

Iniciada la fase de votación, el votante accede a la aplicación de voto y emite su voto enviando la identificación única de la papeleta (CardID) y los códigos correspondientes a los candidatos escogidos (PCIN). El servidor recibe el voto y calcula los códigos de retorno (RID) a partir de los códigos recibidos (PCIN) y de su clave secreta. El votante recibe los códigos de retorno (RID) y comprueba si su valor coincide con los códigos de retorno de su papeleta asignados a las opciones escogidas. Así, el votante puede comprobar que su voto ha sido recibido y procesado correctamente por el servidor de voto, dado que un atacante no puede conocer por adelantado los códigos de retorno correspondientes a las opciones enviadas.

Finalmente, en la fase de recuento, se recupera la información de los candidatos relacionados con los códigos (PCIN) de los votos, usando la clave secreta asignada al identificador de la papeleta (CardID).

Desde el punto de vista de la privacidad, estos protocolos permiten:

El problema es que aún existe la posibilidad de romper la privacidad del votante si las papeletas con los valores precifrados son comprometidas. Por ejemplo, un tercero podría conocer la intención de voto de un votante interceptando los códigos del voto emitido y comparando los valores con los de la papeleta.

2.2. Modelo de las dos agencias

Estos protocolos [193149] implementan las medidas criptográficas en la fase de votación y se centran en conseguir un canal de voto anónimo para que el votante pueda emitir su voto sin necesidad de revelar su identidad.

El modelo de las dos agencias (ver figura 4) se basa en la existencia de dos servicios completamente independientes: uno para identificar al votante y otro para emitir el voto.


Figura 4: Modelo de las dos agencias.

En estos esquemas, normalmente se utiliza un esquema de firma ciega [20], el Servicio Validador firma el voto que emitirá el votante sin saber exactamente qué está firmando (el contenido del voto). Este tipo de firma puede conseguirse gracias a ciertas propiedades matemáticas de algunos algoritmos como el RSA, por ejemplo, la maleabilidad [66]. Un algoritmo de cifrado con esta propiedad es aquel que al realizar una operación sobre el cifrado de un mensaje y descifrar el resultado se obtiene el mensaje original transformado. Por ejemplo, si E(v) es el cifrado de un voto y lo operamos con un entero r, diremos que el algoritmo de cifrado es maleable si el descifrado D(E(v) ⋅ r)) = v ∗ s.

En un algoritmo de firma ciega basado en RSA, se multiplica el mensaje m por un entero r (llamado factor de ceguera) elevado a e (clave pública) módulo N (clave pública). El servicio de firma firma el mensaje cegado con su clave privada (mre)d = mdred = mdr. Ahora ya, quitando el factor de ceguera r queda el mensaje m firmado, sin que el servicio de firma lo conozca. Hay que puntualizar que en un esquema real de firma ciega, el valor a firmar no sería el mensaje m sino H(m), donde H denota una función criptográfica unidireccional como por ejemplo una función de hash [61].

El proceso de voto es el siguiente:

Cuando acaba la fase de votación, los votos se descifran con la clave privada de la elección y se cuentan para obtener los resultados.

Estos sistemas protegen la privacidad del votante mediante:

Hay que tener presente que la privacidad del votante depende principalmente de que las dos entidades no colaboren, ya que en caso contrario podrían compartir información (por ejemplo, direcciones IP de conexión) que permitirían relacionar los votos con los votantes.

También existe el riesgo de manipulación de la elección en caso de que el Servicio de Validación se vea comprometido: esta entidad puede generar de forma arbitraria votos cifrados y firmados que serían aceptados por el Servicio de Voto.

2.3. Protocolos de recuento homomórfico

Estos protocolos [1623] actúan principalmente en la fase de recuento. Utilizan propiedades homomórficas de ciertos sistemas de cifrado, en el sentido de que cierta operación entre los votos cifrados corresponde al cifrado del resultado de cierta operación entre los votos en claro.

Es decir, si tenemos dos votos v1 y v2 y sus correspondientes cifrados E(v1), E(v2), suponiendo ⋅ y ∗ dos operaciones algebraicas, un cifrado homomórfico se define como aquel que satisface:

E (v1) ∗ E (v2) = E(v1 ⋅ v2)

Según la operación de los votos sea la suma o el producto, se habla de homomórfico aditivo o multiplicativo.

El homomorfismo aditivo es el más utilizado en votación electrónica. Dado que permite obtener directamente la suma de los votos. No todos los algoritmos tienen estas propiedades, los más utilizados son ElGamal [28] o Paillier [50]. En ambos casos, el resultado de multiplicar los votos cifrados es la suma de votos cifrada.

E (v1) ⋅ E (v2) = E (v1 + v2)

Entonces, sólo es necesario descifrar el resultado del producto de cifrados, para obtener la suma de los votos. Como se verá más adelante, los votos han de tener un formato numérico especial para obtener como resultado el número de veces que se ha seleccionado cada candidato u opción de voto por separado.

En el homomorfismo multiplicativo, el resultado de multiplicar los votos cifrados es el cifrado de la multiplicación de los votos.

E(v1) ⋅ E (v2) = E (v1 ⋅ v2)

Éste se usa menos en votación electrónica, ya que no se obtiene de forma directa la suma de los votos.

Dependiendo del homomorfismo que se utilice, el voto se representa de maneras diferentes. Por ejemplo, en el caso de homomorfismo multiplicativo se suele usar ElGamal en su versión exponencial: un elemento g de un grupo se usa para representar una opción de voto y se eleva a 1 o 0 según esa opción se elija o no. El valor resultante se cifra con el algoritmo de ElGamal, entonces, los votos cifrados se suelen representar por un vector con tantas posiciones como candidatos u opciones posibles, y en cada posición aparece el elemento correspondiente elevado a 0 o a 1, cifrado con la clave pública de la elección. La razón de cifrar individualmente cada posición es que así se pueden operar individualmente los cifrados de cada posición, correspondientes a un candidato concreto, de varios votos, y obtener el número de veces que ese candidato ha sido seleccionado. Por ejemplo, suponiendo que el voto tiene un máximo de 5 candidatos y el votante ha elegido el segundo y el quinto, el voto se representaría como (E(g0),E(g1),E(g0),E(g0),E(g1)), donde E(gx) denota el cifrado del valor gx usando el algoritmo de ElGamal. La representación de las opciones de voto en un formato conveniente y su cifrado, así como la firma con la clave privada del votante, se hace en el cliente de voto antes de enviarlo al servidor de voto remoto.


Figura 5: Ejemplo de proceso de recuento homomórfico.

Utilizando exponentes para representar las selecciones, si se multiplican los votos cifrados (efectuando dicho producto por separado en cada coordenada del vector que representa el voto), se obtendrá la suma del número de selecciones que ha recibido cada candidato (ver figura 5). Debe tenerse en cuenta que, después de descifrar el resultado, es necesario calcular el logaritmo discreto en base g para obtener el número de selecciones, o bien se puede tener precalculado gx para todos los valores x de selecciones posibles.

Los protocolos basados en recuento homomórfico proporcionan una buena protección de la privacidad del votante gracias a las siguientes cualidades:

El problema de este tipo de protocolos está relacionado con la integridad de la elección: al no descifrar los votos uno a uno, en principio no es posible verificar que un votante no ha hecho trampa y ha dado más de un voto a un candidato (por ejemplo poniendo un 2 en lugar de un 1 en el exponente). Para evitar esto, estos protocolos requieren que en el momento de cifrar se generen pruebas criptográficas que permitan verificar que el voto contiene el cifrado del valor 1 o 0. Estas pruebas criptográficas se conocen como pruebas de conocimiento nulo o Zero Knowledge Proofs en inglés [56]. La propiedad de conocimiento nulo hace referencia a que el que hace la prueba puede demostrar a un verificador ciertas propiedades de unos valores que mantiene en secreto (el verificador no llega a conocerlos). En el caso que nos ocupa, esta propiedad impide que el servidor sepa si la selección del votante ha sido un 1 o un 0, pero puede comprobar que se ha elegido uno de estos dos valores. Estas pruebas criptográficas incrementan de forma sustancial el número de cálculos a realizar en el cliente de voto y están directamente relacionadas con el número de candidatos/opciones de la elección, por lo que son sistemas poco escalables.

2.4. Protocolos de Mezcla o Mixing

Estos protocolos [10] actúan en la fase de recuento. Se basan en imitar las elecciones convencionales, cuando al acabar la elección la urna se agita para romper el orden en que los votos se han depositado.

Los votos emitidos por los votantes, cifrados y firmados previamente a su envío al servidor de votación, se almacenan. Cuando acaba la elección, los votos se separan de sus respectivas firmas digitales (una vez verificadas) y se pasan por un proceso de Mixing para desordenarlos según una permutación secreta. Gracias a este proceso se pierde la relación entre los votos y sus firmas y los votos ya no pueden vincularse con los votantes que los han emitido, con lo que puede procederse a su descifrado para obtener el resultado.

Para realizar este proceso de mezcla se usa una red de nodos denominados Mix-nodes que, por turnos, van recibiendo los votos de salida del nodo anterior y se permutan según unos valores secretos para que el orden original no pueda ser restablecido una vez mezclados (ver figura 6).


Figura 6: Esquema de recuento basado en una Mixnet.

Para evitar que se pueda restablecer el orden original mediante la comparación de las entradas y salidas de cada nodo, los nodos, además de aplicar la permutación, aplican una transformación sobre cada voto cifrado que impida su relación con el voto entrante correspondiente. Esta transformación suele consistir en una operación de descifrado o recifrado de forma que se cambia el aspecto de los votos cifrados sin variar su contenido (voto en claro).

2.4.1. Mixnets de descifrado

Presentadas por primera vez en [19], originalmente se usaba el algoritmo RSA para cifrar los votos en este tipo de mixnets. Los votos son cifrados por los votantes en varias capas, tantas veces como nodos hay en la mixnet, y cada vez con la clave pública de un nodo diferente, comenzando por el último y acabando por el primero. Cuando los votos entran en la mixnet, cada nodo permuta los votos y usa su clave secreta para eliminar la capa correspondiente de cifrado de los votos. Este proceso se repite en cada nodo hasta que el último elimina la última capa de cifrado y proporciona los votos descifrados. El principal inconveniente de este sistema es que el votante ha de cifrar su voto tantas veces como nodos hay en la mixnet, y que, debido al relleno (padding) que añade el algoritmo RSA al contenido antes de cifrar, la medida del voto se incrementa con cada capa de cifrado. Con el uso de algoritmos de cifrado como el de ElGamal (puesto en práctica más tarde) estos inconvenientes se eliminan ya que el votante puede cifrar el voto una única vez con la clave resultante del producto de las claves públicas de los nodos de la mixnet y este algoritmo no introduce padding.

2.4.2. Mixnet de recifrado

En este tipo de mixnet se usan algoritmos de cifrado que permiten la realeatorización del voto, sin añadir (hablando en términos prácticos) otra capa de cifrado al voto. Es decir, recifrar un voto cambia su valor (propiedad de realeatorización) y, tras cifrar varias veces el voto sólo hay que descifrar una vez para recuperar su valor en claro. El algoritmo RSA añade un padding aleatorio al valor del voto: [([([v|pad1]e (mod n))|pad2]e (mod n))|pad3)e (mod n) (donde | denota una operación de concatenación) que hace que no sea posible recuperar el valor del voto descifrando una sola vez, sino que es necesario descifrar tantas veces como se haya cifrado, para sacar en cada paso el padding que se había añadido. ElGamal es un ejemplo de algoritmo con propiedades aleatorizantes que no usa padding. El cifrado de un voto con ElGamal es E(v) = (gr (mod p),vhr (mod p)), donde g,p,h son el generador, el módulo y la clave pública del algoritmo, respectivamente, r es un valor aleatorio y v es el valor del voto. En ElGamal recifrar con la misma clave pública equivale a modificar el valor aleatorio en los exponentes: E′(v) = (gr,vhr) ⋅ (gr′,hr′) = (gr+r′,vhr+r′).

Sólo es necesaria una operación para recuperar v.

Entonces, en este tipo de mixnet cada nodo, en su turno, recifra los votos para evitar que a su salida puedan compararse directamente con los valores a su entrada. Cuando los votos han pasado por todos los nodos de la mixnet, se realiza una única operación de descifrado. Los valores de realeatorización aplicados en cada nodo se mantienen en secreto, igual que la permutación, para evitar que se pueda descubrir el orden original de los votos, que se pueden relacionar con las firmas de los votantes que los han emitido.

En estos protocolos la privacidad del votante se consigue mediante

El principal inconveniente de los protocolos de mixing es que actúan como una caja negra que transforma y mezcla votos, su seguridad se basa en que los valores de transformación y permutación se mantengan en secreto, por lo que su auditoría, aunque crucial, no es fácil. Si la mixnet no permuta los votos correctamente o revela los valores de la permutación y/o realeatorización aplicados sobre los votos, se podría llegar a correlacionar los votos descifrados con los votantes que los han emitido. Además, dado que la mixnet cambia el valor de los votos que entran para evitar su rastreo, ya sea descifrándolos o recifrándolos, también podría cambiar el contenido de estos votos o sustituirlos sin ser detectado.

Como ventajas de estos protocolos podemos destacar que usan algoritmos de cifrado que permiten una representación del voto más general, permitiendo procesar votos que contengan textos escritos por los votantes (write-ins), y en general pueden ser usados en elecciones complejas.

Inicio Anterior Arriba Siguiente