Paper 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.

Note: Fixed a typo. Added tables containing experimental results that do not fit in the SEA 2010 document.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. extended abstract will appear in proceedings of SEA 2010
Keywords
AESS-boxfinite field inversioncircuit complexitymultiplicative complexity.
Contact author(s)
peralta @ nist gov
History
2010-03-13: revised
2009-05-04: received
See all versions
Short URL
https://ia.cr/2009/191
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/191,
      author = {Joan Boyar and Rene Peralta},
      title = {New logic minimization techniques with applications to cryptology.},
      howpublished = {Cryptology ePrint Archive, Paper 2009/191},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/191}},
      url = {https://eprint.iacr.org/2009/191}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.