From: Bill Stewart <stewarts@ix.netcom.com>
Date: Mon, 30 Sep 1996 14:18:56 +0800
To: cypherpunks@toad.com
Subject: Re: [CRYPTO] Does any body know anything about this?
Message-ID: <199609300436.VAA08532@netcomsv.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At 02:38 PM 9/29/96 -0700, some nobody wrote:
>Is this just more snakeoil or is this real?

Neither Matt Blaze nor Ross Anderson are particularly on the
pro-snake-oil side....  Sounds like an interesting talk and I'd
enjoy being there for a variety of reasons, including being able
to time-travel back to Last Monday :-)  One difference between
snake oil salesmen and mathematical cryptographers is that
the latter talk about what they're doing, why it's as strong
as it is, and how it relates back to other known hard problems
or attack techniques.  If this is sufficiently hard, cool.

Most of the symmetric-key attacks these days are based on being
sufficiently messy to be hard to attack, and on resisting known
attacks, but there's no particular way to prove how hard they are -
you can just show that they're messier than any currently known
techniques can untangle.  On the other hand, the experience with
most public-key techniques is that it's hard to adapt NP-hard 
problems to crypto in ways that don't introduce special forms
that can fall apart when handled right - the knapsack problem
was a good example.  Factoring and discrete-log still appear to
be hard problems, but it would be nice to have other known-hard
public-key systems.  It would also be nice to have private-key
systems that use NP-hard problems in strong ways, especially if
it doesn't make them appallingly slow :-)



>TITLE:          SYMMETRIC-KEY CIPHERS BASED ON HARD PROBLEMS
>A useful principle in cipher design is to reduce or at least relate
>closely the cryptanalysis of the cipher to some long-studied problem
>that is believed to be difficult.  Most public-key ciphers follow this
>principle fairly closely (e.g., RSA is at least similar to factoring).
>Modern symmetric-key ciphers, on the other hand, can rarely be reduced
>in this way and so are frequently designed specifically to resist the
>various known cryptanalytic attacks.  In this informal talk, we examine
>a simple cipher primitive, based on Feistel networks, for which recovery
>of its internal state given its inputs and outputs is NP-complete.  We
>outline simple and efficient block- and stream- cipher constructions
>based on this primitive.

#			Thanks;  Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# <A HREF="http://idiom.com/~wcs"> 	
# You can get PGP software outside the US at ftp.ox.ac.uk/pub/crypto