1994-06-22 - RSA Key Size & QP

Header Data

From: catalyst-remailer@netcom.com
To: cypherpunks@toad.com
Message Hash: 06cd617d9f26675bab7d4be1f3b01b68f9a3eedcc7ac6457f6a5b3b9463052f6
Message ID: <199406221823.LAA11794@mail2.netcom.com>
Reply To: N/A
UTC Datetime: 1994-06-22 18:23:10 UTC
Raw Date: Wed, 22 Jun 94 11:23:10 PDT

Raw message

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.