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
From: email@example.com Date: Wed, 22 Jun 94 11:23:10 PDT To: firstname.lastname@example.org 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.
Return to June 1994
Return to “Roger Bryner <email@example.com>”