0
$\begingroup$

Assume that we have an already assigned Multiplicative Cyclic Group $\mathbb Z_p^*$ with order $q=p-1$, and $p$ is a prime number, is it possible to create a bilinear function $\hat{e}: \mathbb Z_p^* \times \mathbb Z_p^* \rightarrow \mathbb G_2$ with the property that follows:

$$\hat{e}(g^{a},g^{sb})=\hat{e}(g^{b},g^{sa})$$

$g$ is a generator for $\mathbb Z_p^*$, and $\mathbb G_2$ is also a Multiplicative Cyclic Group with order $q$

it seems that if the creation of this function is practical in polynomial time then there should be new attacks on some cryptographic protocols with security property of anonymity.

|improve this question|||||
$\endgroup$
  • $\begingroup$ You might have to add more information about the properties of the groups you are referring to. It is already known that the discrete logarithm problem is easier to solve in some groups, than it is other groups. $\endgroup$ – Henrick Hellström Mar 1 '13 at 17:42
1
$\begingroup$

If you can find such an efficiently computable function (other than the trivial solution $\hat{e}( x, y ) = 1\ \ $ for all $x$, $y$), then you have shown that the decisional Diffie-Hellman problem is easy. That is, given $g$, $g^a$, $g^b$, $g^c$, you can check whether

$$ab = c$$

simply by testing:

$$\hat{e}( g^a, g^b ) = \hat{e}( g, g^c)$$

The decisional Diffie-Hellman problem is believed to be hard in appropriately sized Multiplicative Cyclic groups, hence we believe that there is no such efficiently computable $\hat{e}$

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Given the formula in the question, I think you have to set $xy=z$, $x=a$, $y=sb$, $b=z=xy$ and consequently $s=x^{-1}$, and get $e(g^x,g^y)=e(g^z,g)$ which is equivalent to what you write in your second edit. However, doesn't this require either x or y to be invertible $\mod p-1$? $\endgroup$ – Henrick Hellström Mar 1 '13 at 22:32
  • $\begingroup$ @HenrickHellström: no, you have $a=x$, $b=1$, $s=y$; plugging those into the property gives $\hat{e}(g^x, g^y) = \hat{e}(g, g^{xy})$. If they are both $\hat{e}(g, g^z)$, that indicates that $g^{xy} = g^z$ $\endgroup$ – poncho Mar 1 '13 at 22:57
  • $\begingroup$ poncho's answer is acceptable for me, but for addition I want to add that the DDH problem does NOT hold for $\mathbb Z_p^*$ but it holds for some sub groups of $\mathbb Z_p^*$ for more information take a look at: link $\endgroup$ – Habib Mar 2 '13 at 13:54

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.