Verification of NIZK proof with algebraic MACs The paper Algebraic MACs and Keyed-Verification Anonymous Credentials, includes a way to instantiate a NIZK proof with algebraic MAC. This is given in Appendix E where this NIZK is a part of the Show protocol. I understand the proof generation given in E.1, where the protocol outputs proof P. The hash $c$ in P is given as:
$c = H(param||\{C_{m_i}\}_{i=1}^{n}||C_{u^\prime}||\{\tilde{C}_{m_i}\}_{i=1}^{n}||\tilde{V})$
But I do not understand the Proof Verification part given in E.2. Particularly, I do not understand the construction of $c^\prime$ which is given as:
$c = H(param||\{C_{m_i}\}_{i=1}^{n}||C_{u^\prime}||\{C_{m_i}g^{s_{m_i}}h^{s_{z_i}}\}_{i=1}^{n}||VX^{s_{z_1}}...X^{s_{z_n}}g^{s_r})$
The verifier checks whether $c = c^\prime$. But I do not see how they can be computed to be equal even if everything is right. The first 3 parts of the construction of $c^\prime$ have the same elements as $c$, so for them to be equal, the particular equations below should be satisfied.
$\{\tilde{C}_{m_i}\}_{i=1}^{n} = \{C_{m_i}g^{s_{m_i}}h^{s_{z_i}}\}_{i=1}^{n}$, and
$\tilde{V} = VX^{s_{z_1}}...X^{s_{z_n}}g^{s_r}$
But upon expanding the left-hand-side of either of the equations, they do not equate to their corresponding right-hand-sides. Where am I going wrong here?
Yes, you are correct that this is an error. I discovered the same thing myself a couple of months ago and emailed the authors. Greg Zaverucha responded and agreed with me. More specifically, this was what he agreed with:
&quot;
Hi,
I've been studying https://eprint.iacr.org/2013/516.pdf and in Appendix E.2 part 3(b) in the verification algorithm, there appears to be an error, wanted to check it with you:
In order for the verifier to reconstruct the challenge hash $c$, you concatenate items in the preimage, the 4th item (or set of items) is given as:
$$C_{m_{i}} . g^{s_{m_i}} . h^ {s_{z_i}} \quad \forall i$$
but this does not appear to be the correct way to construct the items $C_{m_i}$~ that were in the prover's challenge hash preimage. As far as I know the correct way to reconstruct the $C_{m_i}$~ terms would be:
$$(C_{m_i})^c . u^{s_{m_i}} . h^{s_{z_i}} \quad \forall i$$
(where $c$ lower case is of course the challenge hash provided by the prover).
&quot;
I figured out what it should be based on analogy with sigma protocols in general, but it's been a little while; hopefully you can see that this version makes sense.
Additional edit: today I have been studying this again, and realised that you were also stating that the final element of the hash preimage construction also does not validate. Looking at it carefully I can see there is a very similar issue: $V$ should be replaced with $V^c$.