From: Eugen Leitl (eugen@leitl.org)
Date: Sat Aug 31 2002 - 05:24:23 MDT
In regards to Robert's questions. I've got no clue either.
Somebody got a satanic Q mechanic?
---------- Forwarded message ----------
Date: Fri, 30 Aug 2002 10:27:30 -0700 (PDT)
From: bear <bear@sonic.net>
Cc: cryptography@wasabisystems.com
Subject: Re: Quantum computers inch closer?
On Sat, 17 Aug 2002, Perry E. Metzger wrote:
>
>[I don't know what to make of this story. Anyone have information? --Perry]
>
>Quantum computer called possible with today's tech
>http://www.eet.com/story/OEG20020806S0030
>
>MADISON, Wis. Researchers at the University of Wisconsin in
>Madison claim to have created the world's first successful simulation
>of a quantum-computer architecture that uses existing silicon
>fabrication techniques. By harnessing both vertical and horizontal
>tunneling through dual top and bottom gates, the architecture lays
>out interacting, 50-nanometer-square, single-electron quantum dots
>across a chip.
The papers I've been reading claim that feistel ciphers (such as
AES, DES, IDEA, etc) are fairly secure against QC.
But I don't see how this can be true in the case where the
opponent has a plaintext-ciphertext pair.
Because most feistel ciphers (and most other ciphers) can
be implemented as linearized hardware in a fairly small
(<1M) gate-and-wire count, and the "combinatorial explosion"
can be prevented if you have a plaintext-ciphertext pair,
I don't understand why you can't set up the entangled state
on the wires, gates, and key register, collapse the
eigenvector on the eigenstate that gives the known ciphertext
and plaintext, and read the key out of the collapsed state.
Similarly, if you can build a function that returns "1" if
a plausible plaintext is found and "0" otherwise, in hardware
gates, you have a specification for breaking feistel ciphers
using a Qchip from ciphertext only. And there are a lot of
functions that return "1" for plausible plaintext -- you can
check for a zipf distribution of bytes to detect natural-language
plaintext for example, or check for headers and binary-formatted
data to detect compressed files.
In this case you'd need to set up the wires-and-gates model
in the QC for two ciphertext blocks, each attached to an
identical plaintext-recognizer function and attached to the
same key register. Then you set up the entangled state,
and collapse the eigenvector on the eigenstate where the
ciphertext for block A and block B is produced, and the
plaintext recognizer for both block A and block B return
"1", and then you'd read the plaintext and key out of the
appropriate locations (dots?) in the qchip.
I figure two blocks because with keys about as long as blocks
there will be *some* key that produces just about any
pattern that will trigger your recognizer -- but with two
blocks running off the same key, a key that triggers the
recognizer in both blocks is highly unlikely unless it's
actually the correct key.
The papers I've been reading are concluding that these ciphers
are secure against Qchips in the unknown-plaintext case,
because for any round of the cipher there are a lot of
prefiguration states that could produce the same output.
keeping track of these prefiguration states introduces
additional "virtual" bits to the internal state that the
Qchip has to collapse, and of course each prefiguration
state was output by another round of the cipher so in turn
it produces its own family of prefiguration states, and
there's an exponential explosion in the number of qbits
needed in the eigenvector to keep track of them all.
But if you can design a plaintext-recognizer in gates,
I think that this argument is out the window. Even
with an unknown plaintext, if we assume that the plaintext
is english words (or a zipfile, or a GIF file, or whatever)
then we can design a plaintext recognizer that will be
highly reliable. And if we have the plaintext recognizer's
assumed output anchoring one end of the entangled model,
we don't need all the qbits devoted to the virtual bits
to keep track of prefiguration states.
I'm not a quantum physicist; I could be wrong here. In
fact, I'm probably wrong here. But can anyone explain
to me *why* I'm wrong here?
Bear
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:16:35 MST