GPG's vulnerability to quantum cryptography
Robert J. Hansen
rjh at sixdemonbag.org
Mon May 19 22:16:38 CEST 2014
> I do however believe that factoring a product of two large
> prime numbers might either be the subject of a sudden mathematical
> breakthrough, or that the solution is already known to my
> adversaries but this fact has been kept secret.
tl;dr summary of the rest of this email -- don't focus on
factorization, and be careful of thinking about a post-RSA future.
I can't comment on this (for the most pedestrian of reasons: I can't
predict the future, and if anyone currently knows how to do it they
sure haven't told me), but a little commentary might be appropriate:
1. We would like integer factorization to belong to complexity class
NP-Complete, but there are good reasons to think it's not. If its
NP-Completeness could be proven, then so much of mathematics would be
transformed that I'm not sure continued confidence in *anything*
involving computers would be warranted.
2. If someone could prove IFP was in P, that would be ...
breathtaking, to say the least. Same thing: if it could be proven,
that would be such a seismic shift -- and would foment such
revolutions in mathematics -- as to jeopardize confidence for years
until the repercussions of it were fully understood.
3. If IFP is NP-intermediate, as it's currently conjectured to be,
then nothing short of quantum computation will endanger it.
4. But RSA is not the same as the IFP, and Dan Boneh has written a
great paper showing that it may be possible to break RSA without
needing to factor anything. We don't know how to do it, we don't even
have *hints* about how to do it, just a good paper from Dan Boneh
showing that it may in fact be possible to do it. But this, too,
would be such a breakthrough as to jeopardize confidence, etc., etc.
5. If and when RSA gets broken, all bets are off.
More information about the Gnupg-users