
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."