[Cryptography] Other obvious issues being ignored?

[Joshua Hill]

Joshua Hill <josh-crypto at untruth.org> wrote:
> If you know the factorization of the order of the group, you can apply
> Pohlig-Hellman to decompose the discrete log problem on a large group
> into several discrete log problems on (perhaps much!) smaller groups. This
> was traditionally coupled with the Pollard-rho algorithm or brute force,
> but in cases where more modern discrete log algorithms work, you can
> just as well use these more advanced algorithms to solve the subproblems.

Watson Ladd responded:
> This is not true. The size of the numbers that need to be smooth
> depends on the modulus, which Pohlig-Hellman doesn't reduce.

I'd like to voice my agreement with Watson Ladd's response to my e-mail.

The issue at hand here is my statement "you can just as well use these
more advanced algorithms to solve the subproblems". This is perhaps
technically true, but you only gain an actual advantage in the case of
the group theoretic DL algorithms (giant step / baby step, Pollard-rho,
brute force).

It is not obvious how to apply the (asymptotically faster) sieving
/ smoothness based algorithms in this setting in a way that buys us
anything. You can certainly apply Pohlig-Hellman, and then use NFS for the
subproblems, but you'd have to build up a factor base sized appropriately
for the overall modulus (p) rather than some reduced bound associated with
the smaller order groups that you're really working with for each step.
This leaves us with a runtime that is worse than directly solving the
single discrete log problem, because you're now solving several discrete
logs over the same modulus rather than just one.

There's actually a small bit in the HAC on this topic, section 3.6.6
(p. 113):
http://cacr.uwaterloo.ca/hac/about/chap3.pdf

My apologies for any confusion,
Josh