Robert J. Hansen
rjh at sixdemonbag.org
Wed Apr 18 16:14:03 CEST 2007
-----BEGIN PGP SIGNED MESSAGE-----
> Note that breaking Diffie-Hellman and other discrete logarithm based
> algorithms is thought to be nearly equivalent to factoring, but has
> not been proven to be so.
Going off the top of my head, the DLP is known to be greater than or
equal to the difficulty of the IFP. You can make strong arguments
that they're equal difficulty in a computational-theoretic sense, and
you can make strong arguments that in real silicon DLP will be
stronger due to our current lack of understanding of how to
efficiently use the general number field sieve for the DLP. The
current state of the art in the GNFS requires a large amount of
storage overhead for the DLP, while the storage overhead for the IFP
is comparatively minimal.
As a word of warning, comparing DLP to IFP is a spectacularly black
art. There are so many nuances to it that just expressing some of
the ideas in English is difficult.
As further warning: it's 9:10am, I haven't yet had my morning cup of
coffee, and I'm working without my references. This being the
internet, there's also a nonzero chance that I'm barking mad.
Confirm this information before relying on it.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)
-----END PGP SIGNATURE-----
More information about the Gnupg-users