A New Combinational Logic Minimization Technique with Applications to Cryptology

Published

May 20, 2010

Author(s)

Joan Boyar, Rene Peralta

Abstract

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). This is an experimental proof of concept, as opposed to a full-fledged circuit optimization effort. Nevertheless the result is, as far as we know, the circuit with the smallest gate count yet constructed for this function. We have also used the technique to improve the performance (in software) of several candidates to the Cryptographic Hash Algorithm Competition. Finally, we have experimentally verified that the second step of our technique yields significant improvements over conventional methods when applied to randomly chosen linear transformations.

Proceedings Title

Experimental Algorithms (Lecture Notes in Computer Science

Volume

6049

Conference Dates

May 20-22, 2010

Conference Location

Ischia Island (Napoli), IT

Conference Title

9th International Symposium on Experimental Algorithms (SEA 2010)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-642-13193-6_16

Local Download

Keywords

AES, S-box, finite field inversion, circuit complexity, multiplicative complexity.

Citation

Boyar, J. and Peralta, R. (2010), A New Combinational Logic Minimization Technique with Applications to Cryptology, Experimental Algorithms (Lecture Notes in Computer Science, Ischia Island (Napoli), IT, [online], https://doi.org/10.1007/978-3-642-13193-6_16, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=902701 (Accessed September 19, 2024)