Yao Sun
State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Min Zhang
State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Ting Li
State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Keywords: S-box, Circuit depth, Gate count, Boyar-Peralta algorithm, AES

Abstract

Good circuits of cryptographic components must balance performance and area. Lower circuit depth increases performance, while fewer gates decrease area. A trade-off exists between gate count and depth. Optimizing the gate count of a circuit under depth constraints is always significant. In this paper, we study how to obtain an S-box circuit with fewer gate count from a given circuit, while constraining the depth of the outputs. Unlike the linear layer, the S-box circuit involves more linear and nonlinear gates, so optimizing it requires more computations. To solve this problem, Boyar and Peralta proposed a layer-by-layer algorithm. They first divide an S-box into several linear and nonlinear layers. The outputs of each layer are sub-targets. Boyar-Peralta’s algorithm must generate all sub-targets in the current layer before proceeding to the next layer. Jeon et al. improved this layer-by-layer algorithm at CHES 2025. In their algorithm, new sub-targets in the next layer can be activated flexibly, without waiting for all sub-targets in the current layer to be generated. Because the local sub-targets in their algorithm change at each stage, we refer to Jeon et al.’s algorithm as the stage-by-stage algorithm. Neither Boyar-Peralta’s nor Jeon et al.’s algorithms initially handle the final targets. As a likely consequence, their algorithms may find optimal sub-circuits for sub-targets but obtain only suboptimal circuits for the final targets. By defining the weighted distance from the final target, we propose a new end-to-end algorithm for optimizing the circuit. The distance from the sub-targets does not need to be considered independently. Besides, two new techniques are presented to speed up this end-to-end algorithm significantly. We have also given several heuristic optimizations to improve the performance. As a result, we improved all circuits given by Jeon et al. under different depth constraints.