GUASCH CASTELLÓ, Sandra (SCYTL SECURE ELECTRONIC VOTING, SAC/ Tuset 20-2, 1r 7a Barcelona, E-08006, ES)
PUIGGALÍ ALLEPUZ, Jordi (SCYTL SECURE ELECTRONIC VOTING, SAC/ Tuset 20-2, 1r 7a Barcelona, E-08006, ES)
GUASCH CASTELLÓ, Sandra (SCYTL SECURE ELECTRONIC VOTING, SAC/ Tuset 20-2, 1r 7a Barcelona, E-08006, ES)
| REIVINDICACIONES 1. Método para verificar que una información de un emisor se ha registrado de forma correcta por parte de una entidad receptora preservando la privacidad del emisor, caracterizado por comprender las siguientes etapas: a) Codificado de la información del emisor en una entidad emisora y envío de dicha codificación a la entidad receptora; b) Generación por parte de la entidad emisora de una prueba de contenido basada en la información codificada en el paso a), y posterior envío de la prueba de contenido a la entidad emisora; y c) Verificación por parte del emisor de que la prueba de contenido se corresponde con la información que se ha codificado. 2. Método según la reivindicación 1 , caracterizado por comprender las siguientes etapas adicionales: d) Realización de un segundo codificado de la información del emisor en la entidad emisora antes o después del paso a), y envío de dicha segunda codificación a la entidad receptora; e) Cálculo de una prueba de similitud que demuestra que las codificaciones de los pasos a) y d) se han realizado sobre la misma información sin revelar dicha información, y envío de dicha segunda codificación a la entidad receptora; y f) Verificación por parte de la entidad receptora de que la prueba de similitud del paso e) se corresponde a las dos informaciones codificadas en los pasos a) y d); 3. Método según la reivindicación 1 caracterizado porque el algoritmo de codificado de la etapa a) tiene propiedades deterministas. 4. Método según la reivindicación 2 caracterizado porque el algoritmo de codificado de la etapa a) tiene propiedades probabilísticas. 5. Método según la reivindicación 2 caracterizado porque el algoritmo de codificado de la etapa d) tiene propiedades probabilísticas. 6. Método según la reivindicación 3 caracterizado porque las propiedades deterministas del algoritmo de codificado se consiguen utilizando un algoritmo de codificado probabilístico y con un exponente determinado por el emisor y el valor del mensaje. 7. Método según la reivindicación 2 caracterizado porque los algoritmos de codificado usados en las etapas a) y d) tienen propiedades homomórficas. 8. Método según la reivindicación 2 caracterizado porque en el codificado de las etapas a) y c) se usa un parámetro común, tal como la misma clave pública. 9. Método según la reivindicación 2 caracterizado porque la prueba de similitud de la etapa e) es la prueba de conocimiento nulo de que el codificado de la etapa a) es el re-codificado del codificado de la etapa d), o viceversa. 10. Método según la reivindicación 2 caracterizado porque la información codificada en las etapas a) y d) está compuesta respectivamente por un conjunto de codificaciones individuales de partes de dicha información. 11. Método según la reivindicación 9 caracterizado porque la prueba de similitud de la etapa e) está compuesta por un conjunto de pruebas de similitud entre el conjunto de las codificaciones individuales obtenidas en la etapa a) y el conjunto de las codificaciones individuales obtenidas en la etapa d). 12. Método según la reivindicación 2 caracterizado porque la prueba de contenido de la etapa b) se obtiene a partir de una función unidireccional sobre la información codificada en la etapa a), del grupo que comprende un SHA1 , SHA2 o MD5. 13. Método según la reivindicación 2 caracterizado porque la prueba de contenido de la etapa b) se genera a partir del codificado de la información codificada en la etapa a). 14. Método según la reivindicación 13 caracterizado porque la función de codificación es una función criptográfica que usa una clave secreta S asignada a la entidad receptora del grupo que comprende un cifrado simétrico o una función MAC. 15. Método según la reivindicación 9 caracterizado porque la prueba de contenido generada en la etapa b) está compuesta por el conjunto de pruebas de contenido de las codificaciones individuales de la etapa a). 16. Método según la reivindicación 15 caracterizado porque la prueba de contenido generada en la etapa b) es el resultado de la operación del conjunto de pruebas de contenido de las codificaciones individuales de la etapa a). 17. Método según la reivindicación 1 caracterizado porque la verificación de la etapa c) se basa en la posesión por parte del emisor de los valores de las pruebas de contenido correspondientes a cada posible información válida. 18. Método según la reivindicación 17 caracterizado por comprender una etapa adicional g) de generación de los valores de las pruebas de contenido correspondientes a cada posible información válida y envío de estos valores a los emisores. 19. Método según la reivindicación 17 caracterizado porque la verificación de la etapa c) se realiza comparando los códigos de contenido generados en la etapa b) con aquellos que el emisor posee. 20. Método según la reivindicación 4 caracterizado por realizar una etapa adicional h) de descodificado parcial de la información codificada en la etapa a) antes de generar la prueba de contenido de la etapa b). |
INFORMACIÓN
Campo de la invención
La presente invención es apta para aplicaciones donde se requiere verificar que una información ha sido registrada de forma correcta. Concretamente, es apta para verificar que la información enviada por un emisor ha sido recibida correctamente en el receptor. Esta invención es de especial relevancia en procesos de envío de información donde se debe preservar la privacidad de la entidad emisora.
El método es susceptible de ser utilizado en entornos de voto electrónico remoto.
Antecedentes de la invención
Cuando es necesario el envío de información a través de un medio considerado no seguro conservando la confidencialidad del emisor, esta se cifra de forma que sólo el destinatario sea capaz de descifrarla. De este modo, otras personas, entidades o sistemas que accedan a esta información serán incapaces de leerla.
A pesar de la protección que ofrece el codificado, este se limita sólo a la privacidad del emisor pero no a la integridad del mensaje. Por lo tanto, la información a enviar puede ser modificada durante el proceso de codificado o el envío. Para evitar que la información sea modificada, el emisor de la información debe poder detectar esta modificación verificando que la información registrada en el receptor es la misma que el emisor ha enviado. Las firmas digitales permiten asegurar la integridad de la información codificada durante su envío, pero no permiten verificar que antes del envío la información ha sido correctamente codificada. En este aspecto, el emisor generalmente debe confiar en el proceso de codificado. Este proceso, normalmente ejecutado por un software específico, puede ser manipulado por una entidad externa para que cifre información distinta a la que el emisor pretende enviar. Una solución sería firmar la información antes de codificarla y adjuntar la firma con la información codificada. El problema de esta solución es que no permite preservar el anonimato del emisor, puesto que la firma permite vincularlo con la información una vez descodificada.
En situaciones en las que el receptor inicial de la información codificada no es el destinatario final y, por tanto, no posee la capacidad de descifrarla, probar que la información codificada recibida se corresponde con la que el emisor ha enviado (antes del proceso de codificado) puede ser un proceso complejo. Existen diversos métodos que tratan de presentar soluciones a este problema. Comprobación de que la información enviada coincide con la que se ha querido enviar
Existen entornos en los que es importante que un emisor que envía un mensaje codificado a una entidad receptora, pueda verificar que el mensaje codificado recibido coincide con los contenidos que ha escogido enviar sin comprometer el secreto de la información enviada (al menos hasta que esta sea descodificada) ni el anonimato del emisor. Un ejemplo de ellos son los procesos de votación electrónica, donde el votante escoge sus opciones de voto, que son codificadas y almacenadas en un dispositivo receptor. La firma digital permite verificar que la información, una vez codificada y firmada (normalmente paso previo a su envío y/o almacenamiento), no ha sufrido ninguna manipulación, pero esta información puede manipularse durante el proceso de codificado.
En el momento en que el votante cifra sus opciones de voto, generalmente debe confiar en que el proceso de codificado realmente cifra las opciones escogidas, y que, por tanto, son estas las que se almacenan en el receptor.
Existen varias técnicas desarrolladas para permitir al votante verificar que el mensaje codificado enviado se corresponde con su intención de voto. Algunas de estas técnicas realizan una verificación extremo a extremo, en la que el receptor del mensaje codificado demuestra al emisor que el contenido es el mismo que el emisor ha pretendido enviar, mientras que otras se concentran en la verificación del proceso de codificado.
Verificación punto a punto En [Ch01] y [Ma02] se presenta un método de verificación del contenido de un mensaje o voto codificado extremo a extremo, de forma que es el receptor el que proporciona al votante una prueba de que el voto codificado recibido se corresponde con las opciones escogidas por el votante.
Este método de verificación se basa en la generación previa a la fase de votación de códigos asignados a cada candidato u opción de voto, equivalentes al codificado de la opción. A partir de estos códigos, mediante una operación criptográfica (por ejemplo, una función de Hash) y un parámetro secreto, se calcula para cada uno su correspondiente código de retorno.
Estos códigos se envían en papeletas a los votantes, y se calculan de forma que sean distintos para cada votante y cada papeleta.
En el momento de la votación, el votante selecciona los códigos correspondientes a las opciones de voto elegidas y los envía al servidor de voto. El servidor de voto calcula a partir de los códigos de las opciones de voto los códigos de retorno correspondientes usando el parámetro secreto que sólo él conoce. A continuación, envía los códigos de retorno al votante, que comprueba que coinciden con los códigos de retorno impresos en su papeleta de voto al lado de las opciones de voto seleccionadas.
Dado que solamente el servidor de voto conoce el parámetro secreto para generar los códigos de retorno, y que éstos no están previamente almacenados, sino que se calculan a partir de los códigos recibidos, el votante puede verificar que las opciones escogidas concuerdan con las que se han recibido en el servidor. Además, como los códigos de retorno se calculan a partir de los códigos de las opciones de voto, el secreto del voto se mantiene.
La debilidad de este método reside en la protección de las papeletas de voto. Dado que los códigos de candidato son distintos para cada papeleta de voto y no guardan ninguna relación con los nombres de los candidatos, cualquiera que accediera a las papeletas en una fase previa a la votación podría intercambiar los códigos de dos candidatos, desviando los votos de uno hacia el otro. Otro de los problemas es la usabilidad del sistema: la introducción y comprobación de códigos alfanuméricos aumenta considerablemente la complejidad del sistema de votación desde el punto de vista del votante. Verificación del proceso de codificado
En [Be06] se presenta una idea distinta, en la que la verificación va enfocada al proceso de codificado.
Después que el emisor haya escogido el contenido del mensaje, éste es codificado por una entidad que se compromete con el mensaje codificado resultante. Des este modo, a partir de este momento el mensaje codificado no puede ser modificado. Una vez realizada esta operación, el emisor puede escoger dos opciones: enviar el mensaje o, en caso de querer realizar el proceso de verificación, pedir a la entidad que ha codificado el mensaje que lo descifre para poder comprobar que el contenido del mensaje codificado se corresponde con el escogido por el emisor. En caso de realizar la verificación, el mensaje codificado (cuyo contenido ha sido desvelado) se desecha y se crea otro nuevo para proteger la privacidad del emisor. Como la decisión de verificar la decide el emisor de la información, este puede haber facilitado una información distinta a la entidad de codificación para preservar su confidencialidad cuando esta es descodificada al verificarse.
En [Ad08] se realiza una implementación basada en el sistema propuesto en [Be06]. Una vez el mensaje ha sido codificado y la entidad que ha realizado proceso se compromete con el resultado, existen dos opciones: enviar el mensaje codificado o realizar el proceso de verificación del codificado. Este método se diferencia del anterior en que, en lugar de realizar el proceso de verificación pidiendo a la entidad que ha calculado el codificado del mensaje que lo descifre, y comprobando que el resultado coincide con el mensaje escogido por el emisor, el emisor pide a la entidad que libere ciertos parámetros del codificado para poder comprobar de forma independiente que el codificado es correcto.
Otra propuesta basada en [Be06] es [Sa08]. Esta propuesta está especialmente diseñada para los lugares de votación donde los votantes votan en máquinas de voto. En la propuesta, estas máquinas están interconectadas mediante una red local aislada de redes exteriores, de forma que ningún mensaje de una red exterior pueda acceder a la red local.
Cuando un votante emite un voto codificado en una de las máquinas, éste se envía a través de la red local y se almacena en todas las máquinas del lugar de votación. Después de esta "publicación" del voto codificado en todas las máquinas, se presenta al votante la opción de verificar si el contenido del voto codificado se corresponde con las opciones elegidas o enviarlo (aunque en este caso ya se haya enviado). Si el votante decide enviar el voto codificado, la máquina simplemente guarda en el registro esa aceptación, dado que ya ha mandado el voto a las otras máquinas del lugar de votación. En cambio, si el votante decide comprobar que las opciones codificadas son las mismas que él ha elegido, la máquina publica la información con la que ha realizado el codificado a través de la red local.
Para proporcionar un método de verificación en tiempo real, se propone que la red local esté conectada a una red externa o Internet mediante un diodo de datos que asegure que la información solo circula en una dirección, de modo que un observador externo pueda observar el tráfico de la red local en tiempo real. Así, el votante o un observador externo pueden captar el voto y los parámetros de codificado para verificar que las opciones codificadas son las que se habían seleccionado en un principio. Una vez se audita un voto, éste se anula en todas las máquinas de voto a través de la red local.
La principal desventaja de estos métodos es que el votante requiere la ayuda de un sistema alternativo para verificar el correcto codificado de las opciones una vez el sistema muestra los parámetros del codificado. Para realizar esta verificación son necesarias operaciones criptográficas que no pueden ser realizadas a mano o mediante una calculadora convencional. El uso de un dispositivo alternativo para realizar estos cálculos puede ocasionar problemas de verificación y de usabilidad para el votante.
Los métodos de verificación del correcto registro de un mensaje codificado presentados tienen como principal problema la usabilidad, dado que el usuario debe realizar operaciones más o menos complejas para hacer la verificación, como la introducción y comparación de códigos, o complejas operaciones matemáticas.
La presente invención se basa en la implementación de un método para verificar el correcto registro de una información que resuelva los problemas de usabilidad de los métodos anteriormente explicados. Breve descripción de los dibujos
La Figura 1a identifica los componentes básicos del método de verificación de la recepción correcta de información:
o 101 : entidad emisora.
o 102: entidad receptora.
o 103: información a codificar.
o 104: información codificada.
o 105: pruebas de contenido.
o 106: emisor.
La Figura 1b muestra el proceso general de la invención presentada con las etapas básicas. En ella se detalla de forma visual el funcionamiento del proceso en el que la información original 103 se codifica y se envía a la entidad receptora 102, que envía unas pruebas de contenido 105 correspondientes a la información codificada 104 a la entidad emisora 101 para verificar el correcto registro de la información. Los procesos involucrados en esta Figura 1b son:
o La entidad emisora 101 codifica y envía 201 la información original 103 a la entidad receptora 102.
o La entidad receptora 102 genera unas pruebas de contenido 105 a partir de la información codificada 104 y las envía 202 a la entidad emisora 101.
o La entidad emisora 101 verifica 203 las pruebas de contenido 105 para comprobar el correcto registro de la información codificada 104 en la entidad receptora 102.
La Figura 2a identifica los componentes del método de verificación de la recepción correcta de información cuando se implementan las etapas adicionales:
o 101 : entidad emisora.
o 102: entidad receptora.
o 103: información a codificar.
o 104: información codificada (primera codificación).
o 105: pruebas de contenido.
o 106: emisor.
o 107: información codificada (segunda codificación)
o 108: prueba de similitud. La Figura 2b muestra el proceso general de la invención presentada con las funcionalidades añadidas gracias a las etapas adicionales. En esta figura se detalla de forma visual el funcionamiento del proceso en el que se realizan y envían dos codificaciones 104, 107 de la información original 103 relacionadas por una prueba de similitud 108 a la entidad receptora 102, que envía unas pruebas de contenido 105, correspondientes a la información codificada 104, 107, a la entidad emisora 101 para verificar el correcto registro de la información. Los procesos involucrados en esta Figura 2b son:
o La entidad emisora 101 codifica y envía 201 la información orig 103 a la entidad receptora 102.
o La entidad emisora 101 realiza una segunda codificación 107 de la información original 103 y la envía 204 a la entidad receptora 102.
o La entidad emisora 101 también genera y envía 205 a la entidad receptora 102 una prueba de similitud 108 que relaciona la primera codificación de la información 104 y la segunda 107.
o La entidad receptora 102 verifica 206 la prueba de similitud 108. o La entidad receptora 102 genera 202 las pruebas de contenido 105 a partir de la información codificada por primera vez 104 o por segunda vez 107 y las envía 202 a la entidad emisora 101.
o La entidad emisora 101 verifica 203 las pruebas de contenido 105 para comprobar el correcto registro de la información codificada 104, 107 en la entidad receptora 102.
La Figura 3a identifica los componentes del método de verificación de la recepción correcta de información en un ejemplo de implementación en el que existe una entidad intermedia que realiza uno o varios pasos intermedios de generación de la información cifrada:
o 101 : entidad emisora.
o 102: entidad receptora.
o 103: información a codificar.
o 104: información codificada (primera codificación).
o 105: pruebas de contenido.
o 106: emisor.
o 107: información codificada (segunda codificación). o 108: prueba de similitud.
o 109: información re-codificada.
o 110: entidad intermedia.
La Figura 3b muestra un ejemplo de implementación de la invención presentada. En la figura se detalla de forma visual el proceso en el que se realizan y envían dos codificaciones, una realizada con un algoritmo con propiedades deterministas 104 y otra realizada con un algoritmo con propiedades probabilísimas 107, se envía una prueba de similitud 108 que relaciona las dos codificaciones y se recodifica la información cifrada 104 en una entidad intermedia 110, que la envía a la entidad receptora 102 para que genere a partir de la información recodificada 109 las pruebas de contenido 105 que se envían a la entidad emisora 101. Los procesos involucrados en esta Figura 3b son:
o La entidad emisora 101 codifica de forma determinista y envía 201 la información original 103 a la entidad intermedia 110.
o La entidad emisora 101 realiza una segunda codificación probabilística 107 de la información original 103 y la envía 204 a la entidad intermedia 110.
o La entidad emisora 101 también genera y envía 205 a la entidad intermedia 110 una prueba de similitud 108 que relaciona la primera codificación de la información 104 y la segunda 107.
o La entidad intermedia 110 verifica 206 la prueba de similitud 108. o La entidad intermedia 110 realiza 207 una recodificación con un algoritmo determinista de la información codificada 104 y la envía 207 a la entidad receptora 102.
o La entidad receptora 102 genera 202 las pruebas de contenido 105 a partir de la información recodificada 109 y las envía 202 a la entidad emisora 101.
o La entidad emisora 101 verifica 203 las pruebas de contenido 105 para comprobar el correcto registro de la información codificada 104, 107.
La Figura 4 muestra otro ejemplo de implementación de la invención presentada. En la figura se detalla de forma visual el proceso en el que se realiza una segunda codificación 107 de la información original 103 en la entidad emisora 101 , que es enviada a la entidad intermedia 110 para realizar una primera codificación 104 de la información. Estas codificaciones envían a la entidad receptora 102 para generar las pruebas de contenido 105 que son enviadas a la entidad emisora 101 para verificar el correcto registro de la información. Los procesos involucrados en esta Figura 4 son:
o La entidad emisora 101 realiza una segunda codificación de la información (con propiedades probabilísticas) 107 y la envía 204 a la entidad intermedia 110.
o La entidad intermedia 110 realiza 201 una primera codificación de la información (con propiedades deterministas) 104 a partir de la información codificada 107, y envía ambas codificaciones 201 , 204 a la entidad receptora 102.
o La entidad receptora 102 genera 202 las pruebas de contenido 105 a partir de la información codificada 104 y las envía 202 a la entidad emisora 101.
o La entidad emisora 101 verifica 203 las pruebas de contenido 105 para comprobar el correcto registro de la información codificada 104, 107.
Breve exposición de la invención
La presente invención describe un método de verificación que permite comprobar el correcto registro de una información (p. ej., que la información que recibe un medio de almacenamiento es la misma que se le ha proporcionado).
Este método de verificación es aplicable en procesos en los que el emisor envía cierta información al receptor y se quiere comprobar que la información recibida en el receptor es la misma, especialmente cuando se quiere preservar la privacidad del emisor.
El método descrito en esta invención se caracteriza porque la verificación del correcto registro de una información se realiza preservando la privacidad del emisor, basándose en el cálculo de un código de retorno en la entidad receptora correspondiente al contenido de la información registrada sin necesidad de descodificar esta información, y porque el conocimiento previo de este código de retorno por parte del emisor de la información permite su comprobación. En una implementación básica, el método comprende las siguientes etapas:
a) Codificado de la información original por parte de uno o varios emisores en una entidad emisora, y envío de la información codificada a una entidad receptora;
b) Cálculo por parte de la entidad receptora de una prueba de contenido de la información codificada recibida, y envío de dicha prueba a la entidad emisora;
c) Verificación por parte de los emisores de que la prueba de contenido recibida se corresponde con los contenidos originales codificados en la entidad emisora;
En una implementación preferente, el método utiliza un algoritmo criptográfico asimétrico con propiedades deterministas. En una implementación específica con EIGamal, se considera prefijar el factor aleatorio del codificado para codificar de forma determinista. Una vez se recibe esta información codificada en la entidad receptora, se calculan una o varias pruebas de contenido a partir de la información codificada de forma determinista usando una función criptográfica unidireccional, como una función de Hash o una HMAC.
En el caso en que el mensaje codificado esté formado por un conjunto de codificaciones individuales, se considera la generación de las pruebas de contenido a partir de cada una de las diferentes codificaciones o de una prueba de contenido a partir del conjunto de las mismas.
También se considera la posibilidad de la realización de una segunda codificación de la información. En una implementación preferente, se relaciona el contenido de los diferentes codificados de la información mediante una prueba de similitud, que puede ser una prueba de conocimiento nulo que demuestre que uno de los dos codificados es el re-codificado o el descodificado parcial del otro. En una implementación específica con EIGamal, se considera el uso del Protocolo de Identificación de Schnorr.En una implementación preferente la prueba de similitud se calcula a partir de dos conjuntos de mensajes codificados, de modo que se demuestra que los mensajes codificados de un grupo corresponden al re-codificado de los mensajes del otro grupo, o que los mensajes codificados de un grupo corresponden al descodificado parcial de los mensajes del otro grupo. En este caso se considera el uso de algoritmos de codificado con propiedades homomórficas, tales como EIGamal, Paillier, o algoritmos basados en curvas elípticas.
En una implementación no preferente se generan más de dos codificados distintos de la información. En este caso se contempla la generación de pruebas de similitud que relacionen todos los codificados.
En una implementación alternativa en la que el método utiliza un algoritmo criptográfico asimétrico con propiedades probabilísticas, la/s prueba/s de contenido se calculan a partir de este codificado usando una función criptográfica unidireccional, como una función de Hash o una HMAC. En una implementación específica de este método se considera la realización del descodificado parcial en la entidad receptora de la información codificada sin revelar el contenido, para calcular sobre esta información parcialmente descodificada la/s prueba/s de contenido.
En una implementación práctica de este método se contempla su utilización en entornos de voto electrónico para la verificación del correcto registro de las opciones de voto codificadas enviadas por los votantes al servidor de voto. Descripción detallada de la invención
La presente invención describe un método de verificación del correcto registro de una información. Este método de verificación es aplicable en procesos de registro de información donde se debe preservar la privacidad del emisor. Este método es aplicable a entornos de voto electrónico, para facilitar a los votantes la verificación del correcto registro de su voto.
El método de verificación del correcto registro de una información descrito en la presente invención permite al receptor de una información codificada, enviar al emisor una prueba del contenido codificado en dicha información sin necesidad de que el receptor deba descodificarla. De este modo el emisor puede comprobar que la información codificada recibida por el receptor contiene la misma información original que ha sido codificada por este emisor sin necesidad de que el receptor la conozca. El método es independiente del envío de la información por parte del emisor al receptor, ya sea a través de una red de comunicación, un medio de almacenamiento (como un CD o DVD), etc. Además, se contempla que el canal de envío de la información codificada y de recepción de la prueba de información codificada sean distintos.
El método de verificación descrito en la presente invención comprende las siguientes etapas:
a) Codificado de la información original por parte de uno o varios emisores en una entidad emisora, y envío de la información codificada a una entidad receptora;
b) Cálculo por parte de la entidad receptora de una prueba de contenido de la información codificada recibida, y envío de dicha prueba a la entidad emisora;
c) Verificación por parte de los emisores de que la prueba de contenido recibida se corresponde con los contenidos originales codificados en la entidad emisora;
Etapa de codificado y envío de la información
La etapa de codificado consiste en la codificación por parte de un emisor (p e., votante) de una información o de los mensajes originales (p.e., votos) en una entidad de envío (p.e., un ordenador personal del emisor), con el objetivo de preservar su privacidad. En una implementacion preferente, en esta etapa se utilizan criptosistemas de clave pública. El codificado se realizará con la componente pública P del algoritmo de codificado.
De forma adicional, el algoritmo de codificado tendría propiedades homomórficas. Existen varios algoritmos del estado de la técnica que cumplen con esta propiedad, como por ejemplo EIGamal, Paillier o basados en curvas elípticas.
En el caso de que el algoritmo tenga propiedades homomórficas, se contempla también la opción preferente de que este cifrado se realice de forma determinista, de modo que el resultado de la codificación de una información específica será siempre el mismo para un emisor concreto. La codificación determinista de la misma información por parte de distintos emisores sería preferentemente distinta. En el caso de escoger el algoritmo de codificado EIGamal, se considera prefijar el exponente aleatorio del codificado para conseguir esta propiedad determinista. Se contempla utilizar parámetros únicos para cada emisor e información codificada con el fin de que esta información sea solo determinista para la combinación emisor e información. En una implementación preferente, cada emisor dispondrá de un identificador único y el identificador de la información original a codificar se obtiene al aplicar una función de hash sobre dicha información. De este modo, el exponente aleatorio será una combinación del identificador único del emisor y el hash de la información original (p.e., una concatenación de ambos o un hash de dicha concatenación).
También se contempla una implementación alternativa en la que la codificación determinista la realiza una entidad intermedia, distinta del emisor, sobre el cifrado del mensaje que ha realizado el emisor. De este modo, el emisor envía la información codificada de forma probabilística a la entidad intermedia y ésta genera un cifrado determinista de dicha información. Este cifrado determinista puede realizarse sobre el conjunto global del mensaje codificado por el emisor o sólo aplicarse sobre el factor de cifrado utilizado por el emisor para codificar el mensaje o solo una parte. Un ejemplo del primer caso sería una codificación (p.e., un cifrado o exponenciación) del mensaje codificado. Un ejemplo del segundo caso sería una re-codificación del mensaje (p.e., un re- cifrado de un algoritmo con propiedades homomórficas utilizando la misma clave pública con la que el emisor codificó la información). En una implementación específica se considera el uso del criptosistema EIGamal para el cifrado o re- cifrado de la información codificada por el emisor.
En una tercera implementación alternativa, la codificación determinista se realiza de forma conjunta en el emisor y una entidad intermedia, y el resultado de esta doble codificación determinista es facilitado a la entidad receptora.
El envío se realiza por parte de la entidad emisora a la entidad receptora mediante un canal físico o lógico. En una implementación preferente, por canal físico se utilizaría el correo postal o FAX. Para ello, la información codificada se registraría en formato papel o equivalente. En el caso de canal lógico, en una implementación preferente se utilizaría una red de comunicación tal como Internet o telefonía. En este caso, la información codificada se representaría de forma lógica tal como binaria o electrónica.
También se contempla la posibilidad de utilizar modelos híbridos de envío lógico/físico. En estos casos, la información codificada se guardaría de forma lógica en un dispositivo físico, tal como un CD-ROM o cinta magnética o dispositivo removible de almacenamiento. Esta información se enviaría de forma física a la entidad receptora, utilizando uno de los canales mencionados anteriormente o simplemente a mano.
La codificación del mensaje puede realizarse sobre la totalidad del mensaje original o mediante la codificación individual de partes del mensaje. En el segundo caso, las distintas partes codificadas que forman el mensaje codificado pueden enviarse de forma combinada o de forma independiente. En una ¡mplementación preferente, el mensaje se divide y codifica en partes que combinadas (p.e., concatenadas) o operadas (p.e., multiplicadas aritméticamente) permitan obtener la totalidad del mensaje original codificado. Opcionalmente, estas partes codificadas del mensaje podrían facilitar información parcial del mensaje global si se descodifican individualmente. En una ¡mplementación práctica de esta propuesta el mensaje se codifica en partes que descodificadas individualmente facilitan información parcial significativa del mensaje global (p.e., cada parte podría contener un selección del total de las selecciones que ha realizado un votante de un voto). Opcionalmente, el mensaje podría también contener adicionalmente partes añadidas con información neutra que no modificaría el contenido del mensaje original, Esta técnica se utilizaría para evitar que se pueda romper la privacidad del emisor a partir del número de partes que forman un mensaje codificado: si hay un solo emisor que ha enviado un mensaje con un número concreto de partes codificadas, su identidad se podría descubrir al encontrar cuál de los mensajes descodificados requiere ese mismo número de opciones para su codificación. Tomando como referencia un entorno de voto electrónico, un ejemplo sería encontrar un voto que tuviera un número de selecciones que que ningún otro votante haya realizado. En ese caso, todos los votos se codificarían en tantas partes como el número de selecciones máximas permitidas, y las partes que correspondan a selecciones no realizadas se representarían como selecciones vacías o nulas. En una implementación preferente, el contenido de la información a codificar se procesaría previamente para convertirla a un formato numérico susceptible de ser compactado mediante técnicas aritméticas conocidas en el estado de la técnica, como sería el producto o la suma. Esta conversión podría hacerse a nivel del global de la información o por componentes individuales. Tomando el entorno del voto electrónico como referencia, un voto podría convertirse en un conjunto o vector de números, cada cual representado de forma única el valor de cada una de las selecciones. Esta conversión podría no ser necesaria si la información original ya estuviera en formato numérico o pudiera descomponerse en este formato. En una implementación preferente, cada componente del mensaje se representaría por un número primo, de forma que el mensaje podría compactarse mediante el producto de los componentes y descompactarse mediante una operación de factorización. En este caso, las selecciones nulas se representarían mediante el valor neutro (i.e., 1). Este método es susceptible de implementarse utilizando operaciones aritméticas modulares para la compactación del mensaje cifrado o de sus partes cifradas.
.En una implementación práctica, el mensaje se convertiría en un conjunto de números primos, cada uno representando a una información del mensaje, tal como una selección, que se codificarían mediante un algoritmo con propiedades homomórfícas multiplicativas (p.e., EIGamal). De este modo, se podrían verificar individualmente los contenidos de cada parte del mensaje codificado y después de verificarlos compactar el mensaje mediante la operación homomófica de todas a algunas de sus partes codificadas. El mensaje original se podrá descompactar de nuevo mediante la factorización en números primos del valor obtenido después de ser descodificado.
Generación de una prueba de contenido
En esta etapa la entidad receptora genera una prueba de contenido de los mensajes codificados recibidos, y envía dicha prueba a la entidad emisora. En el caso de que el mensaje codificado esté formado por un conjunto de partes del mensaje codificadas, la entidad receptora podría enviar una prueba de contenido individual de cada una de las partes. En una implementación preferente se usa una función unidireccional para calcular el código de retorno a partir del mensaje codificado, como podría ser una función de hash: Código Retorno: CR(m)=H(E(m)), donde E(m) es el codificado del dato m.
En otra implementación preferente, la entidad receptora dispone de una clave secreta S para generar la prueba de contenido mediante una función MAC, por ejemplo con una función HMAC:
Código Retorno: CR(m)=HMAC(E(m), S), donde E(m) es el codificado de los datos.
En el caso de que el mensaje codificado esté formado por un conjunto de codificaciones individuales, en una implementación preferente se pueden generar tantas pruebas de contenido como codificaciones distintas. En este caso, estas pruebas podrían operarse de forma que se obtenga una única prueba de contenido, por ejemplo mediante una operación XOR:
CR(m 2 )=HMAC(E(m 2 ), S)
CR(m 3 )=HMAC(E(m 3 ), S)
CR(m n )=HMAC(E(m n ), S)
CR= CRfrrii) φ CR(m 2 ) Φ CR(m 3 ) φζ... φ CR(m n ),
donde n es el número de mensajes codificados.
Las pruebas de contenido también se pueden calcular usando el mensaje codificado resultado de la operación de varios mensajes codificados: E(M)= Efirti) Φ E(m 2 ) Φ... Φ E(m n )
CR(M)=HMAC(E(M), S). En una implementación alternativa en la que se ha codificado la información usando un algoritmo probabilístico en la etapa a), se considera la descodificación parcial de la información por parte de la entidad receptora con el fin de eliminar el factor aleatorio de la codificación, sin revelar por ello el contenido de la información codificada. En esta implementación, las pruebas de contenido se realizan a partir de la información parcialmente descodificada.
Verificación de la prueba de contenido
En esta etapa el emisor verifica que la prueba de contenido se ha obtenido a partir de la información original codificada.
En una implementación preferente los emisores de los mensajes codificados poseerán previamente una lista con los valores válidos de las pruebas de contenido para cada valor (o subconjunto de valores válidos) posibles del mensaje original.
Esta lista se puede haber calculado previamente antes de las etapas de codificado, a partir del conocimiento de los posibles mensajes a enviar. En una implementación preferente, estos valores se calculan previamente a partir de la clave S de la entidad de retorno conjuntamente con el codificado determinista por parte del emisor específico de cada posible valor válido del mensaje.
En el caso de que se pueda enviar más de un mensaje codificado y que solo se genere un único código de retorno, se podrán especificar también en esta etapa previa los códigos de retorno correspondientes a determinados conjuntos de mensajes, de forma que en la etapa de verificación se comprueba un único código de retorno para varios mensajes codificados. Etapas adicionales
La invención contempla la implementación de tres etapas adicionales a las anteriores de generación y envío de una segunda codificación del mensaje, de generación y envío de una prueba de similitud y de verificación de la prueba de similitud.
Etapa de segunda codificación y envío de una información
Esta etapa se puede realizar antes o después de la etapa de codificado y envío a).
En la etapa de segundo codificado, la información original codificada en el paso a) también es codificada por la misma entidad emisora y enviada a la misma entidad receptora. El método de codificación utilizado en esta etapa puede ser el mismo que en la etapa a) de codificado de la información.
En una implementación preferente se utilizará para codificar la información el mismo criptosistema de clave pública, realizando el cifrado con la componente pública P del algoritmo de cifrado. El criptosistema y la clave pública utilizados para cifrar pueden ser los mismos que en la etapa a) de codificado de la información o pueden ser distintos.
En otra implementación preferente este segundo codificado de la información se realiza con un algoritmo de codificado con propiedades probabilísticas y homomórficas. De este modo, no será posible en ningún caso correlacionar la codificación resultante con el mensaje original cifrado. En el caso de escoger el algoritmo de codificado EIGamal, el exponente se escogerá siempre de forma aleatoria.
El envío del segundo codificado del mensaje se puede realizar del mismo modo que en la etapa a) anterior. De forma preferente, se utilizaría el mismo canal de envío que en la etapa a) aunque también podrían enviarse ambas codificaciones por canales distintos.
Del mismo modo que en la etapa a), la codificación del mensaje puede realizarse sobre la totalidad o en partes del mensaje.
Etapa de generación y envío de una prueba de similitud
En esta etapa la entidad emisora realiza una prueba de similitud entre la información codificada y la segunda codificación de la información, y después envía dicha prueba a la entidad emisora. Esta etapa se realiza después de las dos etapas de codificación de la información. El envío de la prueba de similitud puede hacerse de forma individual o junto con el envío de cualquiera de las dos codificaciones. La forma de envío puede ser cualquiera de las vistas anteriormente para la información codificada.
En una implementación preferente esta prueba de similitud se obtiene a partir de prueba de conocimiento nulo de igualdad de contenido entre textos codificados. En un ejemplo de implementación, se utilizarían en los dos codificados de la información algoritmos con propiedades homomórficas que permiten realizar una operación de re-codificado. De este modo, la prueba de conocimiento nulo puede ser una prueba de re-codificado o de descodificado parcial. En el caso de utilizar el sistema de codificado EIGamal en las dos etapas de codificado, la prueba de conocimiento nulo puede consistir en la implementación del Protocolo de Identificación de Schnorr. La prueba de conocimiento nulo podría ser interactiva o no.
En el caso de utilizar el sistema de codificado EIGamal, tenemos los siguientes componentes: g generador del subgrupo G q de Z p * q es un primo grande, y p=2*q+1 clave privada: x x número aleatorio en Z q clave pública: (h, g) donde h=g x mod p mensaje: m
El codificado se realiza: c = (m.h r , donde r es un número aleatorio en Z q .
Para descifrar calculamos m = c * ( (f) ~x . Si se ha utilizado un algoritmo de codificado determinista en la etapa a) de codificado:
Ci = (m.h v , g v ) donde v es un número en Z q calculado a partir de unos valores fijos (p.e., unos identificadores únicos del emisor y del mensaje).
En el caso de que el algoritmo de la segunda codificación sea probabilístico: c 2 = (m.h r , cf) donde r es un número aleatorio en Z q .
Siendo r=v+r', se puede considerar c 2 como el re-codificado de ci con el factor r' y calcular la prueba basada en el Protocolo de Identificación de Schnorr del siguiente modo:
- Calcular c 2 /c 1 = (Lh" ' , ).
Definiendo g' = h y h' = h r , se puede probar en conocimiento nulo que se conoce el factor de recodificado r':
Seleccionar un número aleatorio e, 1 < e < q-1, y calcular w - g e .
Calcular d = H(w\h'\g'\h\g), donde H es una función de hash.
- Finalmente, calcular s = r'.d+e.
La prueba de conocimiento nulo de que los dos codificados tienen el mismo contenido consiste en los parámetros [w, s].
En el caso de efectuar esta prueba sobre un conjunto de mensajes, se considera el uso de algoritmos con propiedades homomórficas, en los que la operación de los mensajes codificados con una operación Φ da como resultado el codificado de los mensajes operados mediante la operación Θ. De este modo se puede obtener un mensaje codificado resultado de la operación de todos los otros:
Siendo E P (m) el codificado de un mensaje con una clave pública P, el mensaje codificado resultante de operar n mensajes es
E P (M) = Epfrrii) Φ E P (m 2 ) Φ... Φ E P (m n ), donde M = m 1 Θ m 2 Θ... Θ m n El mensaje codificado resultante después de operar los mensajes codificados en la etapa a) es
EIP(M) = Eipfmi) Φ Eip(m 2 ) Φ... Φ Ei P (m n ), donde M = m-, Θ m 2 Θ... Θ m n
Mientras que el mensaje codificado resultante después de operar los mensajes codificados en la segunda etapa de codificación es
E2p(M)= Φ E 2P (m 2 ) Φ... Φ E 2 p(m n ), donde M= m-¡ Θ m 2 Θ... Θ m n
La prueba de conocimiento nulo de que los dos codificados del conjunto de mensajes tienen el mismo contenido se puede resumir en una prueba de que los dos mensajes codificados resultantes tienen el mismo contenido. Ésta puede ser una prueba de re-codificado o de descodificado parcial. En el caso de utilizar el sistema de codificado EIGamal en las dos etapas de codificado, la prueba de conocimiento nulo puede consistir en la implementación del Protocolo de Identificación de Schnorr.
Si se ha utilizado un algoritmo de codificado determinista en la etapa a) de codificado:
Ei(m¡) = (m¡.h vl , g vi ) donde v¡ es un número en Z q acordado antes del proceso de codificado.
El mensaje codificado resultante después de operar un conjunto de n mensajes codificados en la etapa a) es d = (M.h v , g v ) = {m,.tí g v1 ) * (m 2 .h v2 , g v2 ) *... * (m n .h vn , g vn ), donde M = mi * m 2 *... * m n y V = v-i+v 2 +... +v n . En el caso en que el algoritmo de la segunda codificación sea probabilístico:
E 2 (m¡) = (m¡.h n , g rl ) donde A " , es un número aleatorio en Z q . El mensaje codificado resultante después de operar el mismo conjunto de n mensajes codificados es
C 2 = (M.h R , g R ) = (mi.h r1 , tf 1 ) * (m 2 .h r2 , 2 ) * ... * (m n .h rn , g™), donde = * m 2 * ... * m n y R=r 1 +r 2 +... +r n .
Siendo r¡ = v¡+r¡ se puede considerar C como el re-codificado de C 7 con el factor de re-codificado R' = ri'+r 2 '+... +r n ', y calcular la prueba basada en el Protocolo de Identificación de Schnorr del siguiente modo:
- Calcular C 2 / d = (1.h R g R ).
Definiendo g' = h y h' = h R , se puede probar en conocimiento nulo que se conoce el factor de re-codificado R'\
Seleccionar un número aleatorio e, 1≤e≤q-1, y calcular w = g e .
Calcular d = /-/(w|/7'|g'|/7|gj, donde H es una función de hash.
- Finalmente, calcular s = R'.d+e.
La prueba de conocimiento nulo de que los dos codificados tienen el mismo contenido consiste en los parámetros [w, s].
Verificación de ¡a prueba
En esta etapa la entidad receptora verifica que las codificaciones recibidas han sido realizadas sobre la misma información, a partir de la prueba de similitud recibida.
En el caso de que esta prueba se haya obtenido a partir de una prueba de conocimiento nulo, esta verificación se realiza verificando que esta prueba conocimiento nulo se ha generado a partir de las codificaciones recibidas.
En una implementación preferente, los dos codificados se han realizado con algoritmos que tienen propiedades homomórficas utilizando la misma clave pública o el mismo factor de cifrado, y la prueba de similitud se ha generado a partir de una prueba de conocimiento nulo de re-codificado o de descodificado parcial.
Si se ha utilizado un algoritmo de codificado determinista en la etapa a) de codificado: Ci - (m.h v , g v ) donde v es un número en Z q determinado antes del proceso de codificado.
Y el algoritmo del segundo codificado es probabilístico:
c 2 = (m.h r , < ) donde res un número aleatorio en Z q .
Siendo r = v+r la verificación de la prueba efectuada que demuestra el conocimiento del factor de re-codificado de Ci con el factor r' para obtener c 2 se basa en la verificación de [w, s] si la prueba se ha realizado usando el Protocolo de Identificación de Schnorr:
Calcular C 2 / CÍ = (1. f, tf).
- Definir g' = h y h - H .
Calcular d = H(w\h'\g'\h\g), donde H es una función de hash.
Verificar que g = w.h d .
En el caso que la prueba de conocimiento nulo se haya efectuado sobre un conjunto de mensajes codificados con algoritmos con propiedades homomórficas, en los que la operación de los mensajes codificados con una operación Φ da como resultado el codificado de los mensajes operados mediante la operación Θ, la verificación se realiza utilizando el resultado de la operación de los mensajes codificados en la etapa a) y el resultado de la operación de los mensajes codificados en la etapa c).
En el caso de utilizar el sistema de codificado EIGamal en las dos etapas de codificado, la prueba de conocimiento nulo puede consistir en la implementación del Protocolo de Identificación de Schnorr.
Si se ha utilizado un algoritmo de codificado determinista en la etapa a) de codificado:
Ei(m¡) = (mj.h vl , g vi ) donde v¡ es un número en Z q acordado antes del proceso de codificado.
El mensaje codificado resultante después de operar un conjunto de n mensajes codificados en la primera etapa es d = (M.h v , g v ) = ( i. v1 , g v1 ) * (m 2 .h v2 , g v2 ) * ... * (m n .h vn , g vn ), donde M = mi * m 2 * ... * m n y V=vi+v 2 + ... +v n . En el caso en que el algoritmo de la etapa de segundo codificado es probabilístico:
E 2 (m¡) = (mj.h", g") donde r,es un número aleatorio en Z q .
El mensaje codificado resultante después de operar el mismo conjunto de n mensajes codificados en la segunda etapa es
C 2 = (M.h R , g R ) = (m^H 1 , tf 1 ) * (m^lY 2 , 2 ) * ... *(m n .h rn , tf n ), donde M = m 1 * m 2 * ... * m n y R=ri+r 2 +... +r n .
Siendo r¡ = v¡+r¡', se puede considerar C 2 como el re-codificado de C 7 con el factor de re-codificado R'= ri'+r 2 '+... +r n '. La verificación se efectúa sobre los parámetros [w, s] si la prueba se ha realizado usando el Protocolo de Identificación de Schnorr:
Calcular C 2 / C 7 = (1.h R
Definir g' = h y h' = h R' .
Seleccionar un número aleatorio e, 1≤e≤ q-1, y calcular w = g e .
Calcular d = H(w\h'\g'\h\g), donde H es una función de hash.
- Verificar que g' s = w.h d .
Referencias
[Ch01] Chaum, D. (2001). "Surevote technical overview (slides)". http://www. vote, caltech. eduA/voteO 1/pdfs/surevote.pdf
[Ma02] Malkhi, D; Margo, O; "Pavlov, E. E-voting without 'cryptography'". Conference Information: 6th International
Conferene on Financial Cryptography, 2002, SOUTHAMPTON BERMUDA. FINANCIAL CRYPTOGRAPHY
[Be06] Josh Benaloh. "Simple verifiable elections". Proceedings of the USENIX/Accurate Electronic Voting Technology (2006). Vancouver, B.C., Canadá.
[Ad08] Ben Adida. "Helios: web-based open-audit voting". Proceedings of the 17th conference on Security symposium, USENIX. Pages 335-348. Year of Publication: 2008
[Sa08] Sandler, D., Derr, K., and Wallach, D. S. 2008. "VoteBox: a tamper-evident, verifiable electronic voting system". In
Proceedings of the 17th Conference on Security Symposium, USENIX Association. Pp. 349-364.