Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26
John Kelsey (kelsey@plnet.net)
Fri, 5 Feb 1999 01:04:54 -0600
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Perry's Crypto List ## Date: 02/04/99 ##
Subject: Re: quantum cryptanalysis ]
Date: Wed, 03 Feb 1999 01:04:20 -0800
To: staym@accessdata.com, CodherPlunks@toad.com
From: Bill Stewart <bill.stewart@pobox.com>
Subject: Re: quantum cryptanalysis
Cc: cryptography@c2.net
>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?
Anyway, there's a fair amount of crypto that would keep
working even if all public-key methods became breakable.
Not only symmetric cryptography, but variations on Merkle's
puzzles (Bob Jenkins was discussing a bunch of mechanisms
for this a couple years ago on sci.crypt; I think Maurer had
a paper on a bunch of these methods in the last few years,
as well.) There's also quantum key distribution. In place
of signatures, there are a bunch of one-time signature
schemes, using Merkle's hash tree idea to great effect to
basically give you the ability to sign many documents
(hundreds or thousands) from one `public key,' based only on
using a collision-resistant hash function.
>Bill Stewart, bill.stewart@pobox.com
>PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
- --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQCUAwUBNrqX0yZv+/Ry/LrBAQHJkwP3X549ELte6U0GWm5torxQMHxwVyPhzq8d
evycxXCdbxTflzHNdFnI4eAl1Oo9CmcvxdH4TaMyeu1PCBKf1SB0hA7qI+MkBnko
kW+mXSMjzjb08W/EpWMGZt/LB6DnZsvnwiIIWnHWRb4pzaRLnbf+wURjZntNSuDn
1+R7/CLjWQ==
=25zg
-----END PGP SIGNATURE-----
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26