2
$\begingroup$

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?

|improve this question|||||
$\endgroup$
  • $\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
1
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\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.