Skip to main content
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.

Small Low-Depth Circuits for Cryptographic Applications



Joan Boyar, Magnus G. Find, Rene Peralta


We present techniques to obtain small circuits which also have low depth. The techniques apply to typical cryptographic functions, as these are often specified over the field GF(2), and they produce circuits containing only AND, XOR and XNOR gates. The emphasis is on the linear components (those portions containing no AND gates). A new heuristic, DCLO (for depth-constrained linear optimization), is used to create small linear circuits given depth constraints. DCLO is repeatedly used in a See-Saw method, alternating between optimizing the upper linear component and the lower linear component. The depth constraints specify both the depth at which each input arrives and restrictions on the depth for each output. We apply our techniques to cryptographic functions, obtaining new results for the AES S-Box, for multiplication of binary polynomials, and for multiplication in finite fields. Additionally, we reduced by 2/3 the size of the 16-bit S-Box proposed in [Kelly, Kaminsky, Kurdziel, Lukowiak, Radziszowski, 2015].
Cryptography and Communication


circuit size, circuit depth, cryptographic functions, Boolean functions, See-Saw Method, depth-constrained circuit optimization


Boyar, J. , Find, M. and Peralta, R. (2018), Small Low-Depth Circuits for Cryptographic Applications, Cryptography and Communication, [online],, (Accessed July 25, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created March 23, 2018, Updated October 12, 2021