An official website of the United States government
Here’s how you know
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].
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 December 7, 2024)