# 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

## 1 Answer

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

2
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 80, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9293544888496399, "perplexity_flag": "head"}