Optimized Implementation of Low-Depth Lightweight S-Boxes

FENG Zixi; LIU Yupeng; DOU Guowei; LIU Chengle

doi:10.11999/JEIT250690

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2026 >

FENG Zixi, LIU Yupeng, DOU Guowei, LIU Chengle. Optimized Implementation of Low-Depth Lightweight S-Boxes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250690

Citation:

FENG Zixi, LIU Yupeng, DOU Guowei, LIU Chengle. Optimized Implementation of Low-Depth Lightweight S-Boxes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250690

FENG Zixi, LIU Yupeng, DOU Guowei, LIU Chengle. Optimized Implementation of Low-Depth Lightweight S-Boxes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250690

Citation:

FENG Zixi, LIU Yupeng, DOU Guowei, LIU Chengle. Optimized Implementation of Low-Depth Lightweight S-Boxes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250690

PDF( 666 KB)

Optimized Implementation of Low-Depth Lightweight S-Boxes

doi: 10.11999/JEIT250690 cstr: 32379.14.JEIT250690

Data Communication Science and Technology Research Institute, Beijing 100191, China

Received Date: 2025-07-23
Accepted Date: 2026-02-13
Rev Recd Date: 2026-02-13

Available Online: 2026-03-07

Abstract

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.
- S-Box Optimization,
- Satisfiability problem,
- Equivalent gates,
- Circuit area,
- Circuit depth

FullText(HTML)

References(20)

References

[1]	钟悦, 谷杰铭, 曹洪林. 轻量级分组密码算法综述[J]. 计算机科学, 2023, 50(9): 3–15. doi: 10.11896/jsjkx.230500190. ZHONG Yue, GU Jieming, and CAO Honglin. A survey of lightweight block cipher[J]. Computer Science, 2023, 50(9): 3–15. doi: 10.11896/jsjkx.230500190.
[2]	贾美纯. 两类轻量级分组密码算法的安全性研究[D]. [硕士论文]. 西北师范大学, 2024. doi: 10.27410/d.cnki.gxbfu.2024.002853. JIA Meichun. Security analysis on two types of lightweight block cipher algorithms[D]. [Master dissertation]. Northwest Normal University, 2024. doi: 10.27410/d.cnki.gxbfu.2024.002853.
[3]	JEAN J, PEYRIN T, SIM S M, et al. Optimizing implementations of lightweight building blocks[J]. IACR Transactions on Symmetric Cryptology, 2017, 2017(4): 130–168. doi: 10.13154/tosc.v2017.i4.130-168.
[4]	BAO Zhenzhen, GUO Jian, LING San, et al. PEIGEN–a platform for evaluation, implementation, and generation of S-boxes[J]. IACR Transactions on Symmetric Cryptology, 2019, 2019(1): 330–394. doi: 10.13154/tosc.v2019.i1.330-394.
[5]	WEI Zihao, SUN Siwei, LIU Fengmei, et al. Technology-dependent synthesis and optimization of circuits for small S-boxes[J]. IACR Communications in Cryptology, 2025, 1(4): 35. doi: 10.62056/akmpdkp10.
[6]	COURTOIS N, MOUROUZIS T, and HULME D. Exact logic minimization and multiplicative complexity of concrete algebraic and cryptographic circuits[J]. International Journal on Advances in Intelligent Systems, 2013, 6(3/4): 165–176.
[7]	STOFFELEN K. Optimizing S-box implementations for several criteria using SAT solvers[C]. Proceedings of the 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 140–160. doi: 10.1007/978-3-662-52993-5_8.
[8]	LU Zhenyu, WANG Weijia, HU Kai, et al. Pushing the limits: Searching for implementations with the smallest area for lightweight S-boxes[C]. Proceedings of the 22nd International Conference on Progress in Cryptology, Jaipur, India, 2021: 159–178. doi: 10.1007/978-3-030-92518-5_8.
[9]	ZHANG Fuxin and HUANG Zhenyu. Optimizing S-box implementations using SAT solvers: Revisited[EB/OL]. Cryptology ePrint Archive, https://eprint.iacr.org/2023/1721, 2023.
[10]	JIA Chenhao, CUI Tingting, LING Qing, et al. How small can S-boxes be?[J]. IACR Transactions on Symmetric Cryptology, 2025, 2025(1): 592–622. doi: 10.46586/tosc.v2025.i1.592-622.
[11]	SUN Yu, WU Lixuan, JIA Chenhao, et al. Addendum to how small can S-boxes be?[J]. IACR Transactions on Symmetric Cryptology, 2025, 2025(2): 192–205. doi: 10.46586/TOSC.V2025.I2.192-205.
[12]	JEAN J, NIKOLIĆ I, and PEYRIN T. Joltik v1.3[EB/OL]. CAESAR Round, https://competitions.cr.yp.to/round2/joltikv13.pdf, 2015.
[13]	SHIBUTANI K, ISOBE T, HIWATARI H, et al. Piccolo: An ultra-lightweight blockcipher[C]. Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems, Nara, Japan, 2011: 342–357. doi: 10.1007/978-3-642-23951-9_23.
[14]	ZHANG Wentao, BAO Zhenzhen, LIN Dongdai, et al. RECTANGLE: A bit-slice lightweight block cipher suitable for multiple platforms[J]. Science China Information Sciences, 2015, 58(12): 1–15. doi: 10.1007/s11432-015-5459-7.
[15]	BEIERLE C, JEAN J, KÖLBL S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]. Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2016: 123–153. doi: 10.1007/978-3-662-53008-5_5.
[16]	WU Wenling and ZHANG Lei. LBlock: A lightweight block cipher[C]. Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Nerja, Spain, 2011: 327–344. doi: 10.1007/978-3-642-21554-4_19.
[17]	ZHANG Lei, WU Wenling, WANG Yanfeng, et al. LAC: A lightweight authenticated encryption cipher[EB/OL]. Submitted to the CAESAR competition, https://competitions.cr.yp.to/round1/lacv1.pdf, 2014.
[18]	BANIK S, BOGDANOV A, ISOBE T, et al. Midori: A block cipher for low energy[C]. Proceedings of the 21st International Conference on Advances in Cryptology, Auckland, New Zealand, 2015: 411–436. doi: 10.1007/978-3-662-48800-3_17.
[19]	KAVUN E B, LAURIDSEN M M, LEANDER G, et al. PRØST v1[EB/OL]. CAESAR Round, https://competitions.cr.yp.to/round1/proestv1.pdf, 2014.
[20]	BANIK S, FUNABIKI Y, and ISOBE T. More results on shortest linear programs[C]. Proceedings of the 14th International Workshop on Advances in Information and Computer Security, Tokyo, Japan, 2019: 109–128. doi: 10.1007/978-3-030-26834-3_7.