Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Logic Minimization Techniques with Applications to Cryptology

Published

Author(s)

Joan Boyar, Philip Matthews, Rene Peralta

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

Keywords

Circuit complexity, multiplicative complexity, linear component minimization, Shortest Linear Program, cancellation, AES, S-box.

Citation

Boyar, J. , Matthews, P. and Peralta, R. (2013), Logic Minimization Techniques with Applications to Cryptology, Journal of Cryptology, [online], https://doi.org/10.1007/s00145-012-9124-7, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=908384 (Accessed March 28, 2024)
Created March 31, 2013, Updated October 12, 2021