# Using pairings to verify an extended euclidean relation without leaking the values?

Let $P_i(x)$ be polynomials $i=1,...,n$, $s$ some value, and $g$ a generator of a group $G$ where the discrete logarithm is hard.

Assume a prover wants to convince a verifier having access to the values $g^{P_i(s)}$ that it knows polynomials $q_i(x)$ such that the following equation holds:

$q_1(s)*P_1(s)+q_2(s)*P_2(s)+\ldots+q_n(s)*P_n(s) = 1.$

The prover thus sends the verifier the values $g^{q_i(s)}$ and uses bilinear maps to verify the correctness of the answer.

Can the following equation tell me whether it has correctly computed the $q_i(s)$: $$e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$$ where $e$ is a bilinear map $G\times G\rightarrow G_1$.

So basically I want my bilinear map to verify on the exponents while hiding them. Is the second part of the equation correct? Or should it be 1, or $e(g,g)^{ord(G)}=1$?

-
There seems to be a typo or grammatical error in the question, which has me lost. "...for some secret s that the prover which is...": is there some word or sequence of words missing in the middle of this? –  D.W. Oct 19 '12 at 5:49
Also, I don't understand what information is known to which parties. Who knows $s$? Who knows $S$? Does anyone know the polynomials $P_i(x)$ and $q_i(x)$? Who knows the value of $P_i(s)$ and $q_i(s)$ (these polynomials evaluated at $s$)? And, your definition of $P_i(s)$ does not seem to have any dependence on $i$. Did you mean to use $S_i$ instead of $S$ in that equation? If so, who knows the $S_i$'s? –  D.W. Oct 19 '12 at 5:51
The exact definition of the $P_i$, $q_i$, and $s$ are not really relevant to the question. But in case you really want to know the dirty details, look at the dirty details of set intersection queries... –  bob Oct 19 '12 at 16:43

Well, assuming the equation holds, $\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ must also hold, due to the bilinearity of $e$. (Conversely, the equation only holds mod |G_1|.)

To see why, recall that the fact that the mapping $e$ is bilinear translates into $e(g^a,h^b)=e(g,h)^{a*b}$ for all elements $g$ and $h$ in $G$ and for all integers $a$ and $b$. Thus, we always have $e(g^{q_i(s)},g^{P_i(s)})=e(g,g)^{q_i(s)*P_i(s)}$ and by multiplying all these equalities together we get that $$\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) =e(g,g)^{q_1(s)*P_1(s)+\cdots+q_n(s)*P_n(s)}.$$ Now what you want to check is if $q_1(s)*P_1(s)+\cdots+q_n(s)*P_n(s)=1$: if it is true, we can replace the expression in the left-hand side of this equation in the pairing equation above by 1 and thus get $$\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$$ as stated in the beginning.

For $e(g,g)$ is a group element of $G_1$, it must hold that $e(g,g)^{|G_1|}=1$, as for any other element of $G_1$.

For the actual value of $e(g,g)$ itself, we can only say it is an element of $G_1$ (by definition of $e$). It can be the neutral element of $G_1$ in which case $e(g^a,g^b)=1$ for all $a$ and $b$ and thus does not provide you with a way to check the extended euclidean equality, since you'll basically get $1=1$ for all possible values of $q_i$ and $P_i$.

-
so $e(g,g)=1$. I am always confused whether or not $e(g,g)=e(g,g)^{ord(G)}=1$ –  curious Oct 11 '12 at 9:38
So to conclude . In all bilinear mappings from $G$ to $G_1$ where $g$ the generator of $G$ $e(g,g)=1$Right? –  curious Oct 11 '12 at 11:24
No: $e(g,g)$ is just an element of the group $G_1$ since $e$ maps pairs of elements from $G$ to elements of $G_1$. Now, if $e(g,g)=1$, that is, if $e(g,g)$ is the neutral element of $G_1$, then you can basically do nothing with the pairing $e$ using the generator $g$, since then $e(g^a,g^b)=e(g,g)^{a*b}=1^{a*b}=1$. So, to summarize, it can be that $e(g,g)$ for a specific $g$ and $e$, but this case is devoid of interest to build upon for cryptographic purposes (degenerate case). –  bob Oct 11 '12 at 11:54
So can i be sure that $e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ holds? –  curious Oct 11 '12 at 12:57
No. As I said in the answer, assuming the output of the extended euclidean algorithm is correct, $\Pi_{i=1}^n e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ must also hold. Please note the $\Pi$ in there: it means that you have to multiply with the group law in $G_1$ all of the $e(g^{q_i(s)},g^{P_i(s)})$ together to get the group element $e(g,g)$. –  bob Oct 11 '12 at 19:01
show 1 more comment