1
$\begingroup$

Given two values $g^{a_1}, g^{a_2}$ where $a_1, a_2 \in \mathbb{Z}_q$ and $g$ is a generator of group $\mathbb{G}$ of order $q$. Discrete logarithm is assumed to be hard in $\mathbb{G}$.

Is there a way to find the value $g^x$ such that $x = a_1 + a_2 \text{ mod } p$ with p < q. We also know, $a_1, a_2 < p$. Here $p,q$ are large primes, for example $128, 256$ bit respectively.

$\endgroup$
3
  • $\begingroup$ I was hoping to find some scheme which does not involve solving the discrete log problem $\endgroup$
    – MeV
    Jun 28 '21 at 15:36
  • $\begingroup$ Nice problem. I assume it's homework, thus won't give a complete answer, only hints; also, I'm not quite sure. I think it's asked a proof by contraposition that what the question asks can't be. For given $p$, $q$, and the ability to perform group operations, any algorithm doing what's asked can be turned into an algorithm that solves any DLP in the group with feasible effort. If we disregard memory, It think this effort is about $2^{65}$ group operations (if that can be lowered, I want to know how). [summary of earlier comments, now removed]. $\endgroup$
    – fgrieu
    Jun 29 '21 at 9:15
  • $\begingroup$ oh no, its not homework but thanks for the inputs. $\endgroup$
    – MeV
    Jun 29 '21 at 20:45
0
$\begingroup$

Let $\mathbb G$ with generator $g$, it's 256-bit prime order $q$, and the 128-bit prime $p$ be known and fixed.

Assume we get an algorithm $\mathcal A$ which on input $(h_1,h_2)\in\mathbb G^2$, with $h_1=g^{a_1}$, $h_2=g^{a_2}$ for random $a_1,a_2\in\mathbb Z_q$, outputs $h_3=g^{a_1+a_2\bmod p}$ with non-vanishing probability, as in the question.

Define algorithm $\mathcal A'$ that on input $h\in\mathbb G$ attempts to output $y$ with $g^y=h$, and towards this:

  • draws $u$ random in $\mathbb Z_q$, computes $h_1=g^u\;h$, which now is random in $\mathbb G$; there's thus a unique (as yet unknown, random) $a_1\in\mathbb Z_q$ with $g^{a_1}=h_1$
  • draws $a_2$ random in $\mathbb Z_q$, computes $h_2=g^{a_2}$
  • runs $\mathcal A$ with input $(h_1,h_2)$, gets $h_3$ assumed to be (with non-vanishing probability) $g^{a_1+a_2\bmod p}$
  • finds $x\in\mathbb Z_q$ with $0\le x<p<2^{128}$ such that $g^x=h_3$, which requires in the order of $2^{66}$ group operations using Polard's rho with distinguished points, feasibly little memory, and is easily distributed
  • computes $r=x-a_2\bmod p$; it holds $a_1\equiv r\bmod p$, and $0\le a_1<q$; let the (sd yet unknown) $s\in\left[0,\left\lfloor q/p\right\rfloor\right]$ be such that $a_1=r+s\,p$, thus $g^{r+s\,p}=h_1$, thus $g^{s\,p}=h_1\,g^{q-r}$, thus $g^s=(h_1\,g^{q-r})^{p^{-1}\bmod q}$
  • computes $h_4=(h_1\,g^{q-r})^{p^{-1}\bmod q}$; it holds $g^s=h_4$ and $s<2^{129}$
  • finds $s$ by essentially the same method as $x$
  • computes $a_1=r+s\,p$, which is thus such that $g^{a_1}=h_1$
  • computes and output $y=a_1-u\bmod q$, which is such that $g^y=h$.

Our algorithm $\mathcal A'$ is thus able to computes the discrete logarithm $y$ to base $g$ of any given element $h$ in $\mathbb G$ with non-vanishing probability, and feasibly little works. This is hypothesized impossible. Hence our assumption that $\mathcal A$ exists is false.

We thus answer the question in the negative.

$\endgroup$
1
  • $\begingroup$ This is tentative. I welcome critic, pointing hole in the reduction, or a tighter one. $\endgroup$
    – fgrieu
    Jul 1 '21 at 8:44
0
$\begingroup$

It seems that finding $g^x$ is nonsense, duo to there being $g^x=g^{a_1} * g^{a_2}\text{ mod }q$. However, we could not judge that whether $x=a_1+a_2 \text{ mod } p$.

Another way, we can let the generator $g=r^{(q-1)/p}\text{ mod }q$, where $r\in(1,...,q-1)$ and $p$ is a large prime such that $q-1 \text{ mod } p = 0$. Now, according to the Fermat Therom, the result of $g^x\in(g^0,g^1,...,g^{p-1})\text{ mod } q$ for any $x\in Z_q$. Howerver, I still think we could not confirm that whether $x=a_1+a_2 \text{ mod } p$ in case of $a_1+a_2=(p + b)>p$ where $b$ is the $x$.

If the equation was $x\equiv a_1+a_2 \text{ mod } p$, then the above method could confirm that.

$\endgroup$
2
  • 1
    $\begingroup$ It's not clear what you mean by $g^x=g^{a_1} * g^{a_2}\text{ mod }q$. The group considered is not $\mathbb Z_q^*$, which has order $\varphi(q)<q$ . It's considered an unspecified group $\mathbb G$ with an element $g$ of order $q$. We can say that $g^{a_1} * g^{a_2}=g^{a_1+a_2}=g^{a_1+a_2\bmod q}$, but $g^{a_1} * g^{a_2}\text{ mod }q$ is undefined. $\endgroup$
    – fgrieu
    Jun 28 '21 at 9:24
  • $\begingroup$ @fgrieu I thought all operations were in $Z_q$, ignoring that point. I need to further improve my answer. $\endgroup$
    – ming alex
    Jun 29 '21 at 0:37

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.