When the news broke earlier this month that
the U.S. government is trying to build a super-fast quantum computer, reports suggested the
demise of private information as we know it.
“[T]he National Security Agency is racing to
build a computer that could break nearly every
kind of encryption used to protect banking,
medical, business and government records
around the world,” The Washington Post said
in a front-page story on 3 January.
The end may not be so nigh, however.
“People are not actually shaking in their
shoes so much,” says Lance Fortnow, a
computer scientist and blogger at the Georgia
Institute of Technology (Georgia Tech) in
Atlanta. The $80 million National Security
Agency (NSA) initiative came to light in
documents leaked by former NSA contractor
Edward Snowden, but experts say they’re not
surprised that NSA is working on quantum
computing. “It would be shocking if they
weren’t,” Fortnow says. But a full-fledged
quantum computer is likely decades away.
More important, even if a quantum code
cracker can be built, it might be defeated by
encryption algorithms already in the works—
or by another technology, called quantum key
distribution, that relies on quantum mechanics
itself for security. “In the future, we believe
our adversaries will have better computers
and better algorithms, but they won’t be able
to break the laws of physics,” says Richard
Hughes, a physicist at Los Alamos National
Laboratory in New Mexico.
Which raises a practical question: If such
countermeasures rob a quantum computer of
its widely perceived killer app, will anybody
put up the huge sums of money likely needed
to make a quantum computer a reality?
Be it data file or love letter, information crosses
the Internet in the form of numbers, written in
binary strings of 0s and 1s. Cryptography is the mathematics of
scrambling a numerical message
so that it can be unscrambled only
by the intended recipient, at least
in a reasonable amount of time. A
quantum computer could crack
current algorithms for so-called
asymmetric or public key encryption, the
technique typically used to begin secure Internet communications.
In such schemes, a sender, Alice, scrambles
a message to the recipient, Bob, using a
numerical key that Bob makes public. Bob
also possesses a private key that mates with
the public key to unscramble the message.
In principle, an eavesdropper, Eve, could
deduce the private key from the public key. In
practice, that problem is so hard it would take
nearly forever to solve.
For example, in the widely used RSA
algorithm, the public key is a huge number that
factors into two prime numbers known only to
Bob. To encode a message, Alice multiplies
the binary message by itself a number of
times—that is, raises it to a power—that’s
based on those factors and specified by Bob.
She divides the result by the public key and
takes the remainder—an operation called
modding out. (For example, 33 mod 15 equals
3.) She sends the remainder to Bob as the
coded message. To unscramble the message,
Bob raises it to another power that depends on
the two primes. That power is his private key.
He then mods out by the public key. Voilà! The
original message pops out.
Confusing? It’s supposed to be. But
basically it’s as if Alice has a counter that
resembles a car’s odometer, except that it
rolls over to zero when the count equals the
public key. She dials in the original message
and scrambles it by advancing the counter
according to a certain recipe, letting the
counter roll over however many times it will.
Bob then advances the counter in a way that
makes the original message roll around again.
The algorithm is secure because, without
knowing how many times the counter has
rolled over, Eve can’t readily reverse Alice’s
manipulations. She may have a better shot at
figuring out Bob’s private key—the power to
which he’s going to raise the coded message.
But that requires factoring the public key. As
the key is huge—typically 2048 bits—that
task would overwhelm an ordinary computer.
But it would be easy for a quantum
computer. An ordinary computer employs
“bits” that can be set to either 0 or 1; a
quantum computer would use “qubits”—
perhaps spinning ions or little loops of
superconductor—that could be set to 0, 1,
or, thanks to the weirdness of
quantum mechanics, 0 and 1 at the
same time. The qubits’ state would
be described by quantum waves
that can interfere to reinforce or
cancel one another, making new
algorithms possible. In 1994,
Peter Shor, a computer scientist
at the Massachusetts Institute of Technology
(MIT) in Cambridge, reported an algorithm
that uses such “quantum interference” to
factor huge numbers in far fewer steps
than an ordinary computer needs. Shor’s
algorithm could crack not just RSA, but all
current public key schemes.
Quantum Spy Games
Someday a quantum computer may unlock all our secrets—if it isn’t first stymied by
view with Adrian
Cho ( http://scim.ag/