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

Published

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

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 March 4, 2024)
Created March 23, 2018, Updated October 12, 2021