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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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