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
bram (bram@gawth.com)
Fri, 5 Feb 1999 11:13:17 -0800 (PST)
On Fri, 5 Feb 1999, John Kelsey wrote:
> 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.
I have a theory that no matter what computing machine is available, as
long as the same machine is available to both the encrypter and the
cracker, the cracker wins (barring non-turing complete machinery, of
course.)
For example, say that there was an oracle which you could ask 'Does this
turing machine ever halt?' (quantum cryptography can't do that.) A cracker
with such a machine could trivially crack any code encrypted using
standard methods with a published algorithm. If, however, the encrypter
also had such a machine, he could devise an encryption algorithm which
required queries to the oracle to work, and as long as the algorithm
required, say, quadratically many queries to the oracle to encrypt but
exponentially many queries to the oracle to crack, the encrypter wins.
No, I don't have any clue how an algorithm like that might work.
-Bram
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26