Re: Compression and crypto

David Wagner wrote:
Douglas A. Gwyn wrote:
Christian Siebert wrote:
What I want to say is that it would NOT be impossible to construct a
bijective compressor for grammatically correct texts (for a fixed
language). This would also mean that any (even random) input could
always be decompressed into a grammatically correct text. ...
It doesn't even have to be perfect, just so that a sufficient
fraction of bogus decodings would sneak past the bogosity detector.
The fraction doesn't have to be very large to render the search
impractical.
Well, yes, it does. That fraction has to be pretty close to 100% if
you want to make exhaustive keysearch much harder. ...

My analysis is completely different from yours.
For one thing, I don't assume that you can obtain 1000
ciphertexts that have the same key. And even if you could,
having to manually evaluate some 2^50 candidates that
passed the bogosity detector would certainly be infeasible.

Anyway, this whole discussion has the flavor of solving a non-problem.
The benefits claimed for pre-compression (so far) have all been about
increasing the workfactor of exhaustive keysearch. But in a modern
well-designed cryptosystem, the chances that exhaustive keysearch is the
easiest attack on your system are vanishingly small. Perhaps 20 years
ago exhaustive keysearch was worth worrying about, but since then we
have completely solved that problem (namely, by increasing key lengths
enough to make exhaustive keysearch completely impractical). It seems
very peculiar to me to devote so much effort to trying to defend against
a non-threat.

The discussion was prolonged by trying to correct some
misconceptions that others were promulgating. The
primary cryptosecurity value of any form of compression,
bijective or not, lies in its removal of redundancy.

The practical concern relative to brute-force key search
is that some day in the not too distant future that may
become a more practical method of attack, due to advent
of quantum computers that would be able to provide a
tremendous amount of parallelism, not readily defeatable
by scaling up the key size.
.

Relevant Pages

  • Re: Compression and crypto
    ... always be decompressed into a grammatically correct text. ... fraction of bogus decodings would sneak past the bogosity detector. ... you want to make exhaustive keysearch much harder. ... Suppose we have 100 ciphertexts. ...
    (sci.crypt)
  • Re: Compression and crypto
    ... bijective compressor for grammatically correct texts (for a fixed ... always be decompressed into a grammatically correct text. ... The man who is always worrying about whether or not his soul would be ...
    (sci.crypt)
Loading