Let :

$G_{0}$ and $G_{1}$ be two multiplicative cyclic groups of prime order $p$, $g$ be a generator of $G_{0}$ and $e$ be a bilinear map,

$e : G_0 \times G_0 → G_1$

and let $𝐶_{1} = 𝑔^{𝛽𝑠_{1}} $, $ 𝐶_{2} = 𝑔^{𝛽𝑠_{2}} $ , ... , $ 𝐶_{𝑛}= 𝑔^{𝛽𝑠_{𝑛}} $; $ 𝐷=𝑔^{(𝛼+𝑟)/𝛽} $

such that $\alpha, \beta, r, s_{1}, s_{2}, ..., s_{n} \in Z_{p}$

Given $s_{x} \in Z_{p}$ ($x \neq i, i=1, ..., n$), and knowing $e\left( C_{1}, D\right), e\left( C_{2}, D\right), ..., e\left( C_{n}, D\right)$. I would like to know if it is possible to compute the value of $e(C_{x},D)$ and/or $D$.

Secret elements: $D$, $e(C_{x},D)$.

Public elements: $𝐶_{1}$, $𝐶_{2}$, ..., $𝐶_{n}$, $𝐶_{x}$, $e(C_{1},D)$, $e(C_{2},D)$, ..., $e(C_{n},D)$.

If it is not possible, how to prove that?

  • $\begingroup$ what is $C_x$? Of course if you know $C_x$.What is known to the attacker?What is public and secret? $\endgroup$ – curious May 5 '15 at 10:39
  • $\begingroup$ In my question, the value of $D$ is kept secret. $\endgroup$ – watou May 5 '15 at 10:43
  • $\begingroup$ @curious : I have just updated my question. $\endgroup$ – watou May 5 '15 at 10:47
  • 1
    $\begingroup$ I think your question is a bit difficult to read because your notation is more difficult than necessary. If you want, you can also write such things just saying like: "Knowing $g^a,g^b$, is it possible to compute $g^{ab}$?". So you don't need all the $C$s and the $D$s. (But I would not change the current question now.) $\endgroup$ – Chris Sep 2 '15 at 18:52

The only way i can see to evaluate $e(C_x,D)$ is to recover $D$ from a previous known pairing $e(C_i,D)$. However due to the Fixed Argument Pairing Inversion 1 assumption this is computationally hard.

  • $\begingroup$ Is it possible to prove that in a formal manner? $\endgroup$ – watou May 5 '15 at 10:55
  • $\begingroup$ It is more than straightforward i think following the reductionist approach $\endgroup$ – curious May 5 '15 at 10:56
  • $\begingroup$ you could try to find a relation between $C_x$ and the $C_i$ which will be translated into $G_1$ $\endgroup$ – Florian Bourse May 5 '15 at 12:53
  • $\begingroup$ @FlorianBourse even if there is a correlation in $C_x-C_i$, still you have to recover D $\endgroup$ – curious May 5 '15 at 14:42
  • 1
    $\begingroup$ @watou I don't really know, the only way to know if there is an attack is to formally prove the security. What I am saying is that an argument such as: "the only way i can see..." will never make a proof. $\endgroup$ – Florian Bourse May 11 '15 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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