As far as is known in the open community, David Scott formulated the idea. He
also implemented the first one-on-one compression algorithm.
He has vocally supported the idea over an extended period of time - in the face
of a large volume of fairly hostile criticism of the approach.
No non-trivial one-on-one compression algorithms predating David's discovery are
currently known.
We would love to have more information about any such algorithms.
One-on-one compression has been criticised because normal compression techniques can
offer some protection against chosen-plaintext attacks, while one-on-one compression
does not.
IF an attacker can choose plaintexts to be encyphered, this can
sometimes assist him in determining the internal workings of a cypher in ways
that a simple knowledge of plaintext would not allow.
Metaphorically speaking, the use of such a technique can be like using a narrow
and bright torch to observe obscure, dark corners of a cypher, which might
otherwise need large volumes of known plaintext to illuminate.
Alternatively, such a technique might allow the attacker to completely avoid the
parts of the cypher they had not yet found weaknesses in - and thus succeed in
finding a key.
The attacker would like to be able to choose the input to the cypher.
This is the output from the compressor.
If the attacker can choose the output from a one-on-one compressor, he can
usually find a decompressed plaintext that corresponds to it.
If an ordinary compressor is used, there is no guarantee that a decompressed
file corresponding to the compressed target file chosen by the attacker
exists.
It has been argued that this prevention of chosen plaintext attacks is
actually one of the purposes of compression. It provides a security
benefit that hinders attackers choose plaintexts.
In fact compression routines are not generally designed to hinder chosen-plaintext
attacks. Consequently they are not very effective at doing so.
Methods exist for preventing chosen plaintext attacks. These typically involve
appending a known volume of "random" information to the message, and applying
diffusion, so that the randomness is evenly distributed throuout the file.
Use of such techniques introduces security problems if the source of randomness
is less than perfectly random. It should be used with caution.
This technique is the best known method of preventing chosen-plaintext attacks.
It may be applied in conjunction with one-on-one compression techniques, just
as well as any other type.
The use of non-one-on-one compression to prevent known plaintext attacks, is a
primitive, dangerous technique, which we cannot recommend. Instead of adding
random information to the file - and having this information evenly
distributed, compression typically adds ordered information to the
file, with an uncertain distribution. This is not what is required.
In practice, defending against chosen plaintext attacks are not terribly
important anyway. For one thing, diffusion can easily prevent an attacker
controlling a plaintext, unless he can control every single last bit of it.
If the attacker can control the entire plaintext, the only method of
defense against chosen plaintexts involves adding information to the file.
Unless done extremely carefully, this is likely to introduce weaknesses
which cryptanalysis can target. Consequently, any such a "defense" only barely
qualifies as such.
No.
This is a generally desirable aim on security grounds, but typically needs a
source of "real" random numbers to be performed without introducing more
security problems than it solves.
If a secure source of "real" random numbers were available, a system
based on sending every message with an equal frequency would be more secure than
the systems under discussion here.
However, under some circumstances, it would also take up large quantities of
bandwidth - the very opposite of the effect of compressing.
Goodness knows.
Yes, but be careful.
If you use a signature that may be publicly verified, and the origin of your
message may be traced to you, and you sign your message before it's
encrypted - you may be providing attackers with a method of mechanically
rejecting the vast majority of keys.
On the other hand, if you sign on the outside of the message, there is some
possibility that a message may be faked.
Bearing these issues in mind when signing messages is recommended.
You can never have too much security.
Nobody knows if there are any modern block cyphers that will withstand
cryptanalytic attack for an extended period. Since the security of these systems
is not known with any certainty, additional security which hinders cryptanalysis
can only be welcome.
Attacks directly on the underlying cyphers are not the only way of compromising
a system's keyspace.
A bad random number generator behind the keys can allow the analyst to narrow
the keyspace to the point where brute force is possible.
Similarly keys may be partially obtained through noisy channels - such
as looking at keyboards through binoculars.