Let's consider a discrete logarithm

$\beta \equiv \alpha ^{x} \bmod \,\, p$

We can solve it using Pohlig-Hellman algorithm. And, if $p-1 = tq$ where $q$ is a large prime factor, we can avoid any leakages by choosing $\beta=a^{t}$.

This is what my professor said at lesson, however i don't succeed in understanding why it avoids any leakages. Can you explain to me why ? Also with calculations if it's possible


Probably what your professor meant is that you start with any group element $\alpha$, and then use $g := \alpha^t$ as the generator for a cryptosystem such as Schnorr signatures, as long as $g$ is not itself the identity.

Why? If $g \ne 1$, then $g$ is guaranteed to have prime order $q$, because $g^q = (\alpha^t)^q = \alpha^{tq} = \alpha^{\phi(p)} = 1$, and since $q$ is prime there are no smaller orders possible for $g$ (just start over with a different $\alpha$ if it is).

Then when you choose a public key $\beta := g^x$ for secret $x$, you're guaranteed that $\log_\alpha \beta \equiv 0 \pmod t$. (Of course, you could have equivalently chosen $\beta := \alpha^{tx}$, but precomputing $g$ may be cheaper.)

Now since the group generated by $g$ has prime order, Pohlig–Hellman has no advantage over any other DLOG algorithms.

  • $\begingroup$ Can you explain me why $\log_\alpha \beta \equiv 0 \pmod t$ ? $\endgroup$ – AleWolf Nov 18 '19 at 7:51
  • 1
    $\begingroup$ $\log_\alpha \beta = \log_\alpha g^x = \log_\alpha \alpha^{tx} = tx$ $\endgroup$ – Squeamish Ossifrage Nov 18 '19 at 8:09

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.