Protocolo de Cramer-Damgard-Schoenmakers
El protocolo de Cramer-Damgard-Schoenmakers o protocolo CDS, también conocido por los nombres protocolo de testigo indistinguible o técnica k-de-n ZKP (del inglés 1-out-of-n ZKP technique) permite probar que se conoce la solución de k problemas de un conjunto de n problemas (k<n) sin revelar para cuales de los problemas se tiene la solución.[1][2]
Descripción[editar]
Supongamos que:[1]
- Existen n diferentes cuestiones
- El probador P quiere probar a un verificador V que conoce la solución de una de las cuestiones
- P no quiere que V encuentre a qué problema él conoce la solución.
Establecemos el siguiente protocolo:[1]
- Supongamos que P conoce la solución de la cuestión , entonces P elige aleatoriamente un y calcula un genuino testigo . A continuación desafíos falsos , y respuestas falsas y los usa para fabricar testigo . P envía a V.
- V aleatoriamente elige un desafío y lo envía a P.
- P calcula y calcula la respuesta real , usando , y su conocimiento . Después de esto P, envía y a V.
- V verifica que y para todas las cuestiones, cada una de sus pruebas se cumplen. Sin embargo, V no podrá distinguir la prueba real entre las pruebas falsas.
Aplicaciones[editar]
Este protocolo se usa en esquemas de voto verificables para probar que un texto cifrado es consecuencia de cifrar alguno de los elementos de un conjunto de valores diferentes.[1]
Ejemplo[editar]
Por ejemplo, el protocolo CDS se ha usado para demostrar que un voto cifrado con ElGamal es uno de dos posibles votos que se pueden realizar en un referéndum ("SÍ" o "NO") sin revelar cual es lo cual es un problema 1-de-2 ZKP.[2]
Para llegar a un problema donde aplicar el protocolo CDS codifica con al "NO" y con al "SI". Formalizando se tiene que con . Por tanto los votos cifrados tienen la forma con K perteneciente a la clave pública y x_i aleatorio.[2]
Por tanto dado un voto cifrado con ElGamal se tiene que poder demostrar que m puede ser o sin revelar cual es. El objetivo a demostrar es probar la siguiente sentencia OR demostrable por el protocolo CDS (al que previamente se le ha convertido en un protocolo no interactivo usando la heurística de Fiat-Shamir):[2]
- Demostración: Partiendo de tenemos:
- Despejando en tenemos
- Despejando en tenemos
- Uniendo las dos igualdades tenemos
Referencias[editar]
- ↑ a b c d Verifiable Voting Systems Archivado el 15 de octubre de 2013 en Wayback Machine.. Thea Peacock, Peter Y. A. Ryan, Steve Schneider y Zhe Xia. University of Luxembourgy University of Surrey
- ↑ a b c d Every Vote Counts: Ensuring Integrity in Large-Scale DRE-based Electronic Voting. Feng Hao, Matthew Nicolas Kreege