Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Henrick Hellström Mar 1 '13 at 17:42
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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$? –  Henrick Hellström Mar 1 '13 at 22:32
    
@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$ –  poncho Mar 1 '13 at 22:57
    
Right, that explains your third edit, thanks. –  Henrick Hellström Mar 1 '13 at 23:14
    
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 –  Habib Mar 2 '13 at 13:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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