From: Scott Brickner <sjb@universe.digex.net>
Date: Mon, 23 Oct 95 16:34:41 PDT
To: cypherpunks@toad.com
Subject: A secure cryptosystem with a 40-bit key?
Message-ID: <199510232334.TAA11134@universe.digex.net>
MIME-Version: 1.0
Content-Type: text/plain


I've been reading a bit recently on constructed languages like
Esperanto.  I came across one that developed out of something called
"LOGLAN" that was published in Scientific American in the early
sixties.  The current active project is called "Lojban".  It has one
really curious property that gave me an idea for an interesting
symmetric-key cryptosystem.

All "native" Lojban words are of entirely predictable forms.  "Root"
words are all five characters containing three consonants and two
vowels in one of two patters (CCVCV and CVCCV).  "Structure" words have
four forms (VV, CV, CVV, and CV'V).  "Combining forms" have two forms
(CVC and CV'C).  All other words are not "native" words (being either
proper names or borrowed words).  The upshot of this is that there is a
fixed limit on the size of the Lojban dictionary of 249500 words (given
17 consonants and five vowels).

The grammar of the language is *so* regularized that they are able to
give a YACC description for it.

A message written entirely using native Lojban words can be encrypted
in a codebook fashion where the particular codebook to be used is a
permutation of the dictionary represented by an 40-bit number (18 bits
to permut the "root word" list, 10 bits for the "structure word" list,
and 12 bits for the "combining form" list).

This system has the interesting property that *any* plaintext with the
same grammatical structure is a potential encryption of a given
cyphertext.  This is similar to some more usual cryptosystems which
operate at the lexical level but which are designed to create this
effect, but has the curious side effect that it is *very* easy to
determine a false-key which makes the transmitted message say nearly
anything you want, thus making mandatory key escrow systems
irrelevant.

When you want to send the message "attack at dawn", you devise a
grammatically identical message, "party 'til you puke" (which is
grammatically identical in Lojban), generate a random key, as well as
the key representing a similar permutation, but with "attack" and
"party" exchanged, "puke" and "morning" exchanged, and so forth.
Transmit the message with the false key in the LEAF field (or report it
to your government-approved escrow agency) and government eavesdroppers
get the wrong message.  Other eavesdroppers get a grammatically
correct, but apparrently nonsensical message ("drink by brick").

There's still the problem of borrowed words and proper names, which
remain problems in any codebook approach, but represents a small
portion of the language, and the words which represent individual
letters are part of the "structure words" category, and could be sent
spelled-out.

This works well in Lojban because it never changes word forms based on
grammatical usage.  Most natural language declensions and conjugations
would make the encrypted message ungrammatical, and make it *much* more
difficult to determine a false key for the LEAF field.  The irregularity
of word forms makes the dictionary much more complicated, too.

Comments?