A new technique for combinational logic optimization is described. The technique is a two-step process. In the first step, the non-linearity of a circuit -- as measured by the number of non-linear gates it contains -- is reduced. The second step reduces the number of gates in the linear components of the already reduced circuit. The technique can be applied to arbitrary combinational logic problems, and often yields improvements even after optimization by standard methods has been performed. In this paper we show the results of our technique when applied to the S-box of the Advanced Encryption Standard (AES).
We also show that in the second step, one is faced with an NP-hard problem, the Shortest Linear Program (SLP) problem, which is to minimize the number of linear operations necessary to compute a set of linear forms. In addition to showing that SLP is NP-hard, we show that a special case of the corresponding decision problem is Max SNP-Complete, implying limits to its approximability.
Previous algorithms for minimizing the number of gates in linear components produced cancellation-free straight-line programs, i.e., programs in which there is no cancellation of variables in GF(2). We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to non-trivial inputs. The straight-line programs produced by our techniques are not always cancellation-free. We have experimentally verified that, for randomly chosen linear transformations, they are significantly smaller than the circuits produced by previous algorithms.