Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de> writes:
As far as I know Boolean minimization has been one of the central themes of people doing circuit design from the beginning. I should be surprised if there are spectacular breakthroughs recently.
The general boolean minimization problem is hard. A specific boolean minimization problem may or may not be difficult to solve. Going back to our "safe execution" analogy; determining the runtime properties of an arbitrary computer program by examination of the code is impossible. Determining whether Bob's page of assembler will write all over the OS may be easy or hard, depending upon the code in question. Knapsack with power of two integers is trivial, general knapsack is NP-Complete, and random knapsack is not secure enough to be used as a strong cryptosystem. So given a specific problem, like DES, it is wrong to say that DES is combinatorially intractable because general satisfiability is hard or general boolean minimization is hard and DES has a polynomial reduction into such a problem, or that DES cannot be broken analytically because there have been no "spectacular breakthroughs" in the general case of these other problems. DES is a single instance, not a class of problems. It is of some constant degree of difficulty, and solving it, even under the image of a transformation into an instance of some other well-known problem, implies things only about the strength of DES, and not about the general case of other classes of problems which might be used to represent it. Breaking N-Round DES tells us only about the resistance of N-Round DES to whatever attack we are using, and does not imply intractable problems do not exist, or disclose some new sneak attack against all problems in NP. After this project is done, hard problems will still be hard. Hopefully what will have been demonstrated is that a small simple block cipher designed in the mid-70's is algebraically crunchable in a lot less time than an exhaustive search would take. An interesting result, but one which has no huge implications for the larger scheme of things. -- Sponsor the DES Analytic Crack Project http://www.cyberspace.org/~enoch/crakfaq.html