Quantum computing

[Robert J. Hansen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

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

I don't mean to sound flip, but as soon as you invent a hypercomputer  
I would love to revisit this issue with you.  For now, all our  
computational theoretic proofs will be limited by the the lambda  
calculus.  I don't mean to sound blunt there, but our current model  
of computation is extraordinarily robust, and there are very strong  
arguments that hypercomputation is both physically and mathematically  
impossible.  (If any problem in UNDECIDABLE can be solved by an  
oracle, then math goes from incomplete and inconsistent straight into  
pervasively self-contradictory and broken.  That's the rationale for  
hypercomputation being physically and mathematically impossible.)

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

Wikipedia is not an authoritative reference.

"Quantum cryptography" is a nice catchphrase.  I'm unaware of any  
respected authority in the field of crypto who takes the phrase  
seriously.

The phrase is used in nontechnical media, and in that environment its  
usage is probably defensible.  After all, people reading the  
newspaper don't want to be bothered with the details of what QKE is  
all about.  But we're trying to be precise here, and for that reason,  
let's not talk about quantum cryptography.  Let's be precise and talk  
about QKE.

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

The NSA was breaking the KGB's one-time pads.  Look into Project  
VENONA.  Soviet cipher clerks were making technical errors in using  
their one-time pads and the NSA was able to start reading their traffic.

So yeah, I'm not sure why you want flawless perfect proofs of  
security when reality shows that provably secure systems never are.

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

It's beyond the realm of mathematical cryptography, but not the field  
as a whole.

My day job involves security analysis of electronic voting machines  
for the National Science Foundation [*].  We spend far, far more time  
scrutinizing the human side of the cryptography than the mathematical  
side.  Probably an order of magnitude.




[*] I'm not speaking for the NSF here, obviously, I'm completely  
responsible for any errors I make, etc., etc.


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGKOavAAoJELcA9IL+r4EJ0cUIAKtWkRqLLXEfUfUzGmCTLXep
rsaxL2M3pBooQ9IIrnaTqKJxGkwyctYELZj94q+qcO+UZQ63HQGs7cslK7o1/Wyl
lN23aBlio7lABDT+jqyZYg2RWj2Urb6TKpYdTqsKiYM7MA2oxLpvIw9ear5s3Nxe
33uGKb5S3rZzjoYPgz35KXaqX7Qq9STbXFkiP70PsA8CazYXo3F9Tlqa+/n2/Wwf
Ti18Ga3DVjQoFx3uuU2U/+99gAQKrU9f6J6Q0N4WDFJO3Elst+7eCB89FEuoQYOl
iM2/bxTvJ+2/Uk022b++nlc7agtgMtJaVTsec7mbDqyaNinD5BR3jQgRl3oG7E8=
=p91A
-----END PGP SIGNATURE-----