I am working my way through this paper. I am trying to figure out the OR zero knowledge proof in figure 2. The prover is verifying that she has correctly voted, and that her input satisfies $$\log_gx=\log_h{(y/m_0)} \wedge \log_gx=\log_h{(y/m_1)}$$ The authors' protocol for this makes sense except for one thing. After the prover receives the challenge $c$, she sets $d_2 \leftarrow c - d_1$ if her vote is 1, or $d_1 \leftarrow c - d_1$ if her vote is -1. Because $c \in_R \mathbb{Z}$ and the previously set $d$ is also $\in_R \mathbb{Z}$, the new $d$ could be negative.

However, in the final step, the verifier needs to compute two values to the power of each $d$. This means the prover can't simply send $d \mod p$, and must send $d$ even if it is negative. But the other $d$ value will never be negative.

Doesn't this mean that verifier can learn the prover's vote? If $d_2$ is negative then she voted 1, or if $d_1$ is negative then she voted -1.

What am I missing?


1 Answer 1


I figured it out, it's quite simple actually.

The $d$ values (and $r$ values) are all exponents and chosen from $\mathbb{Z}_q$. Thus all calculations on them directly take place in $\mathbb{Z}_q$. Applying mod $q$ (not mod $p$) to all of my calculations on $d$ and $r$ fixed any problems with calculations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.