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