From: solman@MIT.EDU
Date: Mon, 3 Oct 94 01:17:09 PDT
To: frissell@panix.com (Duncan Frissell)
Subject: Re: Anyone seen the 'quantum cryptanalysis' thread?
In-Reply-To: <199409291241.AA11195@panix.com>
Message-ID: <9410030816.AA25214@ua.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


[sorry if this is way out of it, I haven't had time to keep up with my
c-punks mail lattely]

Duncan writes
> It's easier to make an omlette out of eggs than to make eggs out of an
> omlette so encryption should remain well ahead of decryption.

As I'm sure somebody else has pointed out somewhere along this thread, the
ability to simultaneously analyze a superposition of an arbitrarilly large
subset of all possible imputs (as our theoretical quantum cryptanalytic
device might) implies to ability to solve, in polynomial time, any
exponential time problem.

[Its easy to consider a device which, given a superposition of a subset of
all numbers less than 2^n, delivers as output a confirmation or denial
that one of the numbers in the subset is a factor of the input modulus.
Such a device can factor in order n time complexity simply by playing higher
lower games and guessing one bit at a time] 

I want to take issue Duncan's analogy here however. It starts off well:

> "It's easier to make an omlette out of eggs than to make eggs out of an
> omlette"

This is like saying entropy always wins, which it does. It will always be
easier to take apart and destroy than to create. Then he continues:

> So encryption should remain well ahead of decryption

Which process is increasing order and which process is increasing entropy?

I think an encrypted message is a highly ordered construct. In its natural
state, information can be read by everyone. Upon this state encryption
imposes order. It allows a specific subset of all entities to read the
information. In the total cyberspatial system, none of the original
information has been lost, yet new information has been added. 

I look at encryption as the tool that will allow us to build up an orderly
society within the natural anarchy of cyberspace. Encryption is an artifact
of order.

And as such I would expect science to eventually uncover a mechanism that
makes it easier to breakdown this order than to create it in the first
place.

I suppose it is plausible that there exists a class of Quantum-Hard problems,
but it is difficult for me to conceptualize such a class of problems. It
seems like quantum computation is capable of decreasing the time complexity
 of any problem to its logarithm an arbitrarilly large number of times.
[Not that I believe for one moment that it is likely that quantum
cryptanalytic machines will be developed that are sufficiently fault
tolerant (if the term can even be applied to a system like this) to
overcome the coupling between the quantum computer and the surrounding
environment in the next couple of decades.]

Cheers,

Jason W. Solinsky