From: catalyst@netcom.com (Scott Collins)
Date: Thu, 20 May 93 00:43:40 PDT
To: cypherpunks@toad.com
Subject: Re: false positives
Message-ID: <9305200743.AA02030@netcom.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


>Has anyone tried to create a strong encryption algorithm that cannot
>be broken by brute force?
    ^^^^^^

Brute force = exhaustive search.  Therefore, if there is a solution, and
the search terminates, the answer will be found.  Your point was, can an
encryption system be designed such that an exhaustive search yields
multiple equally good, different (preferably contradictory) decryptions,
for any given encrypted message.

In "Communications Theory of Secrecy Systems", Bell Systems Technical
Journal, Vol 28, pp. 656-715, Shannon measures the efficacy of an
encryption system by the average number of plaintext messages that map to
an arbitrary cyphertext (via different keys).  Later, Hellman (in "An
Extension of the Shannon Theory Approach to Cryptography", IEEE
Transactions on Information Theory, vol 23, No. 3, pp. 289-284) emphasized
Shannon's point about using compression with encryption so that decryption
will yield more false positives.  Ross Williams discusses this in his book:
"Adaptive Data Compression".

Note the limited definition of meaningful in these papers as 'makes words'.
 Given sufficient context, a correct decryption would not be able to hide
in a forest of 'meaningul' false positives.  (e.g. "Hmmmm, do you think
it's 'cats often enjoy', or 'be ready by tuesday').

Of course, a one time pad affords a very large space of meaningful (much
more meaningful than just 'makes words') decryptions for each encryption,
hence its information-theoretically perfect security.

A system which provides arbitrary mappings at the message level and no
derivable component context enjoys this property as well.  (e.g. a code
book: 1-->be ready by tuesday; 2-->expect a guest.  What does the message
'1' mean?  It can mean any message in the world, exactly as (when using a
one time pad) the 17th character might mean any character in the world.)

So in answer to your question: yes, a one time pad is just such a system.

        -- Scott

+ Scott Collins       + "Few people realize what           +
+ catalyst@netcom.com |  tremendous power there is in one  |
                      +  of these things." -- Willy Wonka  +