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$
4
  • $\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, 2015 at 10:39
  • $\begingroup$ In my question, the value of $D$ is kept secret. $\endgroup$
    – watou
    May 5, 2015 at 10:43
  • $\begingroup$ @curious : I have just updated my question. $\endgroup$
    – watou
    May 5, 2015 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, 2015 at 18:52

1 Answer 1

Reset to default
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$
9
  • $\begingroup$ Is it possible to prove that in a formal manner? $\endgroup$
    – watou
    May 5, 2015 at 10:55
  • $\begingroup$ It is more than straightforward i think following the reductionist approach $\endgroup$
    – curious
    May 5, 2015 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, 2015 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, 2015 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, 2015 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.