Logic Minimization Techniques with Applications to Cryptology

A new technique for combinational logic optimization is described. The technique is a two-step process. In the first step, the nonlinearity of a circuit-as measured by the number of nonlinear 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 (FIPS in Advanced Encryption Standard (AES), National Institute of Standards and Technology, 2001).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 nontrivial 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.

描述了一种组合逻辑优化的新技术。该技术是一个两步的过程。在第一步中，通过电路所含非线性门的数量来衡量的电路非线性度得以降低。第二步减少已简化电路的线性组件中的门的数量。该技术可应用于任意组合逻辑问题，并且即使在已经使用标准方法进行优化之后，通常也能带来改进。在本文中，我们展示了将我们的技术应用于高级加密标准（美国国家标准与技术研究院，2001年《高级加密标准（AES）中的FIPS》）的S盒时的结果。我们还表明，在第二步中，面临一个NP难问题，即最短线性程序（SLP）问题，该问题是要使计算一组线性形式所需的线性操作数量最小化。除了表明SLP是NP难问题之外，我们还表明相应判定问题的一个特殊情况是最大SNP完全的，这意味着其可近似性存在限制。先前用于最小化线性组件中门数量的算法产生无抵消的直线程序，即伽罗瓦域GF(2)中变量无抵消的程序。我们表明此类算法的近似比至少为3/2，因此不能期望它们对非平凡输入产生最优解。我们的技术所产生的直线程序并不总是无抵消的。我们通过实验验证，对于随机选择的线性变换，它们比先前算法产生的电路要小得多。