Proving the Riemann Hypothesis and Impact on Cryptography

Question

I was talking with a friend last night, and she raised the topic of the Clay Millennium Prize problems. I mentioned that my "favorite" problem is the Riemann Hypothesis; I explained what it posits and mentioned that, if proven, it would have great impact on cryptography. Her immediate response was, "Why do we have to wait to prove it? We're pretty sure it's true, so why can't cryptographers assume so until shown otherwise?" As weird as it sounds, I was unable to give a good response.

In "popular mathematics" culture (i.e. not necessarily accurate but well-known), I've heard over and over that "proving the Riemann Hypothesis would cause a lot of problems in Cryptography." (See, for instance, the Numb3rs episode where a mathematician supposedly solves it and puts all of encryption at risk.) However, if a positive answer to the Riemann Hypothesis would result in us being able to break much of modern encryption, why couldn't we just assume that it has a positive answer and use that "maybe-valid" result to break codes now?

My best guess is that the idea that R.H. puts cryptography at risk is actually false; instead, either the process to reach the solution is the risky part, or it just produces a theoretical attack strategy that is still infeasible. That is, it would prove modern encryption insecure to some attack, but that attack technique is not possible at this time (much like creating a collision with SHA-1; theoretically, but not practically, possible).

tl;dr: I've been told that a positive answer to the Riemann Hypothesis is bad for cryptography. Why can't we assume a positive answer now to break codes, but just realize that what we're doing isn't guaranteed correct?

Answer 1

She is right - we already do generally assume the truth of the Riemann hypothesis, but knowing that RH is true does not provide any way to attack primes-based cryptography like RSA. Rather it's actually the opposite that is true, if anything. More on that in a second. But the implications of the Riemann Hypthesis (either way) for cryptography is greatly exaggerated and overhyped; the most likely truth is that a determination one way or the other won't affect security at all, and if it did have any effect it would likely be only theoretical.

Also see this question: Would a proof of the Riemann hypothesis affect security?

RH has numerous implications for regularity in the distribution of primes. Primes-based security is based on the belief that finding one of the two prime factors of an appropriately-generated semiprime is difficult. If there were a chink in the regularity of primes that made some part of them more predictable than they otherwise would be, then conceivably such a phenomenon could be exploited to detect prime factors better than we currently know how. Thus it would be a counterexample to RH that could actually pose a problem, not its truth.

But whether or not RH's negation could say something about primes that could be exploited for detecting prime factors is not clear. The most notable consequence of RH is the best error term for counting primes up to a given magnitude using the prime number theorem. Can you see how primes appearing a little more frequently than we currently believe could be transformed into a clever algorithm for prime factor detection? I don't think there is any known literature on how a nontrivial zero off the critical line could be utilized in cryptography.

The popular attacks and ideas on how to approach the Riemann hypothesis - noncommutative geometry and trace formulas, the field with one element, quasicrystals, quantum energy levels viz Hilbert-Polya and Berry-Keating, etc. - all seem to delve into territory far beyond and properly outside of analytic number theory, which is the subject dedicated to statistical and asymptotic properties of primes. (Although if anything does happen to stick in the future it will subsequently become subsumed into number theory.) But it is at least possible that the ideas that will be used in proving the Riemann Hypothesis (assuming it's true) will be strictly number-theoretic and provide direct insight into the structure of the primes that we did not previously have, that could conceivably be exploited to attack primes-based security. Once again, though, these are some pretty big ifs.

Answer 2

As with all these very difficult conjectures which we are sure to be true, but are unproven, the truth of the statement itself holds some profound insight which we can bring to bear on various matters - however the means of the proof also usually reveals some deep insight into numbers.

So taking Fermat's last theorem as an example, the proof arrived at by Andrew Wiles demonstrated without ambiguity a powerful relationship between modular elliptic curves and number theory. As a result of the proof we now know that further research in this area has the power to yield very difficult results.

Bringing this back to the last part of your question... the reason we need the proof in order to attack cryptography, is that the means by which it is proven will reveal to cryptographers the means by which they can successfully attack very difficult encryption algorithms. This will, of course, show us how to create more resilient encryption systems in due course but it will also, in the interim, make current systems less resilient.