[tahoe-dev] What's the state of the art in factorization?

[Zooko O'Whielacronx]

On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves <sneves at dei.uc.pt> wrote
(on the cryptography at metzdowd.com list):
> [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf

I've been looking at that one, with an eye to using it in the One
Hundred Year Cryptography project that is being sponsored by Google as
part of the Google Summer of Code (see recent discussions on the
tahoe-dev archives for April 2010 [1]).

Later I discovered this paper [2] which appears to be an improvement
on that one in terms of performance (see Table 1 in [2]) while still
having a tight reduction to the Computational Diffie-Hellman (CDH)
problem. Strangely, this paper [2] doesn't appear to have been
published anywhere except as an eprint on eprint.iacr.org. I wonder
why not. Is there something wrong with it?

I still have some major questions about the funky "hash into a curve"
part of these schemes. I'm hoping that [3] will turn out to be wrong
and a nice simple dumb efficient hack will be secure for these
particular digital signature schemes.

Of course if the newfangled schemes which reduce to a random instance
of a classic hard problem work out, that would provide an even
stronger assurance of long-term safety than the ones that reduce to
CDH. See for example the paper [4] that I mentioned previously on the
cryptography at metzdowd.com mailing list. Unless I misunderstand, if you
can break that scheme by learning someone's plaintext without knowing
their private key, then you've also proven that P=NP!

Unfortunately that one in particular doesn't provide digital
signatures, only public key encryption, and what I most need for the
One Hundred Year Cryptography project is digital signatures.

Regards,

Zooko

[1] http://allmydata.org/pipermail/tahoe-dev/2010-April/date.html
[2] http://eprint.iacr.org/2007/019
[3] http://eprint.iacr.org/2009/340
[4] http://eprint.iacr.org/2009/576