In the BeleniosRF e-voting scheme, Groth-Sahai proofs with the "Instantiation based on the SXDH assumption" are used (see https://eprint.iacr.org/2007/155, version 20160411:065033, page 24).

In the BeleniosRF paper on page 8, Figure 2, a Groth-Sahai proof is used to prove $g_1^\overline{r} = c_1$ with $g_1$ being the generator of the first group of a pairing. Using the notation of the Groth-Sahai paper, an equality of two elements in $A_1 = G_1$ must be proven. How can this be done?

This is most likely a special case of one of the described equation types

  1. pairing product equation
  2. multi-scalar equation in $G_1$
  3. multi-scalar equation in $G_2$
  4. quadratic equation

but I'm not seeing how it fits into one of those.


1 Answer 1


First of all, the idea of proving element equality does not make much sense, since that would reveal the secret element. $prove(X == T)$ with secret $X \in G_1$ and public constant $T \in G_1$ reveals the value of $X$. What I was looking for instead is $prove(g_1^x == T)$ with public constants $g_1, T \in G_1$ and secret scalar $x$.

It tuned out that type 2. multi-scalar equation in $G_1$ was what I was looking for. Since both left hand side and right hand side of those equations are elements in $G_1$, this is exactly what I needed. The special case to use was the liniear equation:

$A^y = T_1$

with public constants $A, T_1 \in G_1$ and private scalar $y$.

Note: Here I used the multiplicative notation for the operation in $G_1$ as it is done in the BeleniosRF paper; the GS paper uses the additive notation.


Your Answer

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

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