Quantum computing

[Robert J. Hansen]

Anders Breindahl wrote:
> Well. Yeah. But the thing that was and is fascinating about cryptography
> is that it -- assuming some model of computing -- is ``provable too
> hard'' to bypass. I'm worried that the future holds in store revolutions
> in computability that will shake those assumptions on ``too hard''.

I forget who said this, but it's my favorite quote about predicting the
future.  "The future never comes to us well-ordered."  It's always
punctuated with unpredictable advances and inexplicable delays.  You can
either obsess over the fact that crypto is a branch of mathematics, and
thus a human endeavor subject to the disordered-future rule, or you can
smile and shrug and say "well, we'll do the best with what we have, and
keep our eyes open for the future."

My best advice is to not worry about it.  :)

> This is in contrast to quantum cryptography, which, IINM, is provably

There is no such thing as quantum cryptography.  "Cryptography" is a
broad term encompassing a great many subjects, and we simply don't have
that for the quantum world.

Quantum key exchange is an interesting trick of physics.  But that's all
"quantum cryptography" is at this point--a simple key exchange
algorithm.  There are no quantum encryption algorithms, no quantum
signature schemes, no quantum hash functions.  Just quantum key
exchange... which is nowhere near as cool as people make it out to be.

It's an interesting parlor trick.  It's not anything new in the world of
crypto.

> Again, if I got it correctly, Rice' theorem came into a world where
> science was occupied with proving that this and that property was
> undecidable. Something ``like'' Rice' theorem would in a similar way
> alter the way that the scientific field is on.

[scratches head] Are you talking about the second Hilbert problem?  That
one generally goes to Gödel or Turing.  Rice's theorem is an interesting
bit of work with some deep consequences for computer science, but it's
not anywhere near as big of a shakeup as incompleteness.

> Both are convenient. However, the proofs that consolidate the security
> of programs like gnupg, assume some model of computation...

What proofs?  There are none.  There are just lines of reasoning which
we believe to have substantial weight, but nobody has delivered an
actual proof of security for any cipher or hash.  To do so you'd have to
prove P != NP, and that's one of the Holy Grails of CompSci.

Look at something as simple as RSA.  There are three major conjectures
that go into RSA.

1.  The RSA problem (RSAP) is equivalent to the integer
    factorization problem.

2.  The Integer Factorization Problem is not in P.

3.  P != NP.

None of those have been proven.  None.  We like to pretend that they
have been, we like to handwave them, but the reality is those
conjectures are unproven... and, in fact, #1 is probably false.

See Boneh and Venkatesan, "Breaking RSA May Be Easier than Factoring".

http://theory.stanford.edu/~dabo/papers/no_rsa_red.pdf

> So what I would love to see is some proof that -- even when faced with
> this new model of computing, ignoring its practical limitations --

Why?  Seriously.  Why?  By and large, cryptanalysis of intercepts is a
dead issue.  Nobody with half a brain does it.

According to the best information available, during the entire Cold War
the KGB and GRU were never able to break a single United States cipher
cleared for top-secret information.  That's not to say the KGB and GRU
weren't reading top-secret cables on a regular basis.  Instead of
cryptanalyzing the traffic, they just sent expensive hookers and good
bourbon to cipher clerks in the American embassy.

There are literally thousands of ways to skin this cat.  Focusing on
purely the mathematical aspect is very shortsighted.