Communications in Cryptology IACR CiC

Technology-Dependent Synthesis and Optimization of Circuits for Small S-boxes

Authors

Zihao Wei, Siwei Sun, Fengmei Liu, Lei Hu, Zhiyu Zhang
Zihao Wei ORCID
School of Cryptology, Beijing, China
Data Communication Science and Technology Research Institute, Beijing, China
wei_z_h at 163 dot com
Siwei Sun ORCID
School of Cryptology, Beijing, China
State Key Laboratory of Cryptology, Beijing, China
siweisun dot isaac at gmail dot com
Fengmei Liu
Data Communication Science and Technology Research Institute, Beijing, China
lfmei at sina dot com
Lei Hu
Key Laboratory of Cyberspace Security Defense, Beijing, China
School of Cyber Security, Beijing, China
hulei at iie dot ac dot cn
Zhiyu Zhang ORCID
School of Cryptology, Beijing, China
zhangzhiyu14 at mails dot ucas dot ac dot cn

Abstract

Boolean formula minimization is a notoriously hard problem. Circuit minimization, typically studied in the context of a much broader subject known as synthesis and optimization of circuits, introduces another layer of complexity since ultimately those technology-independent representations (e.g., Boolean formulas and truth tables) has to be transformed into a netlist of cells of the target technology library. To manage those complexities, the industrial community typically separates the synthesis process into two steps: technology-independent optimization and technology mapping. In each step, this approach only tries to find the local optimal solution and relies heavily on heuristics rather than a systematic search. However, for small S-boxes, a more systematic exploration of the design space is possible. Aiming at the global optimum, we propose a method which can synthesize a truth table for a small S-box directly into a netlist of the cells of a given technology library. Compared with existing technology-dependent synthesis tools like LIGHTER and PEIGEN, our method produces improved results for many S-boxes with respect to circuit area. In particular, by applying our method to the GF(2^4)-inverter involved in the tower field implementation of the AES S-box, we obtain the currently known lightest implementation of the AES S-box. The search framework can be tweaked to take circuit delay into account. As a result, we find implementations for certain S-boxes with both latency and area improved.

References

[abc]
ABC: A System for Sequential Synthesis and Verification. https://people.eecs.berkeley.edu/ alanmi/abc/.
[ARS+15a]
Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 430–454. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_17
[ARS+15b]
Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 430–454. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_17
[BBI+15]
Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: A Block Cipher for Low Energy. In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 411–436. 2015. Springer. DOI: 10.1007/978-3-662-48800-3_17
[BGG+16]
Erik Boss, Vincent Grosso, Tim Güneysu, Gregor Leander, Amir Moradi, and Tobias Schneider. Strong 8-bit Sboxes with Efficient Masking in Hardware. In Benedikt Gierlichs and Axel Y. Poschmann, editors, Cryptographic Hardware and Embedded Systems - CHES 2016 - 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings, volume 9813 of Lecture Notes in Computer Science, pages 171–193. 2016. Springer. DOI: 10.1007/978-3-662-53140-2_9
[BGG+17]
Erik Boss, Vincent Grosso, Tim Güneysu, Gregor Leander, Amir Moradi, and Tobias Schneider. Strong 8-bit Sboxes with efficient masking in hardware extended version. J. Cryptogr. Eng., 7(2):149–165, 2017. DOI: 10.1007/S13389-017-0156-7
[BGLS19]
Zhenzhen Bao, Jian Guo, San Ling, and Yu Sasaki. PEIGEN - a Platform for Evaluation, Implementation, and Generation of S-boxes. IACR Trans. Symmetric Cryptol., 2019(1):330–394, 2019. DOI: 10.13154/TOSC.V2019.I1.330-394
[BHS90]
Robert K. Brayton, Gary D. Hachtel, and Alberto L. Sangiovanni-Vincentelli. Multilevel logic synthesis. Proc. IEEE, 78(2):264–300, 1990. DOI: 10.1109/5.52213
[BIL+21]
Subhadeep Banik, Takanori Isobe, Fukang Liu, Kazuhiko Minematsu, and Kosei Sakamoto. Orthros: A Low-Latency PRF. IACR Trans. Symmetric Cryptol., 2021(1):37–77, 2021. DOI: 10.46586/tosc.v2021.i1.37-77
[BJK+16]
Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 123–153. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_5
[BKL+07]
Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. PRESENT: An Ultra-Lightweight Block Cipher. In Pascal Paillier and Ingrid Verbauwhede, editors, Cryptographic Hardware and Embedded Systems - CHES 2007, 9th International Workshop, Vienna, Austria, September 10-13, 2007, Proceedings, volume 4727 of Lecture Notes in Computer Science, pages 450–466. 2007. Springer. DOI: 10.1007/978-3-540-74735-2_31
[BKL16]
Christof Beierle, Thorsten Kranz, and Gregor Leander. Lightweight Multiplication in GF(2n) with Applications to MDS Matrices. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 625–653. 2016. Springer. DOI: 10.1007/978-3-662-53018-4_23
[BM10]
Robert K. Brayton and Alan Mishchenko. ABC: An Academic Industrial-Strength Verification Tool. In Tayssir Touili, Byron Cook, and Paul B. Jackson, editors, Computer Aided Verification, 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings, volume 6174 of Lecture Notes in Computer Science, pages 24–40. 2010. Springer. DOI: 10.1007/978-3-642-14295-6_5
[BMP13]
Joan Boyar, Philip Matthews, and René Peralta. Logic Minimization Techniques with Applications to Cryptology. J. Cryptol., 26(2):280–312, 2013. DOI: 10.1007/S00145-012-9124-7
[BPP+17]
Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A Small Present - Towards Reaching the Limit of Lightweight Encryption. In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science, pages 321–345. 2017. Springer. DOI: 10.1007/978-3-319-66787-4_16
[Can05]
David Canright. A Very Compact S-Box for AES. In Josyula R. Rao and Berk Sunar, editors, Cryptographic Hardware and Embedded Systems - CHES 2005, 7th International Workshop, Edinburgh, UK, August 29 - September 1, 2005, Proceedings, volume 3659 of Lecture Notes in Computer Science, pages 441–455. 2005. Springer. DOI: 10.1007/11545262_32
[CDL15]
Anne Canteaut, Sébastien Duval, and Gaëtan Leurent. Construction of Lightweight S-Boxes Using Feistel and MISTY Structures. In Orr Dunkelman and Liam Keliher, editors, Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, volume 9566 of Lecture Notes in Computer Science, pages 373–393. 2015. Springer. DOI: 10.1007/978-3-319-31301-6_22
[CDL+20]
Anne Canteaut, Sébastien Duval, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Thomas Pornin, and André Schrottenloher. Saturnin: a suite of lightweight symmetric algorithms for post-quantum security. IACR Trans. Symmetric Cryptol., 2020(S1):160–207, 2020. DOI: 10.13154/tosc.v2020.iS1.160-207
[Cou07]
Nicolas T. Courtois. How Fast can be Algebraic Attacks on Block Ciphers?. In Eli Biham, Helena Handschuh, Stefan Lucks, and Vincent Rijmen, editors, Symmetric Cryptography, 07.01. - 12.01.2007, volume 07021 of Dagstuhl Seminar Proceedings. 2007. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany.
[DGV93]
Joan Daemen, René Govaerts, and Joos Vandewalle. A New Approach to Block Cipher Design. In Ross J. Anderson, editor, Fast Software Encryption, Cambridge Security Workshop, Cambridge, UK, December 9-11, 1993, Proceedings, volume 809 of Lecture Notes in Computer Science, pages 18–32. 1993. Springer. DOI: 10.1007/3-540-58108-1_2
[DL18]
Sébastien Duval and Gaëtan Leurent. MDS Matrices with Lightweight Circuits. IACR Trans. Symmetric Cryptol., 2018(2):48–78, 2018. DOI: 10.13154/TOSC.V2018.I2.48-78
[FS10]
Carsten Fuhs and Peter Schneider-Kamp. Synthesizing Shortest Linear Straight-Line Programs over GF(2) Using SAT. In Ofer Strichman and Stefan Szeider, editors, Theory and Applications of Satisfiability Testing - SAT 2010, 13th International Conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings, volume 6175 of Lecture Notes in Computer Science, pages 71–84. 2010. Springer. DOI: 10.1007/978-3-642-14186-7_8
[GJN+16]
Jian Guo, Jérémy Jean, Ivica Nikolic, Kexin Qiao, Yu Sasaki, and Siang Meng Sim. Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs. IACR Trans. Symmetric Cryptol., 2016(1):33–56, 2016. DOI: 10.13154/TOSC.V2016.I1.33-56
[GLWL16]
Zhiyuan Guo, Renzhang Liu, Wenling Wu, and Dongdai Lin. Direct Construction of Lightweight Rotational-XOR MDS Diffusion Layers. IACR Cryptol. ePrint Arch., 2016.
[JNP14]
Jérémy Jean, Ivica Nikolić, and Thomas Peyrin. Joltik v1. CAESAR competition, 2014.
[JPST17a]
Jérémy Jean, Thomas Peyrin, Siang Meng Sim, and Jade Tourteaux. Optimizing Implementations of Lightweight Building Blocks. IACR Trans. Symmetric Cryptol., 2017(4):130–168, 2017. DOI: 10.13154/TOSC.V2017.I4.130-168
[JPST17b]
Jérémy Jean, Thomas Peyrin, Siang Meng Sim, and Jade Tourteaux. Optimizing Implementations of Lightweight Building Blocks. IACR Trans. Symmetric Cryptol., 2017(4):130–168, 2017. DOI: 10.13154/TOSC.V2017.I4.130-168
[KLPR10]
Lars R. Knudsen, Gregor Leander, Axel Poschmann, and Matthew J. B. Robshaw. PRINTcipher: A Block Cipher for IC-Printing. In Stefan Mangard and François-Xavier Standaert, editors, Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17-20, 2010. Proceedings, volume 6225 of Lecture Notes in Computer Science, pages 16–32. 2010. Springer. DOI: 10.1007/978-3-642-15031-9_2
[KLSW17]
Thorsten Kranz, Gregor Leander, Ko Stoffelen, and Friedrich Wiemer. Shorter Linear Straight-Line Programs for MDS Matrices. IACR Trans. Symmetric Cryptol., 2017(4):188–211, 2017. DOI: 10.13154/TOSC.V2017.I4.188-211
[LSL+19]
Shun Li, Siwei Sun, Chaoyun Li, Zihao Wei, and Lei Hu. Constructing Low-latency Involutory MDS Matrices with Lightweight Circuits. IACR Trans. Symmetric Cryptol., 2019(1):84–117, 2019. DOI: 10.13154/TOSC.V2019.I1.84-117
[LW14]
Yongqiang Li and Mingsheng Wang. Constructing S-boxes for Lightweight Cryptography with Feistel Structure. In Lejla Batina and Matthew Robshaw, editors, Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings, volume 8731 of Lecture Notes in Computer Science, pages 127–146. 2014. Springer. DOI: 10.1007/978-3-662-44709-3_8
[LW16]
Yongqiang Li and Mingsheng Wang. On the Construction of Lightweight Circulant Involutory MDS Matrices. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 121–139. 2016. Springer. DOI: 10.1007/978-3-662-52993-5_7
[LW17]
Chaoyun Li and Qingju Wang. Design of Lightweight Linear Diffusion Layers from Near-MDS Matrices. IACR Trans. Symmetric Cryptol., 2017(1):129–155, 2017. DOI: 10.13154/TOSC.V2017.I1.129-155
[Max19]
Alexander Maximov. AES MixColumn with 92 XOR gates. IACR Cryptol. ePrint Arch., 2019.
[McC56]
Edward J. McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 35(6):1417–1444, 1956. DOI: https://doi.org/10.1002/j.1538-7305.1956.tb03835.x
[ME19]
Alexander Maximov and Patrik Ekdahl. New Circuit Minimization Techniques for Smaller and Faster AES SBoxes. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019(4):91–125, 2019. DOI: 10.13154/TCHES.V2019.I4.91-125
[MPL+11]
Amir Moradi, Axel Poschmann, San Ling, Christof Paar, and Huaxiong Wang. Pushing the Limits: A Very Compact and a Threshold Implementation of AES. In Kenneth G. Paterson, editor, Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, pages 69–88. 2011. Springer. DOI: 10.1007/978-3-642-20465-4_6
[RTA18]
Arash Reyhani-Masoleh, Mostafa M. I. Taha, and Doaa Ashmawy. Smashing the Implementation Records of AES S-box. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(2):298–336, 2018. DOI: 10.13154/TCHES.V2018.I2.298-336
[SKOP15]
Siang Meng Sim, Khoongming Khoo, Frédérique E. Oggier, and Thomas Peyrin. Lightweight MDS Involution Matrices. In Gregor Leander, editor, Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, volume 9054 of Lecture Notes in Computer Science, pages 471–493. 2015. Springer. DOI: 10.1007/978-3-662-48116-5_23
[SPGQ06]
François-Xavier Standaert, Gilles Piret, Neil Gershenfeld, and Jean-Jacques Quisquater. SEA: A Scalable Encryption Algorithm for Small Embedded Applications. In Josep Domingo-Ferrer, Joachim Posegga, and Daniel Schreckling, editors, Smart Card Research and Advanced Applications, 7th IFIP WG 8.8/11.2 International Conference, CARDIS 2006, Tarragona, Spain, April 19-21, 2006, Proceedings, volume 3928 of Lecture Notes in Computer Science, pages 222–236. 2006. Springer. DOI: 10.1007/11733447_16
[SS16]
Sumanta Sarkar and Habeeb Syed. Lightweight Diffusion Layer: Importance of Toeplitz Matrices. IACR Trans. Symmetric Cryptol., 2016(1):95–113, 2016. DOI: 10.13154/TOSC.V2016.I1.95-113
[Sto16]
Ko Stoffelen. Optimizing S-Box Implementations for Several Criteria Using SAT Solvers. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 140–160. 2016. Springer. DOI: 10.1007/978-3-662-52993-5_8
[TP20]
Quan Quan Tan and Thomas Peyrin. Improved Heuristics for Short Linear Programs. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2020(1):203–230, 2020. DOI: 10.13154/TCHES.V2020.I1.203-230
[WZ11]
Wenling Wu and Lei Zhang. LBlock: A Lightweight Block Cipher. In Javier López and Gene Tsudik, editors, Applied Cryptography and Network Security - 9th International Conference, ACNS 2011, Nerja, Spain, June 7-10, 2011. Proceedings, volume 6715 of Lecture Notes in Computer Science, pages 327–344. 2011. DOI: 10.1007/978-3-642-21554-4_19
[ZBL+15]
Wentao Zhang, Zhenzhen Bao, Dongdai Lin, Vincent Rijmen, Bohan Yang, and Ingrid Verbauwhede. RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. Sci. China Inf. Sci., 58(12):1–15, 2015. DOI: 10.1007/s11432-015-5459-7
[ZJB06]
Junlan Zhou, Zhengrong Ji, and Rajive L. Bagrodia. TWINE: A Hybrid Emulation Testbed for Wireless Networks and Applications. In INFOCOM 2006. 25th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain. 2006. IEEE. DOI: 10.1109/INFOCOM.2006.183
[ZWS18]
Lijing Zhou, Licheng Wang, and Yiru Sun. On Efficient Constructions of Lightweight MDS Matrices. IACR Trans. Symmetric Cryptol., 2018(1):180–200, 2018. DOI: 10.13154/TOSC.V2018.I1.180-200

PDFPDF Open access

History
Submitted: 2024-10-07
Accepted: 2024-12-03
Published: 2025-01-13
How to cite

Zihao Wei, Siwei Sun, Fengmei Liu, Lei Hu, and Zhiyu Zhang, Technology-Dependent Synthesis and Optimization of Circuits for Small S-boxes. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/akmpdkp10.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.