Available online ,
doi: 10.11999/JEIT250690
Abstract:
Objective With the rapid development and widespread deployment of the Internet of Things (IoT), embedded systems, and mobile computing devices, ensuring secure communication and data protection on resource-constrained platforms has become a central focus in the field of information security. These devices are typically characterized by severe limitations in terms of computational capability, storage capacity, and energy consumption, which render traditional cryptographic algorithms inefficient or even infeasible in such environments. In response to these constraints, lightweight cryptographic algorithms have been proposed as an effective class of solutions. Their primary objective is to achieve comparable levels of security as traditional algorithms while significantly reducing the hardware and computational overhead through deliberate algorithmic simplifications and structural optimizations. These algorithms are designed to operate efficiently within tight resource bounds and are especially suitable for applications such as sensor networks, smart cards, RFID systems, and wearable devices. From the perspective of hardware implementation, the design of lightweight cryptographic algorithms must account for multiple performance indicators, including throughput, latency, power efficiency, chip area, and circuit depth. Among these, chip area and depth are considered particularly critical, as they directly influence the physical cost of production and the speed of computation. The Substitution-box (S-Box), as the core nonlinear component responsible for providing confusion in most symmetric encryption schemes, plays a decisive role in determining the security strength and implementation efficiency of the entire cipher. Therefore, exploring efficient methods to realize low-area and low-depth implementations of S-Boxes is of fundamental importance to the design of secure and practical lightweight cryptographic systems. Methods In this work, a novel S-Box optimization algorithm based on Boolean satisfiability (SAT) solving is proposed to simultaneously optimize two key hardware metrics: logic area and circuit depth. To this end, a circuit model with depth k and width w is constructed. Under a given area constraint, SAT solving techniques are employed to determine whether the circuit model can implement the target S-Box. By iteratively adjusting circuit depth, width, and area parameters, an optimized implementation scheme of the S-Box is eventually obtained. The method is specifically developed for 4-bit S-Boxes, which are widely adopted in many lightweight block ciphers, and it provides implementations that are highly efficient in both structural compactness and computational depth. This dual optimization approach helps to reduce hardware costs while maintaining low latency, making it especially suitable for scenarios where performance and energy efficiency are both critical. The proposed method begins by transforming the S-Box implementation problem into a formal SAT problem, enabling the use of powerful SAT solvers to exhaustively explore possible logic-level representations. In this transformation, a diverse set of logic gates—including 2-input, 3-input, and 4-input gates—is utilized to construct flexible logic networks. To enforce area and depth constraints, arithmetic operations such as binary addition and comparator logic are encoded into SAT-compatible Boolean constraints, which guide the solver toward low-area and low-depth solutions. To further accelerate the solving process and avoid redundant search paths, symmetry-breaking constraints are introduced. These constraints help eliminate logically equivalent but structurally different representations, thereby significantly reducing the size of the solution space. The Cadical SAT solver, known for its speed and efficiency in handling large-scale SAT problems, is employed to compute optimized S-Box implementations that minimize both depth and area. The proposed approach not only generates efficient implementations but also provides a general modeling framework that can be extended to other logic synthesis problems in cryptographic hardware design. Results and Discussions To validate the effectiveness of the proposed optimization method, a comprehensive set of experiments was conducted on 4-bit S-Boxes from several representative lightweight block ciphers, including Joltik, Piccolo, Rectangle, Skinny, Lblock, Lac, Midori, and Prøst. The results demonstrate that the method consistently produces high-quality implementations that are competitive or superior in terms of both chip area and circuit depth when compared with existing state-of-the-art results. Specifically, for the S-Boxes of Joltik and Piccolo, as well as for those used in Skinny and Rectangle, the generated implementations match the best known results in both metrics, indicating that the method can successfully reproduce optimal or near-optimal designs. In the cases of Lblock and Lac, although the logic area remains similar to prior results, the circuit depth is significantly reduced, from an initial value of 10 down to 3, which represents a substantial improvement in processing latency and suitability for real-time applications. For the inverse S-Box of the Rectangle cipher, the proposed implementation achieves the same circuit depth as previous designs but reduces the area from 24.33 gate equivalents (GE) to 17.66 GE, yielding a more compact and efficient realization. The optimization results for the Midori S-Box further confirm the effectiveness of the method, where both depth and area are improved—depth is reduced from 4 to 3, and area is brought down from 20.00 GE to 16.33 GE. For the Prøst cipher’s S-Box, two alternative implementations are presented to illustrate the trade-off between area and depth. The first achieves a depth of 4 with an area of 22.00 GE, matching the best known depth but at a higher area cost, while the second increases the depth to 5 but reduces the area significantly to 13.00 GE. These results demonstrate that the method not only supports flexible optimization under different design constraints but also contributes to a deeper understanding of the complexity and trade-offs involved in S-Box implementation. Conclusions This paper presents a SAT-based method for jointly optimizing S-box hardware implementations in terms of area and circuit depth. By modeling the S-box realization as a satisfiability problem and exploiting advanced constraint encoding, multi-input logic gates, and symmetry-breaking techniques, the method effectively reduces hardware complexity while maintaining or improving depth performance. Extensive experiments on various 4-bit S-boxes demonstrate that the proposed approach matches or outperforms existing results, particularly in reducing circuit depth and improving logic compactness. This makes it well suited for lightweight cryptographic systems operating under strict constraints on silicon area, speed, and energy consumption.Despite these advantages, the method still has limitations. While it achieves optimal or near-optimal results for 4-bit S-boxes, scalability to larger instances such as 5-bit or 8-bit S-boxes remains challenging due to the exponential growth of the search space and solving time. As model complexity increases, solving becomes computationally expensive and may not converge in practice. Future work will focus on improving modeling efficiency and solver performance through refined constraint generation, stronger pruning strategies, and heuristic-guided search, with the goal of extending the method to more complex S-boxes and other nonlinear components in lightweight and post-quantum cryptographic systems.