Groth-Sahai framework enables us to commit to QE, MSME, PP equations. Now, is the equation below committable in GS framework?

A bilinear map $e: G_1 \times G_2 \rightarrow G_T$. $g_1 \in G_1$ and $g_2 \in G_2$ are the generators of the corresponding groups. $K \in G_1$ and $\tau \in G_T$ are constants. $x,y \in Z_p$ are variables to be committed. The equation is: $$e(K/g_1^x, g_2^y) = \tau$$I want to prove the knowledge of $x$ and $y$ without revealing the values. Note that groups have been written in multiplicative notations.


Firstly, note that Groth-Sahai framework doesn't provide proofs of knowledge of exponents, because all commitments to exponents in it are computationally irreversible. It only provides proofs that show that such exponents exist. That is, a prover can claim to know $x$ but actually only know $\mathcal{A}^x$ for some $\mathcal{A}$, and still be able to produce a valid proof.

Secondly, the equation can be rewritten as follows:


Since $e(K,g_2)$ and $e(g_1,g_2)$ are constants, this equation is linear in terms of $y$ and $-xy$. There is an article describing proof of knowledge systems for such equations:

Camenisch, J., & Stadler, M. Proof Systems for General Statements about Discrete Logarithms.

Alternatively, if it's necessary to use Groth-Sahai framework, the equation can be rewritten as follows:

$$\mathcal{X}=g_1^x\wedge\mathcal{Y}=g_2^y\wedge e(K\mathcal{X}^{-1},\mathcal{Y})=\tau$$

The first two equations are MSME, and the last one is PP. However, there are now three equations instead of one, so the proof is larger than necessary. Also, at least in the DLIN instantiation, a prover can produce a valid proof while only knowing $\mathcal{X}$ and $\mathcal{Y}$ but not $x$ and $y$. I don't know whether it is possible in SXDH instantiation, but anyway, Groth-Sahai proofs are not proofs of knowledge of exponents.

It may also be possible to use Camenisch-Stadler proof system to prove the knowledge of exponents that correspond to commitments in Groth-Sahai proof system. This way, it may be possible to prove the knowledge of exponents as well as the validity of quadratic equations over them.

| improve this answer | |
  • $\begingroup$ Let me go through CS proof system $\endgroup$ – Holmes.Sherlock Sep 22 '14 at 4:39

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.