Cryptology ePrint Archive: Report 2009/191
New logic minimization techniques with applications to cryptology.
Joan Boyar and Rene Peralta
Abstract: A new technique for combinational circuit optimization
is described in the context of S-boxes.
The technique is a two-step process. In
the first step, the non-linearity of the 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 circuits, and seems
to yield improvements even on circuits that have
already been optimized by standard methods. We apply our technique
to the S-box of the Advanced Encryption Standard (AES).
The result is, as far as we know, the
smallest circuit yet constructed for this function.
Category / Keywords: implementation / AES; S-box; finite field inversion; circuit complexity; multiplicative complexity.
Publication Info: extended abstract will appear in proceedings of SEA 2010
Date: received 4 May 2009, last revised 13 Mar 2010
Contact author: peralta at nist gov
Available formats: PDF | BibTeX Citation
Note: Fixed a typo. Added tables containing experimental results that do not fit in the SEA 2010 document.
Version: 20100313:080431 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]