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]
