In context of Groth-Sahai NIZK proof system, I have a couple of doubts on Hiding and Binding keys.

enter image description here

  1. In case of hiding keys (highlighted in red), how is it ensured that $\tau(A) \subseteq \langle u_1,...u_m \rangle$?
  2. In case of binding keys (highlighted in green), how come $\tau \circ p$ be an identity map on $A$? Shouldn't it be an identity map on $B$?
  • $\begingroup$ I understand, but otherwise I had to Latex so much text. Apart from that, the title and tag fields are searchable. $\endgroup$ – Holmes.Sherlock Jan 23 '15 at 19:30
  • 2
    $\begingroup$ I personally find "Groth-Sahai proofs revisited" has a clearer presentation of what's going on, and it fixes a few small mistakes/typos. $\endgroup$ – user2552 Jul 27 '15 at 14:47

I am still not very familiar with these kinds of proofs, but from what I understood:

1) This inclusion is actually a condition which defines in itself what a hiding key is. That is to say that this paragraph does not say that the inclusion is ensured, but that we should make sure that it is, if we want a perfectly hiding key. However, you may find sets of $u_i$'s that verify this property in the three different instantiations. If you use the short version of the paper where they do not appear, look here instead.

In the second (SXDH) instantiation for instance, to commit in $G_1$, you get $u_1=(\mathcal{P}_1,\alpha\mathcal{P}_1)$ and either $u_2=tu_1$ for a binding key, or $u_2=tu_1-(\mathcal{O},\mathcal{P}_1)$ for a hiding key ($t$ and $\alpha$ are chosen at random). In this last case, $\iota(G_1)\subset \langle u_1,u_2\rangle$ because for $g\in G_1$, you can write $g=\mathcal{P}_1^n$ and then you have $\iota(g)=(\mathcal{O},\mathcal{P}_1^n)=(tu_1-u_2)^n\in\langle u_1,u_2\rangle$. Note that you don't have this with the binding parameters.

2) You are right, they probably meant to write $p\circ\iota$ instead.

| improve this answer | |

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.