Dear Travis, simplification can be reduced to elimination, which is indeed intractable in the general case (for real-sized problems). (I am assuming that you need to simplify a "big" system; however if you only want to simplify a small SBox, then brute forcing might do.). The standard citation on itnractability is [E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., 46:305–329, 1982.] or Philippon et al.'s article. A more comprehensive approach can be found in [D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo. "The hardness of polynomial equation solving". Found. Comput. Math. 3 (2003).]; see also the citations in their Intro). The intractability of elimination is well known at least since Grete Hermann (http://en.wikipedia.org/wiki/Grete_Hermann), and most probably since the end of the 19th century.
In my opinion "simplification" is a "means" and not an end, and indeed a very intractable mean. On the other hand, form your email I gather that your end is to solve these equations. In polynomial equation solving, special cases are what counts. There is a lot of debate on what are good options for elimination, today there are different approaches presenting families of algorithms that are efficient on certain "problem instances". Briefly I would classify the options as: 1-rewriting techniques (ie Groebner bases), 2-path-following techniques (e.g., [L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York Berlin Heidelberg, 1998.], [B. Huber, B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation 64 (112) (1995).]), 3-numeric techniques (e.g., [W. Rheinboldt, Methods for solving systems of nonlinear equations, vol. 70 of CBMS-NSF Regional Conf. Series in Appl. Math., SIAM, Philadelphia, 1998.), 4-an algorithms family based on flat deformations (e.g., [M. Giusti, K. Haegele, J. Heintz, J.E. Morais, J.L. Monta~na, L.M. Pardo, Lower bounds for Diophantine approximation, J. Pure Appl. Algebra 117,118 (1997)] and its predecessors; see http://tera.medicis.polytechnique.fr) There are also many ad hoc constructions (e.g., in crypto) that can be used on very specific problems. I think this is all. I might be unwittingly omitting some other option. Im sorry if I am. I can only speak for the latter technique (4), in which I have contributed; in fact, together with other coauthors we will be releasing a paper which attacks the problem of polynomial equation solving as applied to public-key schemes based on polynomial equations. I have not analyzed block ciphers, which yeild higher degree equations (as compared to the quadratic equations of typical public-key schemes). I hope that this helps, and feel free to mail me on any other questions. Best, Ariel Travis H. wrote: > Does anyone have any references on how one would go about creating > manipulating the boolean equations that govern symmetric ciphers? > > I know that most of the time ciphers describe an algorithm, often > using tables (S-boxes and E-tables) in lieu of providing equations, > and I'm wondering how one goes about generating the equations for each > bit of the output. > > One thing I've always been curious about is the minimum amount of work > (in terms of a primitive boolean gate such as NAND) necessary to > compute the output values. Could there be tables derived from > equations so cleverly arranged that brute forcing is very simple once > you know the original equations, but their exact structure is not > evident from the tables themselves? > > Once you have some equations, how would you go about simplifying them? > I suspect that finding the simplest form is probably NP-hard, but I'm > not certain and don't quite know where to start reading on the > subject. > -- > http://www.lightconsulting.com/~travis/ -><- > "We already have enough fast, insecure systems." -- Schneier & Ferguson > GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B > > --------------------------------------------------------------------- > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > -- I was scared. Petrified. Because (x) hearing voices isn't like catching a cold, you can't get rid of it with lemmon tea (y) it's inside, it is not some naevus, an epidermal blemish you can cover up or cauterise (z) I had no control over it. It was there of its own volition, just stopped in and (zz) I was going bananas. -Tibor Fischer ``The Thought Gang" Ariel Waissbein RESEARCHER CORE SECURITY TECHNOLOGIES http://www.coresecurity.com/corelabs --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
