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

[1]​[2]​ Supongamos que:[1]​ Establecemos el siguiente protocolo:[1]​ 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]​ 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

Por tanto los votos cifrados tienen la forma

{\displaystyle (g^{x_{i}},K^{x_{i}}{\dot {g}}^{v_{i}})}

con K perteneciente a la clave pública y x_i aleatorio.

[2]​ Por tanto dado un voto cifrado con ElGamal

( x , y ) = (

{\displaystyle (x,y)=(g^{x_{i}},m\cdot h^{x_{i}})}

se tiene que poder demostrar que m puede ser

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]​

{\displaystyle \log _{g}x=\log _{h}(y/m_{0})\lor \log _{g}x=\log _{h}(y/m_{1})}