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.

PUBLICATIONS

A New Combinational Logic Minimization Technique with Applications to Cryptology

Published

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.
Information technology and Cybersecurity

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 April 25, 2024)

Created May 19, 2010, Updated October 12, 2021