I'm studying a protocol whose security is based on the following assumption: given $g_1, g_2, A, B \in \mathbb{F}_p ^*$ with $g_1, g_2, A \neq 1$ and $g_1 \neq g_2$ , it is difficult to find exponents $r_1,r_2, d$ s.t. the following equation holds: $$ g_1^{r_1}g_2^{r_2} \equiv A^dB \ \ (\mbox{mod} \ p) $$ The paper I'm reading states "this is a type of discrete logarithm problem, hence it is assumed hard to solve". I'm not sure why this last sentence is true: initially I thought I could show this problem was harder than the DLP by saying "if I could solve this problem for given $g_1, g_2, A, B$, in particular I could solve it for $g_2 = A = 1$, so I could solve $g_1^{r_1}=B$, which is a DLP". But my argument is fallacious as $g_2$ and $A$ are different from $1$ by hypothesis. I would really like to have some proof like the one I was trying to show, so that I can bring this problem back to the DLP hardness assumpion, and don't assume anything more. If someone know about similar-discrete-log-problem or see any way to show this problem is harder than the DLP, please help me! Thank you in advance
$\begingroup$
$\endgroup$
5
-
$\begingroup$ But if you can solve discrete log, can't you just pick arbitrary $r_1, r_2$ and solve $A^d = g_1^{r_1}g_2^{r_2}B^{-1}\bmod{p}$? That makes your problem easier (but not necessarily strictly) than discrete log. $\endgroup$– CurveEnthusiastCommented May 19, 2017 at 16:01
-
$\begingroup$ @CurveEnthusiast: actually, it shows that it is no harder than discrete log; see my answer that also shows that it is no easier... $\endgroup$– ponchoCommented May 19, 2017 at 16:05
-
$\begingroup$ @CurveEnthusiast yes you are right, but I hoped to prove it is harder.. and btw, I'm sorry: in the question I wrote \emph{harder} instead of \emph{no easier}, thanks poncho $\endgroup$– richardCommented May 19, 2017 at 16:37
-
1$\begingroup$ Of course, I've shown that a random instance of above is as hard as a random instance of the DLP problem. One thing that the paper might not do is show that they have a random instance; if (say) there's a known relationship between $g_1, g_2, A, B$, it might be a lot easier... $\endgroup$– ponchoCommented May 19, 2017 at 17:11
-
$\begingroup$ @poncho we can (slightly) simplify your proof by taking $s_4 = 1$, right? Do we actually need a non trivial exponent for $H$? $\endgroup$– richardCommented May 19, 2017 at 19:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The standard way to prove this problem is at least as hard as the DLP problem is to show that, with an Oracle that can solve this problem, you can solve the DLP problem.
Here's how to do that (and we'll assume that the Oracle will solve random instances with nontrivial probability):
Given the DH problem $G^x = H$, find $x$, we pick random values $s_1, s_2, s_3, s_4$, and form the problem:
$$(G^{s_1})^{r_1} \cdot (G^{s_2})^{r_2} = (G^{s_3})^d \cdot (H^{s_4})$$
This is a random instance, and so the Oracle gives us, with nontrivial probability, values $r_1, r_2, d$, and so we know that:
$$s_1r_1 + s_2r_2 \equiv s_3d + xs_4 \pmod{p-1}$$
We know everything other than $x$ in the above equation, we solve it, and our work is done
-
$\begingroup$ Do you mean $s_3$ and $s_4$ instead of $r_3$ and $r_4$? $\endgroup$ Commented May 19, 2017 at 16:09
-
$\begingroup$ @CurveEnthusiast: yeah, I had initially denoted the random values $r_1, ...$, and then realized those were the same variable names as in the problem statement; I switched them to $s_1, ...$, but didn't update all instances... $\endgroup$– ponchoCommented May 19, 2017 at 16:55
-
$\begingroup$ @poncho we can (slightly) simplify your proof by taking $s_4 = 1$, right? Do we actually need a non trivial exponent for $H$? $\endgroup$– richardCommented May 20, 2017 at 10:50
-
$\begingroup$ @richard: I don't believe we can. It might be that our Oracle to sometimes solve random instances of your problem might not happen to work for specific value of $B$ (obviously, it has to work for a nontrivial fraction of them; it might consistent fail for some of them), and it might be that the DLog problem happens to pick that value for $H$. By completely randomizing things, we avoid such possibilities... $\endgroup$– ponchoCommented May 23, 2017 at 2:59