1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Oct 19, 2012 at 5:49
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Oct 19, 2012 at 5:51
  • $\begingroup$ 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... $\endgroup$
    – bob
    Commented Oct 19, 2012 at 16:43

1 Answer 1

2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ so $e(g,g)=1$. I am always confused whether or not $e(g,g)=e(g,g)^{ord(G)}=1$ $\endgroup$
    – curious
    Commented Oct 11, 2012 at 9:38
  • $\begingroup$ So to conclude . In all bilinear mappings from $G$ to $G_1$ where $g$ the generator of $G$ $e(g,g)=1$Right? $\endgroup$
    – curious
    Commented Oct 11, 2012 at 11:24
  • $\begingroup$ 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). $\endgroup$
    – bob
    Commented Oct 11, 2012 at 11:54
  • $\begingroup$ So can i be sure that $e(g^{q_i(s)},g^{P_i(s)}) = e (g,g)$ holds? $\endgroup$
    – curious
    Commented Oct 11, 2012 at 12:57
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – bob
    Commented Oct 11, 2012 at 19:01

Your Answer

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

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