Quantum computing
Robert J. Hansen
rjh at sixdemonbag.org
Fri Apr 20 18:13:35 CEST 2007
-----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-----
More information about the Gnupg-users
mailing list