Optimizing Implementations of Boolean Functions

Meltem Sonmez Turan

Paper 2024/133

Optimizing Implementations of Boolean Functions

Meltem Sonmez Turan

, National Institute of Standards and Technology

Abstract

Symmetric cryptography primitives are constructed by iterative applications of linear and nonlinear layers. Constructing efficient circuits for these layers, even for the linear one, is challenging. In 1997, Paar proposed a heuristic to minimize the number of XORs (modulo 2 addition) necessary to implement linear layers. In this study, we slightly modify Paar’s heuristics to find implementations for nonlinear Boolean functions, in particular to homogeneous Boolean functions. Additionally, we show how this heuristic can be used to construct circuits for generic Boolean functions with small number of AND gates, by exploiting affine equivalence relations.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: circuit optimization Boolean functions
Contact author(s): meltemsturan @ gmail com
History: 2024-01-31: approved; 2024-01-30: received; See all versions
Short URL: https://ia.cr/2024/133
License: CC BY

BibTeX

@misc{cryptoeprint:2024/133,
      author = {Meltem Sonmez Turan},
      title = {Optimizing Implementations of Boolean Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/133},
      year = {2024},
      url = {https://eprint.iacr.org/2024/133}
}