29
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ A lot of theorems (as far as I understand) are proven with the assumption "assume the Riemann hypothesis"--those more specialized in math can probably give more specific examples (I read about this in The Music of the Primes, an admittedly non-technical text written by a mathematician, and so, I hope, reliable) $\endgroup$ May 8, 2015 at 1:32
  • $\begingroup$ How do you think that RH is bad for cryptography? $\endgroup$
    – davidlowryduda
    May 8, 2015 at 1:35
  • 1
    $\begingroup$ Anyway, I'm interested in this question as well. My feeling (i.e., related to stuff I have read or think I have read) has been that the use of RH to break codes requires the construction of all primes, which would make factoring easier. My other feeling is that we now use primes that are big enough that, even if we could construct primes in series, we would still struggle to factor the 200-or-so digit primes we now use for encryption. $\endgroup$ May 8, 2015 at 1:36
  • 1
    $\begingroup$ @mixedmath That's the thing: I don't know it to be bad, but I've just heard over and over (from non-technical sources) that "Oh, if we proved R.H., really scary/bad things would happen." I'm wondering if that's a myth, truth, or something in between. EDIT: For instance, I've heard the factoring argument a lot that Michael mentions. Is this an actual result, a "lie to children" result, or something else? $\endgroup$
    – apnorton
    May 8, 2015 at 1:36
  • 9
    $\begingroup$ I'm pretty confident that's a myth. You can worry about P=NP, which suggests fast factorization (which breaks a lot, but not all, common cryptosystems). Once upon a time, people realized that RH implies polynomial time primality tests. This was a big deal until AKS came up with an unconditional primality test. There's a probabilistic factoring method that is conditional on RH, but it matches the heuristic time of the elliptic curve factorization method. Its only benefit is that its running time is rigorous, while elliptic curve factorization's running time isn't currently provable. No gain. $\endgroup$
    – davidlowryduda
    May 8, 2015 at 1:43

2 Answers 2

24
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Given recent news regarding the Riemann Hypothesis, this thread just became relevant again! $\endgroup$ Sep 28, 2018 at 2:32
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.