Protocolo de Cramer-Damgard-Schoenmakers

Supongamos que:^[1]

• Existen n diferentes cuestiones ${\displaystyle 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]

1. Supongamos que P conoce la solución ${\displaystyle d_{i}}$ de la cuestión ${\displaystyle Q_{i}}$, entonces P elige aleatoriamente un ${\displaystyle r_{i}}$ y calcula un genuino testigo ${\displaystyle t_{i}}$. A continuación desafíos falsos ${\displaystyle c_{j}}$, y respuestas falsas ${\displaystyle s_{j}}$ y los usa para fabricar testigo ${\displaystyle t_{j},j\neq i}$. P envía ${\displaystyle (t_{1},t_{2},...,t_{n})}$ a V.
2. V aleatoriamente elige un desafío ${\displaystyle c^{*}}$ y lo envía a P.
3. P calcula ${\displaystyle c_{i}=c^{*}-\sum _{j\neq i}c_{j}}$ y calcula la respuesta real ${\displaystyle s_{i}}$, usando ${\displaystyle r_{i}}$, ${\displaystyle c_{i}}$ y su conocimiento ${\displaystyle d_{i}}$. Después de esto P, envía ${\displaystyle (c_{1},c_{2},...,c_{n})}$ y ${\displaystyle (s_{1},s_{2},...,s_{n})}$ a V.
4. V verifica que ${\displaystyle 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.

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 ${\displaystyle g^{0}}$ al "NO" y con ${\displaystyle g^{1}}$ al "SI". Formalizando se tiene que ${\displaystyle m=g^{v_{i}}}$ con ${\displaystyle v_{i}=\{0,1\}}$. 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 ${\displaystyle (x,y)=(g^{x_{i}},m\cdot h^{x_{i}})}$ se tiene que poder demostrar que m puede ser ${\displaystyle m_{0}=g^{0}}$ o ${\displaystyle 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):^[2]

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

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

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