From: catalyst-remailer@netcom.com
Date: Wed, 22 Jun 94 11:23:10 PDT
To: cypherpunks@toad.com
Subject: RSA Key Size & QP
Message-ID: <199406221823.LAA11794@mail2.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


A wild card here is the recent work in quantum computing,  done
at AT&T and reported in a recent post by Pal Vitanyi.
With a specialized quantum computer (not clear yet whether one could
economically built it, but it's theoretically possible) one
can factor in polynomial time (computational class "QP", or
something like that).  If cycles on such a computer would be,
say, 1,000 times more expensive than on your PC, then
cracking the key would be 1,000*O(keysize^c) more expensive than 
generating it, not 1,000*O(c^keysize).  Having a keysize of, say,
8 kbits instead of 1 kbit in this circumstance is not at all overkill; 
it makes a practical economic difference.   Of course if your 
info is _very_ valuable and the polynomial is of small degree, 
even a large key size won't help much.

If such a device was built, we'd want to switch to a cryptosystem 
whose inverse is not in QP; but some of our current communications
would be compromised.  If a QP machine is with even small probability
feasible within the next few decades (or whatever your timeline 
of concern is), it makes sense to use larger key sizes.