[4139] in cryptography@c2.net mail archive
Re: quantum cryptanalysis
daemon@ATHENA.MIT.EDU (Bruce Schneier)
Fri Feb 5 13:21:00 1999
Date: Fri, 05 Feb 1999 08:54:14 -0600
To: "John Kelsey" <kelsey@plnet.net>, <staym@accessdata.com>,
<coderpunks@toad.com>, "Bill Stewart" <bill.stewart@pobox.com>
From: Bruce Schneier <schneier@counterpane.com>
Cc: <cryptography@c2.net>
In-Reply-To: <199902050704.BAA02711@email.plnet.net>
At 01:04 AM 2/5/99 -0600, John Kelsey wrote:
>>At 10:45 AM 2/1/99 -0700, staym@accessdata.com wrote:
>>>Suppose someone discovers a way to solve NP-complete
>>>problems with a quantum computer; should he publish?
>>>Granted, the quantum computers aren't big enough yet, but
>>>the prospects look bright for larger ones in the near
>>>future. It would break all classical cryptography.
>
>>If he's a Good Guy, yes. It not only would revolutionize
>>cryptography (sigh - back to the couriers with briefcases
>>handcuffed to their arms) but would also revolutionize whole
>>areas of mathematical practice - there are a _lot_ of
>>NP-hard problems with real-world applications.
>
>Yeah, I was thinking this, too. Does anyone know how large
>the impact of this would be? Like, would the costs of Fed
>Ex, UPS, etc., go down substantially, because the way they
>flew their delivery routes became so much more efficient?
Not really. In most real-world situations, you don't need to
actually solve the NP-complete problem. Reasonable analysis
techniques quickly get you within a few percent of optimal,
and that's good enough for FedEx, etc. Phone company
routing may improve, but probably not by that much either.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
