On Tue, 15 Aug 2000, Timothy Brown wrote:
>recently than previously thought. Since cryptanalysis will become easier,
>my question was simply put - will cryptography become sufficiently more
>secure using principles inherent in quantum computing? I'm aware of most of
>the basics of what makes a cryptosystem secure, but how do the principles in
>quantum computing make cryptosystems more secure, and are there any
>references to secure cryptosystems theorized with the advent of quantum
>computing blah blah blah, you get the idea.
Hmmm. Actually, what quantum computing does is produce massive
implict parallelism. With a one-bit quantum computer, you can
try zero and one simultaneously. With a five-bit quantum computer,
you can test all values from zero to thirty-one simultaneously.
The crux of it seems to be that they've found a way to make the
eigenvectors behave, so that they can "collapse" on an eigenstate
that has a desired property. As far as crypto goes, this is bad.
If we can actually build a 2048-bit quantum computer, we would
be able to test all the 2048-bit keys of (insert favorite algorithm
here) simultaneously -- so cryptanalysis becomes a breeze. Our
assumptions about "not enough energy in the universe" based on
one electron-volt per NAND operation are invalid here because once
the eigenvectors are collapsed the only calculation that turns out
to have used energy from the universe is the one that produced the
"real" result -- the one the eigenstate was collapsed on. All the
rest are mere shadows, possibilities, ways the calculation *might*
have gone if it had failed, and use no energy.
However, quantum computation can't produce any speedup on a linear
calculation -- so encryption, where the key is known, doesn't get
any speedup.
All told, I'd have to say that the technology makes cryptography
in general LESS secure.
At the very least we need to start adding to our key lengths as
many bits as they can get from quantum computing. And unless
some barrier that keeps them from making an eigenvector with more
than N states emerges, this could turn into a chase where
you wind up needing to double the number of bits in a key every
18 months to keep something secure.
Ray
