From: "Timothy C. May" <tcmay@got.net>
Date: Mon, 25 Nov 1996 22:39:23 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: Provably "Secure" Crypto (was: IPG Algorithm Broken!)
In-Reply-To: <199611252028.MAA16855@vishnu.corsair.com>
Message-ID: <v03007800aec03fd247fd@[207.167.93.63]>
MIME-Version: 1.0
Content-Type: text/plain


At 10:30 PM -0500 11/25/96, Mark M. wrote:

>Matt Blaze did some work on NP-complete Feistel ciphers.  I don't know much
>about the details.  The paper is at ftp.research.att.com/dist/mab/turtle.ps

Matt described some of his (preliminary) results at an evening crypto
session at the Hackers Conference. The motivation was that secret key
ciphers, with the exception of one time pads, tend to be based on crufty,
ad hoc mechanisms, without any kind of provable security (again, with the
exception of true one time pads, which are of course known to be
information-theoretically secure).

It didn't seem to me that Matt had completed his work, and I don't believe
that any usable cipher has resulted (usable in the sense of being a
distibuted, ready to deploy cipher). He mentioned speeds comparable to DES.

Several people in this thread have commented on how nice it would be to
have a cipher provably as "good" as NP-complete problems are "hard"
(loosely speaking).

A noble goal. This was actually a motivation for the Founding Fathers of
Modern Cryptography, of course. Merkle, for example, believed that certain
"puzzle problems" could be used, with the security engendered by
NP-complete problems. The knapsack problem, generally, for example. It
turned out of course that the specifics of the proposed knapsack problem
implementations were not really fully equivalent to the general knapsack
problem, and were in fact breakable.

This is worth bearing in mind. Even if a problem is NP-complete, a
cryptosystem based on it may (and historically, _will_) often fail to be as
strong.

--Tim May


Just say "No" to "Big Brother Inside"
We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1398269     | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."