1
$\begingroup$

Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that satisfies the equations $g^{x^{a_i}}\equiv b_i\ (mod\ p)$ for all $i=1,...,n$.

Is it hard to compute to compute x (assuming the hardness of DLOG)?

And a weaker version of the above problem, given a new group element $b_{i+1}$, is it hard to compute an integer $a_{i+1}$ such that $g^{x^{a_{i+1}}}=b_{i+1}$?

$\endgroup$
3
  • $\begingroup$ This question seems related but not a duplicate. How are the $a_i$ chosen? $\endgroup$
    – Maeher
    Jun 28, 2022 at 13:14
  • $\begingroup$ Good comment, I forgot to mention it. They are selected randomly random for some big predefined set. I'll update the question. $\endgroup$
    – Doron
    Jun 28, 2022 at 13:19
  • $\begingroup$ Good catch. Yes, it is mod some $p$. I'll update the question. $\endgroup$
    – Doron
    Jun 28, 2022 at 13:25

1 Answer 1

1
$\begingroup$

A little notation: we'll write $\mathrm{DLOG}(h,y)$ for a magic, general purpose discrete logarithm solver that returns $z$ where $h^z=y$ in our group of order $q$ and $\mathrm{DH}(h,c,d)$ for a magic, general purpose Diffie-Hellman solver in our group which returns $h^{ef}$ where $c=h^e$ and $d=h^f$.

For your first question, if we have a magic DLOG solver then your problem is not hard. If we call our solver with $h=b_i$ and $y=b_j$ we will get the answer $x^{a_j-a_i}\mod q$. If any of pair of $a_i$s differ by 1 this immediately gives us $x$, otherwise pick two pairs $(i,j)$ and $(k,\ell)$ such that $(a_j-a_i)$ and $(a_\ell-a_k)$ are coprime (it is overwhelmingly likely that such pairs exist). Now by Bezout's identity there are values $r$ and $s$ such that $r(a_j-a_i)+s(a_\ell-a_k)=1$ and we see that $$\mathrm{DLOG}(b_i,b_j)^r\mathrm{DLOG}(b_k,b_\ell)^s\equiv x\pmod q.$$

On the other hand, if your an easy solution to your first problem exists this would provide an easy proof that Diffie-Hellman is exactly as hard as the discrete logarithm problem. This is an open conjecture and so we do not know how to demonstrate the reverse implication. To see how this would show that $\mathrm{DH}\rightarrow \mathrm{DLOG}$ note that a Diffie-Hellman oracle can be used to create additional $(a,b)$ instances by $\mathrm{DH}(g,b_i,b_j)=g^{x^{a_i+a_j}}$ and starting from $g^{x^1}$ we can use our DH oracle to compute $b$ for any given $a$.

$\endgroup$
3
  • $\begingroup$ Thanks a lot! So I understand that in some settings this problems is actually easy (if you are able to compute the $DLOG(b_i,b_j)$ pairs). $\endgroup$
    – Doron
    Jun 28, 2022 at 15:45
  • $\begingroup$ Regarding your your reduction, I think you meant to write $DH(g,b_i,b_j)=g^{x^{a_i+a_j}}$, is that correct? $\endgroup$
    – Doron
    Jun 28, 2022 at 15:47
  • $\begingroup$ @crypto.stackexchange.com/users/56485/doron Yes, there are instances where discrete logarithms are easy (e.g. multiplicative groups of finite fields of small characteristic such as $GF(2^{6000})$). You're correct about the typo and I shall now correct it. $\endgroup$
    – Daniel S
    Jun 28, 2022 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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