Let $Ans$ be the product of two pairings : $e(g,h)^{k} \times e(g,h)^{r}=Ans$

If everybody knows only $[g,h,e(g,h)^{k}]$ but $[r,Ans]$ is not known. In the discrete logarithm problem, the user knows two values. In this scheme, the user only know one value.

Is the discrete logarithm problem suitable for this scheme or not?

  • $\begingroup$ What task is this "scheme" supposed to perform? $\endgroup$ – fkraiem Apr 5 '16 at 7:08
  • $\begingroup$ To hide value of $Ans$ from others, only user who know $r$ can know $Ans$. $\endgroup$ – myat Apr 5 '16 at 8:53
  • 1
    $\begingroup$ So this is a sort of encryption scheme? If yes, you should describe how you generate keys, encrypt, and decrypt. $\endgroup$ – fkraiem Apr 5 '16 at 8:58
  • $\begingroup$ For simple case, consider the value of $r$ is a value from $Z_{p}$ value. Main point is discrete logarithm is suitable for security proof or not. $\endgroup$ – myat Apr 5 '16 at 9:17

First of all, let us simplify the equation by replacing things that the attacker can compute with known constants. We come up with:

$$a \cdot b^x = y$$

where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$.

If it is sufficient for an attacker to find a solution, he can do that easily; he can select a random $x$, and solve it for $y$; there's a solution.

If he needs to find "the correct" solution (that is, the one possible $x, y$ pair that satisfies additional criteria), he doesn't have enough information to pick out which one it is. He might be able to if he knows what that additional criteria is; it would depend on what that looks like.

|improve this answer|||||
  • $\begingroup$ poncho.I don't know the meaning of "a solution".As a definite $y$ value is defined, I think it is to find the correct solution. Isn't it? $\endgroup$ – myat Apr 6 '16 at 4:21
  • $\begingroup$ @astyst: a solution is a pair $(x, y)$ (or $(r, Ans)$ in your terminology) that solves the equation. As for a definite y value is defined, how is the attacker supposed to recognize the correct solution (as opposed to the huge number of possible incorrect solutions)? Within your scheme, there probably is more information that an attacker can use (if he needs a specific solution); however you haven't given us that. $\endgroup$ – poncho Apr 6 '16 at 13:08

I am really not sure about what you are trying to do. If you simply want to prove that $Ans = e(g,h)^k \times e(g,h)^r$ is hidden given only $(g,h,e(g,h)^k)$, then this is trivial and does not require any hypothesis at all (in particular, no discrete logarithm problem is involved). Indeed, this is perfectly equivalent to the problem of finding $e(g,h)^r$ given only $g$ and $h$, for an unknown $r$. If we denote by $\mathbb{G}$ the group generated by $e(g,h)$, then we do simply know a generator of $\mathbb{G}$, $Ans$ can be any element of $\mathbb{G}$ hence there is no way one can guess it (it does not come from any assumption, it's like saying "guess the value I'm thinking about" without telling anything about the value).

|improve this answer|||||

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.