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$
    – sherlock
    Commented Jan 23, 2015 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
    Commented Jul 27, 2015 at 14:47

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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