Small Low-Depth Circuits for Cryptographic Applications

Published

March 24, 2018

Author(s)

Joan Boyar, Magnus G. Find, Rene Peralta

Abstract

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

Citation

Cryptography and Communication

Pub Type

Journals

Download Paper

https://doi.org/10.1007/s12095-018-0296-3

Local Download

Keywords

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

Citation

Boyar, J. , Find, M. and Peralta, R. (2018), Small Low-Depth Circuits for Cryptographic Applications, Cryptography and Communication, [online], https://doi.org/10.1007/s12095-018-0296-3, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=924490 (Accessed April 28, 2026)

Additional citation formats