NIST logo

Publication Citation: Logic Minimization Techniques with Applications to Cryptology

NIST Authors in Bold

Author(s): Joan Boyar; Philip Matthews; Rene C. Peralta;
Title: Logic Minimization Techniques with Applications to Cryptology
Published: April 01, 2013
Abstract: A new technique for combinational logic optimization is described. The technique is a two-step process. In the rst 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 [13]). 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 veri ed that, for randomly chosen linear transformations, they are signi cantly smaller than the circuits produced by previous algorithms.
Citation: Journal of Cryptology
Volume: 26
Issue: 2
Pages: pp. 280 - 312
Keywords: Circuit complexity; multiplicative complexity; linear component minimization; Shortest Linear Program; cancellation; AES; S-box.
Research Areas: Information Technology, Cybersecurity
DOI: http://dx.doi.org/10.1007/s00145-012-9124-7  (Note: May link to a non-U.S. Government webpage)
PDF version: PDF Document Click here to retrieve PDF version of paper (850KB)