Re: Anyone seen the 'quantum cryptanalysis' thread?

At 12:11 PM 9/28/94 -0700, Timothy C. May wrote:

>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).

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.

This differs from the popular view that decryption would eventually win the
"war" with the encryption and devise a way of defeating *any* possible
code/cipher.  This "fact" was expressed in Edgar Rice Burroughs' Mars
stories where he said that the Martians didn't use codes much because they
were vulnerable.  See also Sneakers in which we have a "black box" decyption
device that can break any code.  Also the guy who confronted me at the
London conference last year and said "they broke the satellite movie coding
system so why can't they break PGP?"

I wonder where this idea comes from.

DCF

"Who was shocked, shocked by the end title sequence in Sneakers which
features a newsreader describing how good commie liberals like the Robert
Redford and Dan Ackroyd characters are using their decoding device to steal
money from the Republican National Committee and transfer it to Greenpeace
and all the usual suspects.  Looks like those guys don't believe in
democracy.  That sort of thing is worse than the Watergate break in."

[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

> 
> 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.
> 

I just wanted to point out that I'm not sure this is true.

I might be wrong; I'm a total newbie here.  However, my impression
was that it is *not* known that "anything in NP is solvable in
quantum polytime (BQP)".

I think it's been shown that, relative to a random oracle, it's not
true that NP is contained in BQP.  Then again, I'm told that oracle
results are often misleading and usually not worth a bean.  <shrug>
I don't know much about this stuff. :-(

[This oracle result is mentioned in Schor's paper.]

Hopefully someone more clueful than I will explain this stuff :-)

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu

> > 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.
 
> I just wanted to point out that I'm not sure this is true.
> 
> I might be wrong; I'm a total newbie here.  However, my impression
> was that it is *not* known that "anything in NP is solvable in
> quantum polytime (BQP)".

Well its quite possible that I am wrong since I didn't exactly have the
easiest time reading the papers on the subject. But this is my reasoning:

If you can create a machine that gives you a yes or no result (yes at least
one of the subset of possible inputs entered into the machine contains
the properties you are looking for [i.e. does not destructively interfere],
or no there aren't any) then you can construct an quantum computer that
tests for the property(s) the correct answer must have (in the case of
factoring, the machine will test whether or not inputs divide the modulus).
You can now repeatedly enter as inputs superpositions of inputs that include
precisely half of all inputs that might (given the information that has
already been gathered) be correct). You will now be able to mount a brute
force attack searching through 2^n possibilities in order n time. It should
be possible to nest these machines (although admitedly this does nasty
things to the physical complexity of the quantum computer. It doesn't
seem like the complexity would grow exponentially in the case of nesting
[in fact it seems like it would go quadratically with the nesting level]
but I'd have to think about it some more before I could claim to be confident
of that.) thus allowing us to reduce any problem of time complexity
e^X(n) (where X is either a polynomial in n or of the form e^X(n) [this
goes on recursively]) to a problem of polynomial time complexity.

JWS

solman@MIT.EDU writes
> 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.

As far as is know, quantum computers cannot solve NP complete problems
in polynomial time.

They can solve some problems (such as factoring) that classical
computers cannot solve in polynomial time.

-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com

> Duncan Frissel writes

> This differs from the popular view that decryption would eventually win the
> "war" with the encryption and devise a way of defeating *any* possible
> code/cipher.  This "fact" was expressed in Edgar Rice Burroughs' Mars
> stories where he said that the Martians didn't use codes much because they
> were vulnerable.  See also Sneakers in which we have a "black box" decyption
> device that can break any code.  Also the guy who confronted me at the
> London conference last year and said "they broke the satellite movie coding
> system so why can't they break PGP?"
> 
> I wonder where this idea comes from.
> 

	Casually looking at the history of the past 100 years or so of
cryptanalysis, particularly what has been recently revealed recently
about US/British triumphs in World War II, shows a number of startling
successes against what were thought (and even now seem to ordinary
minds) to be intractable ciphers.  It is not very hard to see why
popular mythology, which usually lags the cutting edge of science by at
least several years and even sometimes several decades emphasizes
decryption. After all, decryption seems to have been winning the last
time we were allowed to have a look.

	It is also true that a quirk of human nature that probably
has a lot to do with the origin of religion tends to mythologize to
vast, even epic status those who can do something that ordinary people
can't.  And this hero/god dieification often involves the myth of
unlimited power, which in the case of crypto means the ability to
break any cipher.

	It will take a while before appreciation of the fundemental
revolution represented by number theory based ciphers sinks in.  Even
the simple understanding that there exist unbreakable ciphers right now
that anyone with a floppy disk drive can implement is too advanced to
sink in very far. 

	But probably the worst myth is the notion that most practical crypto
systems were actually intended by their creators to be unbreakable.   

	And of course nobody out there understands that satellite TV
pirates have yet to break any cipher at all (at least as far as I know
as someone who follows this technology).   All the current triumphs have
been based on exploiting holes (mostly involving cloning) in the
key distribution and management in an environment where your enemy
both necessarily has the complete cipher device and several copies
of known to work keys.  

						Dave Emery

Duncan Frissell and Dave Emery have commented on the popular notion
that all codes and ciphers will "eventually" be broken. 

Dave Emery wrote:

> 	Casually looking at the history of the past 100 years or so of
> cryptanalysis, particularly what has been recently revealed recently
> about US/British triumphs in World War II, shows a number of startling
> successes against what were thought (and even now seem to ordinary
> minds) to be intractable ciphers.  It is not very hard to see why
> popular mythology, which usually lags the cutting edge of science by at
> least several years and even sometimes several decades emphasizes
> decryption. After all, decryption seems to have been winning the last
> time we were allowed to have a look.

On the other hand, Bamford pointed out in 1982 (in "The Puzzle
Palace") that no significant Soviet cipher had been broken _directly_
for at least a decade, as near as he and other experts could tell
(there are clearly uncertainties in what the NSA was able to do, but
this wa Bamford's best estimate).

Ditto for the Soviets not having broken U.S. ciphers in at least as
long a time.

What code and cipher breaking had occurred had generally happened
through HUMINT sources, as with the Walker spy ring (which sold old
code books, allowing earlier traffic to be reconstructed). Black bag
jobs, bugging of buildings, etc. And I have no idea what crypto
material Aldrich Ames transferred.

> 	It will take a while before appreciation of the fundemental
> revolution represented by number theory based ciphers sinks in.  Even
> the simple understanding that there exist unbreakable ciphers right now
> that anyone with a floppy disk drive can implement is too advanced to
> sink in very far. 

I agree. Even Tom Clancy mythologizes crypto and usually gets it wrong.

...
> as someone who follows this technology).   All the current triumphs have
> been based on exploiting holes (mostly involving cloning) in the
> key distribution and management in an environment where your enemy
> both necessarily has the complete cipher device and several copies
> of known to work keys.  

Exactly.

In fact, at the last physical Cypherpunks meeting I arrived a few
minutes late, in the midst of a debate about whether noise sources
from audio inputs were "random enough" to defy cryptanalysis by the
NSA.

After listening for a while I had to speak up: In the history of
modern cryptanalysis is there _any_ evidence that a single message has
been broken because of something like this?

I speculated that any slight reductions of entropy, thus allowing
slight increases in the ability to predict the bits, are dwarfed by
many orders of magnitude by more practical concerns. For example, the
proliferation of keystroke capture utilities which capture and store
all keystrokes entered for later retrieval.

(I acknowledge the importance of high entropy noise sources, I just
question the nit-picking about it when such much more tractable
attacks exist.)

--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