Non-interactive proof that an element is in a subgroup

Question

I am just reading the DAA paper (http://eprint.iacr.org/2004/205.pdf, Appendix A). A party $\mathcal{I}$ generates two group elements $g' \in \mathrm{QR}_n$ and $h = g'^r \bmod n$ with $r \in_R \left| \mathrm{QR}_n \right|$. Now $\mathcal{I}$ wants to prove in zero-knowledge that $h$ has been created correctly, i.e. that $h \in \langle g' \rangle$.

In the paper the authors use binary challenges with a non-interactive proof of knowledge. I don't get why? This is quite inefficient so I guess that there is a reason for this. Why not just proving $h = g^r \bmod n$ where $r$ is the secret and using one "big" challenge instead of using only 0/1 as the challenge and repeat the protocol?

edited

I have made some further research. Can someone please tell me, if I am right or wrong. The prover P wants to prove to a verifier V that h = g'^r, i.e. $ZKP\ [(r): g'^r]$. $g', h \in G$. The protocol is something like

         P                                V
--------------------------------------------------
y = g'^k mod n           y
                 --------------->  choose challenge c
                         c
                 <---------------
s = k + c*r mod |G|
                         s
                 --------------->  check if g^s mod n = y*h^c mod n

To prove the zero-knowledge property, we have to define a simulator S which communicates with V (instead of P). If it is an honest verifier ZKP, we can define S as $S(y, c, s) = (\frac{g'^s}{h^c}, c, s)$ with $s \in_R \{0, \dots, |G|-1\}$, right? There are no differences between real transcripts (between P and V) and faked transcripts (between V and S) => so the protocol is zero-knowledge, correct??

Now, we have an dishonest verifier, which doesn't choose the challenge randomly. To solve this problem, we use a non-interactive proof, where the challenge is created by a random oracle (for practical use we use "a hash function H"). Instead of transferring $y$ to V (and getting a challenge back) the prover sets $c = H(y)$. We can take the same simulator as in the "interactive-case", or???

What I still don't get is why the authors in the paper separate the 160-bit Hash into 160 pieces and take each bit as the challenge? Is the reason for this that maybe the prover chooses the base $g'$? In other papers they say that you can prove $ZKP\ [(w): g'^w]$ "directly" without using binary challenge, but in these cases the base $g'$ is fixed.

Answer 1

My guess would be that they have a proof that their scheme has the zero-knowledge property if the challenge comes from the set $\{0,1\}$, whereas the proof doesn't work if the challenge comes from the set $\{0,1,2,\dots,2^{160}-1\}$ -- and they don't know how to construct an alternate proof to show the latter.

If you want to understand why their proof doesn't work for larger challenges, you should start by reading through their proof for small challenges and see if each step remains valid for large challenges.

For instance, you might find there is a rewinding step that works if the challenge comes from the space $\{0,1\}$ but doesn't work if there is a large challenge space. This is a common phenomenom in rewinding-based proofs. If the challenge space is $\{0,1\}$, you can rewind the challenger and run the protocol forward, and with probability $1/2$ the resulting challenge will match what you want it to be. Thus, on average, you only need to try twice, and that's fine. In contrast, if you used a random 160-bit challenge, the probability of success on rewinding would be only $1/2^{160}$, so you'd need to try $2^{160}$ times, which is not feasible. As result, many rewinding proofs work fine if you have a 1-bit challenge but fall apart if you have a 160-bit challenge. This poses a barrier to proving the zero-knowledge property using large challenges, using this kind of proof technique. If the only way they know to prove the zero-knowledge property is using this sort of rewinding proof technique, then that'd explain why they propose a 1-bit challenge.

Answer 2

My guess is, responses $\hat x_{(g,i)}..\hat x_{(1,i)}$ ($s$ in the example) are computed modulo group order that is not available to verifiers of the statement claimed.

Challenge difference is always one ($1$) while rewinding for binary ($0$/$1$) challenges, and it is not expected to be one for "large" challenges. Dividing by a non-one (in other words, taking a root) in a group of a hidden order is equivalent to decrypting an RSA ciphertext, rendering straightforward knowledge extractor algorithm unusable (of large expected run time).

So, with binary challenges we have a proof of knowledge of numbers $x_g, x_h, x_s, x_z, x_0, x_1$ such that equations (1) and (2) hold (page 8). It follows, $g, h, S, Z, R_0, R_1$ have properties as claimed.