GPG's vulnerability to quantum cryptography

[Robert J. Hansen]

> 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.