[jvfbeoze] Proposals for prize problems for cryptography

Prove that the general number field sieve is asymptotically the fastest non-quantum algorithm for factoring a general integer, or create a faster algorithm.

Prove that GNFS is the fastest algorithm for solving the discrete logarithm problem on the group of integers modulo a prime, or create a faster algorithm.

Prove that factoring the modulus is the fastest way to solve the RSA problem, or create a faster algorithm.

Prove that the quadratic gap in computational effort between the attacker and defender as seen in Merkle puzzles is the largest gap possible, or create a cryptosystem with a larger gap.  (Appears to be solved in Barak, et al. "Merkle Puzzles are Optimal")

Each of these questions is critical for modern asymmetric key cryptography.  There ought to be giant prizes similar to the Clay Millennium prizes.

Similar questions could be asked about elliptic curve cryptography, but I am not versed enough to be asking them.