Quantum computing

[Anders Breindahl]

[ Please interrupt if this is getting too off-topic. ]

On 200704200441, Robert J. Hansen wrote:
> 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.  :)

Yeah, again. I completely agree on the practical aspect of it, but would
nevertheless like to see proofs of complexity that weren't dependent on
the current models of computations.

However, then you'll just invent the hardware-coming-in-3050 model, that
does all its calculations by solving RSA. Or whatever I aim to defend.

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

I was referring to the subject that is mentioned on the Wikipedia page:
http://en.wikipedia.org/wiki/Quantum_cryptography

Saying that ``there is no such thing'' seems harsh and as if you ignore
reality. The European Union put its hopes up for implementing a
``quantum cryptography'' network of communications. That sort of makes
the term real in itself.

Link to that statement in Danish:
http://ing.dk/apps/pbcs.dll/article?AID=/20040826/IT/108270093

That doesn't mean that it (quantum cryptography) by any means is
practical. It would seem from Werner's forward that it's so deeply
buried in its own infancy or -- more seriously -- inherent
technicalities, that it won't find any practical use ever.

However, quantum cryptography does have that nice inherent benefit, that
it _can't_ be eavesdropped, according to said article. That is, after
authenticity has been established and the line has been paid for:
  
  http://en.wikipedia.org/wiki/Quantum_cryptography#Attacks:
  In Quantum Cryptography, traditional man-in-the-middle attacks are
  impossible due to the Observer Effect. If Mallory attempts to
  intercept the stream of photons, he will inevitably alter them. He
  cannot re-emit the photons to Bob correctly, since his measurement has
  destroyed information about the photon's full state and correlations.

I suppose that this is the feature that got the European Union's
attention.

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

Then take that for an example. My point is that proofs can alter the
heading of a scientific field in the time it takes to they're generally
accepted.

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

I was merely assuming that such proofs existed. But, when I think again,
formal proofs of correctness are hard to get, too, so why would
common cryptography be provable?

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

It's the you-don't-know-that-question. *Probably*, it's secure, and all
data supports it, but it hasn't been proved to be secure. Therefore,
it's restricted to being ``probably'' or ``very probably'' secure.
Right?

Contrary to one time pads, which are provably secure -- where ``secure''
means ``unbreakable from theoretical standpoint, but with no thought
given to practical limits''.

I was told that one time pads were also used by the KGB, by the way.
Mini-books whose pages were to be burned after using.

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

Though it sounds sweet, it's beyond the scope of cryptography to ensure
such protection (to some extent, though, security should limit room for
personnel ``breakage'').

And you're right. Nobody needs a formal proof for any of this, since it
probably (in lack of a better word) is good/secure/strong enough. 

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

Or rather, it's very unproductive.

Many a problem stands open in mathematics and scientists spend their
lives on solving or proving them. However, progress is overall slow, and
computer science's overall more pragmatic approach gives *results*. And
many of us are grateful for that.

But the attractive part of focusing on the mathematical aspects are that
-- if provable -- it could give some guarantee ( > reassurance)
of the unbreakability of the ciphers out there.

You may not be interested in that, but I am. I too however neither will
end up a mathematician whose life is focused on solving some single
problem.

But I would be interested in the result. I could pick the cipher that
provably could withstand any battering thinkable over the cipher that
perhaps couldn't.


Regards, skrewz.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : /pipermail/attachments/20070420/79511e43/attachment-0001.pgp