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.

Descripción

Supongamos que:

• Existen n diferentes cuestiones $Q_1,Q_2,...,Q_n$
• 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 $d_i$ de la cuestión $Q_i$, entonces P elige aleatoriamente un $r_i$ y calcula un genuino testigo $t_i$. A continuación desafíos falsos $c_j$, y respuestas falsas $s_j$ y los usa para fabricar testigo $t_j,j\ne i$. P envía $(t_1,t_2,...,t_n)$ a V.
2. V aleatoriamente elige un desafío $c^{*}$ y lo envía a P.
3. P calcula $c_i=c^{*}-\sum _{j\ne i}{c}_j$ y calcula la respuesta real $s_i$, usando $r_i$, $c_i$ y su conocimiento $d_i$. Después de esto P, envía $(c_1,c_2,...,c_n)$ y $(s_1,s_2,...,s_n)$ a V.
4. V verifica que $c^{*}=\sum _{k=1}^n{c}_k$ 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

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.

Ejemplo

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.

Para llegar a un problema donde aplicar el protocolo CDS codifica con $g^0$ al "NO" y con $g^1$ al "SI". Formalizando se tiene que $m=g^{v_i}$ con $v_i=\{0,1\}$. Por tanto los votos cifrados tienen la forma $(g^{x_i},K^{x_i}{\dot{g}}^{v_i})$ con K perteneciente a la clave pública y x_i aleatorio.

Por tanto dado un voto cifrado con ElGamal $(x,y)=(g^{x_i},m\cdot h^{x_i})$ se tiene que poder demostrar que m puede ser $m_0=g^0$ o $m_1=g^1$ 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):

${\log }_{g}x={\log }_h(y/m_0)\vee {\log }_{g}x={\log }_h(y/m_1)$

Demostración: Partiendo de $(x,y)=(g^{x_i},m\cdot h^{x_i})$ tenemos:

• Despejando $x_i$ en $x=g^{x_i}$ tenemos $x_i={\log }_{g}x$
• Despejando $x_i$ en $y=m\cdot h^{x_i}$ tenemos $x_i={\log }_h(y/m)$
• Uniendo las dos igualdades tenemos $x_i={\log }_{g}x={\log }_h(y/m)$