Re: second order homophonic substitution

[wcs@anchor.ho.att.com (Bill_Stewart_HOY002_1305)]

You don't need to do a full table of 2^16 bytes to handle real data -
you could use 4-bit nibbles if you wanted, so each byte of steganotext has
4 bits of real data (which is cyphertext) and 4 bits of fake data.
The steganotext is still twice the size of the plaintext, though.

However, your key doesn't need to contain the whole table - you can use
a much shorter key to describe a tour through the table or other method of 
filling it, where the key is the seed to a PRNG, which doesn't even need
to be cryptographically strong, just decently random.  This approach lets you 
use either 4x4 tables for compactness or 8x8 tables for efficiency.
One way to make the decryption algorithm not reveal its purpose is to have
one of the key parameters be a bitmask showing which 4 or 8 bits
to keep out of the 8 or 16 output bits from the table.
The (fake) encryption algorithm should have some feature
to generate random bits using a hard-to-reproduce PRNG (e.g. the middle
4 or 8 bits of a 64-bit-wide PRNG), or something else obfuscatory,
allowing the real cyphertext to be patched in through a less visible program,
or through an obvious-functionality program like a one-time-pad xor.
(Perhaps the PRNG could have parameters that, given all-zero input,
produces all-zero output, or something similar that lets you use the
same program for real and fake.)

Now, the Bad Guys, if they're any good, will notice the 2:1 compression,
and may suspect something's up, since they're archiving this posting :-).
You can also do ratios other than 2:1, if you're willing to waste space.
However, the algorithm does look like something an amateur would come up
with to be the latest "nobody can crack my new complicated cypher",
and it's tough to prove otherwise, since the real cyphertext is just
raw bits unless you have the keys...   

Its effectiveness depends on whether they know that I know that they know that...
and on whether they ask you in court, under penalties of perjury,
whether this is the only key to the cypher, and whether you're really obligated
to tell the whole truth in addition to telling them the truth and nothing
but the truth.  But truth is pretty complicated stuff, and once you start
explaining the mathematical details of the PRNGs you use and how you know
they're good stuff, and how quantum mechanics relates to the ability to
send keys without eavesdropping, and the effects of quantum on epistemology,
and what Knuth was talking about on page N of volume 2, they'll probably give
up and decide it's irrelevant technicalities...

	said Bill, increasingly verbosely