Misunderstanding about Quantum X

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Tue Jan 04 2005 - 21:09:17 CST

On Jan 4, 2005, at 4:48 PM, Nils Paz wrote:
> Quantum cryptography allows for absolutely secure communication as
> well as a means for breaking current cryptographic communication
> schemes

Ummm... not really.

There's apparently a bunch of misunderstanding about what quantum
computing and quantum cryptography are. The really short answer is
that neither is relevant to the OVCs issues. A slightly longer answer
follows:

(1) Quantum cryptography normally refers to use of quantum phase states
(such as polarization of photons) over a closed channel. By the
Schroedinger principle, you cannot measure such states without changing
them. The way this works for cryptography is it provides an absolute
assurance of detecting an eavesdropper who tries to tap a channel... if
anyone is listening in, they automatically change the signal itself, in
detectable ways.

Generally, even in quantum cryptography, the message itself is also
encrypted by conventional means (AES, IDEA, 3DES, stuff like that).
The only thing the quantum channel adds is a guarantee of intrusion
detection.

In any case, this is strictly a closed-channel point-to-point
technique. It is completely irrelevant to "store and forward"
encrypted messages (i.e. all the data that goes into or comes out of an
OVC voting system), digital signatures, etc. Quantum cryptography
exists right now; in fact, it's commercially available, and in limited
practical use.

(2) Quantum computing is a completely different thing, and is still at
the level of "theoretically possible." FWIW, you can search for my
name along with the phrase, and find a fairly good introductory article
on the topic (but lots of other people have written intros too). The
idea there is that (in principle) you can utilize the superposition of
many "possible states" that you see at a quantum level to resolve (in
polynomial time) SOME problems that are not polynomial-time computable
by deterministic state machines.

Or to put it really simply, a problem that might take 2^100 steps on a
traditional digital computer, might take only 100 steps on a quantum
computer. The first number is way too big to finish in reasonable time
frames (like while humanity still exists). The latter is moderate
(though how long each step takes is still somewhat relevant). But it
is definitely only SOME problems that are amenable to efficiency on
quantum computers.

Factoring is PROBABLY one of the problems that quantum computing makes
tractable. Which means that RSA-based public-key systems are
potentially weakened. Traditional multi-round "diffuse and permute"
symmetric encryptions and cryptographic hashes are not going to be
affected at all by quantum computing. In other words, even if quantum
computers become real, SHA-1, and AES become no less strong than they
are now (which isn't to say that specific mathematical analysis of
individual algorithms won't reveal weaknesses... MD5, for example,
recently had a significant attack discovered).

But in any case, it is far from clear that large scale quantum
computers will ever become real. They might; but they might not.
There are a whole lot of new physical techniques that will be necessary
before it happens. To give you a sense: the most elaborate quantum
computer built so far was specially constructed (single purpose) to be
able to factor the number 6. This took about a decade of work to
accomplish. The fact that someone did this is -interesting-, but it's
not exactly an *attack* on existing cryptography just yet. And whether
this can scale in stable systems is not obvious.

Yours, David...

_______________________________________________
OVC discuss mailing lists
Send requests to subscribe or unsubscribe to arthur@openvotingconsortium.org
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Sat Jan 7 22:28:56 2006

This archive was generated by hypermail 2.1.8 : Sat Jan 07 2006 - 22:28:59 CST