Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

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$?

share|improve this question
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

up vote 2 down vote accepted

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$.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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