From: tcmay@netcom.com (Timothy C. May)
Date: Wed, 28 Sep 94 12:11:46 PDT
To: doug@OpenMind.com (Doug Cutrell)
Subject: Re: Anyone seen the 'quantum cryptanalysis' thread on sci.crypt?
In-Reply-To: <aaaf63c067021003af24@[198.232.141.2]>
Message-ID: <199409281911.MAA23364@netcom8.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Doug Cutrell wrote:

> I won't argue whether Shor's work will be implemented or not within any
> given time period, but I thought that one of the most important properties
> of it is that once (and if) achieved, the resources required to factor
> increasingly large moduli lengths go up only polynomially, not
> exponentially.
> 

I don't know. I skimmed Shor's stuff when it appeared. A lot more
analysis will be needed....and we have many decades left to get
started!

But even if the effort required grows polynomially, think of what that
means in real dollars, potentially. For example, just to imagine some
engineering numbers:

Alice is spending 15 cents worth of 2045 computer
power to use a 10,000-bit modulus for her messages.

The GSA (Global Security Agency, which replaced the NSA in 2008) has a
Shor machine, built with the latest nanotech rod-logic computers. It
cost them $32 billion to build, and it can "crack" a 10,000-bit
modulus in 10 days, at a cost of $20,000 (in 2045 dollars).

Alice switches to 15,000-bit moduli....the how much longer does it
take the Shor machine to do its thing? (Even if polynomial, what
factor?)

I won't speculate further. The numbers are indeterminate, even to
Shor, I suspect.

In any case, nothing for Cypherpunks to worry about in our lifetimes
(certainly not in my lifetime, and probably not in the lifetime of our
youngest members).


--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
Cypherpunks list: majordomo@toad.com with body message of only: 
subscribe cypherpunks. FAQ available at ftp.netcom.com in pub/tcmay