NTY compression proposal
Hi, It has been proposed to compress the keys from 100 cypherpunks down to a 64 character add in the NYT. Let's consider the math a moment to determine if this is realizable. Each key will require some sort of identifier, to make it simple lets assume 8 characters to identify the cypherpunks and 8 bytes to represent their key (64-bits). This mean that each line will contain 16 bytes. With a hundred entries that is 1600 bytes or 12800 bits. Now 64 characters of text in a newspaper represents approx. 64 6-bit characters (we can't use a full 8-bit because the paper doesn't normaly support that many characters in normal text). This provides us with 384 bits. The proposal leads to a requirement for an algorithm with an average compression factor of: 12800/384 or 33.33:1 with no data loss. That's a pretty hefty compression factor for average responce. Is there a loss-less algorithm which provides this level? ____________________________________________________________________ | | | The most powerful passion in life is not love or hate, | | but the desire to edit somebody elses words. | | | | Sign in Ed Barsis' office | | | | _____ The Armadillo Group | | ,::////;::-. Austin, Tx. USA | | /:'///// ``::>/|/ http://www.ssz.com/ | | .', |||| `/( e\ | | -====~~mm-'`-```-mm --'- Jim Choate | | ravage@ssz.com | | 512-451-7087 | |____________________________________________________________________|
At 8:30 PM -0600 1/18/98, Jim Choate wrote:
Hi,
It has been proposed to compress the keys from 100 cypherpunks down to a 64 character add in the NYT. Let's consider the math a moment to determine if this is realizable.
Each key will require some sort of identifier, to make it simple lets assume 8 characters to identify the cypherpunks and 8 bytes to represent their key (64-bits). This mean that each line will contain 16 bytes. With a hundred entries that is 1600 bytes or 12800 bits.
Now 64 characters of text in a newspaper represents approx. 64 6-bit characters (we can't use a full 8-bit because the paper doesn't normaly support that many characters in normal text). This provides us with 384 bits.
The proposal leads to a requirement for an algorithm with an average compression factor of:
12800/384 or 33.33:1 with no data loss.
That's a pretty hefty compression factor for average responce.
Is there a loss-less algorithm which provides this level?
Compression efficiency depends upon 1) the entropy of the input data, 2) the allowable losses and 3) finding an efficient algorithm to code for that entropy. For example, text rarely compress w/o loss beyond 4-5 to 1 (and 2-3 is more typical) using LZW (the defacto standard algorithm). Images have much more correlation in their data (and therfore can be compressed more readily), but even so lossless compression beyond 3-5 to 1 is uncommon (e.g., TIFF). JPG and other lossy algorithms need no apply. I think I'm on fairly firm ground assuming that key data entropy is very high and therefore little or no compressible is feasible. --Steve
At 8:30 PM -0600 1/18/98, Jim Choate wrote:
It has been proposed to compress the keys from 100 cypherpunks down to a 64 character add in the NYT.
Obviously you can't compress the keys themselves, and if you just take a short chunk of each key, you don't have enough entropy to be useful. But you can make a file with all the keys, hash the file, and post the hash and an URL for the file. That lets you use 128 or 160 bits of hash. That's plenty of room, and has full-strength security. If you want to do a 32-character message, it's tighter; using the usual 6-bit characters, 128 bits of hash takes 22 chars, and 160 bits takes 27. If you use the btoa encoding, which puts 4 bytes of binary into 5 bytes of ascii (if the 85 characters it uses can all be printed in the NYT's fonts), that's 20 for 128 or 25 for 160. So you have up to 12 characters left. So how short a URL can you do? With some cooperation from Vince, you can probably do 2 characters - "ai", which should retrieve http://ai/index.html (currently www.ai does.). I don't know if Netscape will let you retrieve this - I tried it, and got the index page for www.ai.com, using the Netscape "try adding .com" hack. (If you use the hack, "a" is shorter, but you'll need to give the IANA a good excuse for using the a.com reserved name. And keys.com is a company in the Florida Keys, but maybe they'd be friendly.) The shortest URL that really looks like an URL is probably www.ai . If the NYT insists on a phone number, that's 10-11 characters, so you'll need a shorter hash :-) Is 64 bits enough? It's long enough that it's hard to brute-force, and you probably don't need to worry about birthday attacks, though it's still uncomfortably short. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
participants (3)
-
Bill Stewart -
Jim Choate -
Steve Schear