Comments/summary on unicity discussion

[Joseph Ashwood]

----- Original Message -----
From: "Joshua Hill" <josh-crypto at untruth.org>
Subject: Re: Comments/summary on unicity discussion


> It doesn't deal with plaintext, just ciphertext.  In fact, unicity
> distance is only valid for a ciphertext only attack.  Once you get a
> known plaintext/ciphertext pair, a high unicity distance works against
> you (more on this later). In addition, it is isn't certain that after
> observing the requisite unicity distance number of ciphertext units that
> you can uniquely determine the key, it is merely very likely.

There appears to be an error in there. The Unicity Distance has a very
strong correlation with the uncertainty of the plaintext (entropy per
message). By having access to the plaintext/ciphertext pair (often it takes
multiple pairs), this removes all uncertainty as to the plaintext, this
changes the unicity distance calculation by making the unicity distance as
short as possible, which would make "Once you get a known
plaintext/ciphertext pair, a high unicity distance works against you"
Seem more than a little odd as a statement.

On K complexity, while K complexity offers a convenient, if somewhat
inaccurate, upperbound of the entropy, that is basically where the
relationship ends. Permit me to give the basic example. Which of these
strings has higher entropy:
kevsnblawtrlnbatkb
kevsnblawtrlnbatkb
One was created by slapping my hands on the keyboard, and so contains some
entropy, the other was created through copy and paste, and so contains none.
However the K complexity of the two is identical. The portion of the
equation you are forgetting is that the key to the pRNG may itself be
compressible. This leads to somewhat of a logic loop, but at the end of it
is the absolute smallest representation, as a compression of a given
language (the only sense in which this makes sense).
                Joseph Ashwood


Trust Laboratories
http://www.trustlaboratories.com


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com