How to prove element equality in G1 using Groth-Sahai proofs

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

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.