# 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:

" 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). "

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$$.