D. J. Bernstein
Authenticators and signatures
A state-of-the-art public-key signature system

Cryptanalysis

The factoring problem

An attacker, given a public key pq, can try to figure out the factors p and q. The fastest known method to find these factors is the number-field sieve. This would be an extremely expensive computation, because pq is so large.

I realize that ``extremely expensive'' is not very precise. It is, unfortunately, not easy to pin down the exact cost. This is an area of current research.

There is a reasonably large gap between the largest public factorization reports (under 2^600) and the moduli pq in this system (over 2^1536).

Are there better attacks?

Forgery via factorization is a generic attack: it succeeds for any functions H0 and H1 used in the system. My rwtight paper proves that all generic attacks against this system can be converted into algorithms to factor pq at comparable speed.

Of course, it's possible that there are faster non-generic attacks against the particular functions H0 and H1 that I selected. It's also possible that there are factorization algorithms faster than the number-field sieve.