New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation

Jingwen Chen; Qun Liu; Yanhong Fan; Lixuan Wu; Boyun Li; Meiqin Wang

doi:10.62056/anmmp-4c2h

New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation

Authors

Jingwen Chen, Qun Liu, Yanhong Fan, Lixuan Wu, Boyun Li, Meiqin Wang

Jingwen Chen

School of Cyber Science and Technology, Shandong University, Qingdao, China
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
jingwenchen at mail dot sdu dot edu dot cn

Qun Liu

School of Cyber Science and Technology, Shandong University, Qingdao, China
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
qunliu at mail dot sdu dot edu dot cn

Yanhong Fan

School of Cyber Science and Technology, Shandong University, Qingdao, China
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
yanhongfan at sdu dot edu dot cn

Lixuan Wu

School of Cyber Science and Technology, Shandong University, Qingdao, China
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
lixuanwu at mail dot sdu dot edu dot cn

Boyun Li

School of Cyber Science and Technology, Shandong University, Qingdao, China
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
202316987 at mail dot sdu dot edu dot cn

Meiqin Wang

Quan Cheng Shandong Laboratory, Jinan, China
School of Cyber Science and Technology, Shandong University, Qingdao, China
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China
mqwang at sdu dot edu dot cn

Keywords: Quantum circuit Decision problem SAT S-box Linear layer

Abstract

In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.

References

[AMMR12]

Matthew Amy, Dmitrii L. Maslov, Michele Mosca, and Martin Rötteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32:818–830, 2012.

Google Scholar ePrint

[ASAM18]

Mishal Almazrooie, Azman Samsudin, Rosni Abdullah, and Kussay N. Mutter. Quantum reversible circuit of AES-128. Quantum Inf. Process., 17(5):112, 2018. https://doi.org/10.1007/s11128-018-1864-3.

Google Scholar ePrint

[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, 411–436. Springer, 2015. https://doi.org/10.1007/978-3-662-48800-3_17.

Google Scholar ePrint

[BCDM21]

Tim Beyne, Yu Long Chen, Christoph Dobraunig, and Bart Mennink. Multi-user security of the elephant v2 authenticated encryption mode. In Riham AlTawy and Andreas Hülsing, editors, Selected Areas in Cryptography - 28th International Conference, SAC 2021, Virtual Event, September 29 - October 1, 2021, Revised Selected Papers, volume 13203 of Lecture Notes in Computer Science, 155–178. Springer, 2021. https://doi.org/10.1007/978-3-030-99277-4_8.

Google Scholar ePrint

[BDK⁺21]

Anubhab Baksi, Vishnu Asutosh Dasu, Banashri Karmakar, Anupam Chattopadhyay, and Takanori Isobe. Three input exclusive-or gate support for boyar-peralta's algorithm. In Avishek Adhikari, Ralf Küsters, and Bart Preneel, editors, Progress in Cryptology - INDOCRYPT 2021 - 22nd International Conference on Cryptology in India, Jaipur, India, December 12-15, 2021, Proceedings, volume 13143 of Lecture Notes in Computer Science, 141–158. Springer, 2021.

Google Scholar ePrint

[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.

Google Scholar ePrint

[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, 123–153. Springer, 2016. https://doi.org/10.1007/978-3-662-53008-5_5.

Google Scholar ePrint

[BMP08]

Joan Boyar, Philip Matthews, and René Peralta. On the shortest linear straight-line program for computing linear forms. In Edward Ochmanski and Jerzy Tyszkiewicz, editors, Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, 168–179. Springer, 2008.

Google Scholar ePrint

[BMP13]

Joan Boyar, Philip Matthews, and René Peralta. Logic minimization techniques with applications to cryptology. J. Cryptol., 26(2):280–312, 2013.

Google Scholar ePrint

[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, 321–345. Springer, 2017. https://doi.org/10.1007/978-3-319-66787-4_16.

Google Scholar ePrint

[CBC23]

Matthew Chun, Anubhab Baksi, and Anupam Chattopadhyay. DORCIS: depth optimized quantum implementation of substitution boxes. IACR Cryptol. ePrint Arch., pages 286, 2023.

Google Scholar ePrint

[CJL⁺16]

Lidong Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. 2016-04-28 2016. https://doi.org/https://doi.org/10.6028/NIST.IR.8105.

Google Scholar ePrint

[DBSC19]

Vishnu Asutosh Dasu, Anubhab Baksi, Sumanta Sarkar, and Anupam Chattopadhyay. LIGHTER-R: optimized reversible circuit implementation for sboxes. In 32nd IEEE International System-on-Chip Conference, SOCC 2019, Singapore, September 3-6, 2019, 260–265. IEEE, 2019. https://doi.org/10.1109/SOCC46988.2019.1570548320.

Google Scholar ePrint

[GLRS15]

Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt. Applying grover's algorithm to aes: quantum resource estimates. 2015.

Google Scholar ePrint

[Gro96]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, 212–219. ACM, 1996. https://doi.org/10.1145/237814.237866.

Google Scholar ePrint

[HS22]

Zhenyu Huang and Siwei Sun. Synthesizing quantum circuits of AES with lower t-depth and less qubits. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part III, volume 13793 of Lecture Notes in Computer Science, 614–644. Springer, 2022. https://doi.org/10.1007/978-3-031-22969-5_21.

Google Scholar ePrint

[JBS⁺22]

Kyungbae Jang, Anubhab Baksi, Gyeongju Song, Hyunji Kim, Hwajeong Seo, and Anupam Chattopadhyay. Quantum analysis of AES. IACR Cryptol. ePrint Arch., pages 683, 2022. https://doi.org/?

Google Scholar ePrint

[JNRV20]

Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing grover oracles for quantum key search on AES and lowmc. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, 280–310. Springer, 2020. https://doi.org/10.1007/978-3-030-45724-2_10.

Google Scholar ePrint

[JPST17]

Jérémy Jean, Thomas Peyrin, Siang Meng Sim, and Jade Tourteaux. Optimizing implementations of lightweight building blocks. IACR Trans. Symmetric Cryptol., 2017:130–168, 2017.

Google Scholar ePrint

[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.

Google Scholar ePrint

[LPS20]

Brandon Langenberg, Hai Pham, and Rainer Steinwandt. Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Transactions on Quantum Engineering, 1():1–12, 2020. https://doi.org/10.1109/TQE.2020.2965697.

Google Scholar ePrint

[LPZW23]

Qun Liu, Bart Preneel, Zheng Zhao, and Meiqin Wang. Improved quantum circuits for AES: reducing the depth and the number of qubits. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part III, volume 14440 of Lecture Notes in Computer Science, 67–98. Springer, 2023. https://doi.org/10.1007/978-981-99-8727-6_3.

Google Scholar ePrint

[LWF⁺22]

Qun Liu, Weijia Wang, Yanhong Fan, Lixuan Wu, Ling Sun, and Meiqin Wang. Towards low-latency implementation of linear layers. IACR Trans. Symmetric Cryptol., 2022(1):158–182, 2022.

Google Scholar ePrint

[LWH⁺21]

Zhenyu Lu, Weijia Wang, Kai Hu, Yanhong Fan, Lixuan Wu, and Meiqin Wang. Pushing the limits: searching for implementations with the smallest area for lightweight s-boxes. In Avishek Adhikari, Ralf Küsters, and Bart Preneel, editors, Progress in Cryptology - INDOCRYPT 2021 - 22nd International Conference on Cryptology in India, Jaipur, India, December 12-15, 2021, Proceedings, volume 13143 of Lecture Notes in Computer Science, 159–178. Springer, 2021. https://doi.org/10.1007/978-3-030-92518-5_8.

Google Scholar ePrint

[LWS⁺22]

Qun Liu, Weijia Wang, Ling Sun, Yanhong Fan, Lixuan Wu, and Meiqin Wang. More inputs makes difference: implementations of linear layers using gates with more than two inputs. IACR Transactions on Symmetric Cryptology, 2022(2):351–378, Jun. 2022.

Google Scholar ePrint

[LXX⁺23]

Da Lin, Zejun Xiang, Runqing Xu, Shasha Zhang, and Xiangyong Zeng. Optimized quantum implementation of aes. 2023.

Google Scholar ePrint

[NC01]

Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Volume 2. Cambridge university press Cambridge, 2001.

Google Scholar ePrint

[Sel13]

Peter Selinger. Quantum circuits of t-depth one. Physical Review A, 87(4):042302, 2013. https://doi.org/?

Google Scholar ePrint

[SM13]

Mehdi Saeedi and Igor L. Markov. Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys, 45(2):1–34, February 2013. https://doi.org/10.1145/2431211.2431220.

Google Scholar ePrint

[SOT⁺21]

Layth Sliman, Tasnime Omrani, Zahir Tari, Abed Ellatif Samhat, and Rhouma Rhouma. Towards an ultra lightweight block ciphers for internet of things. J. Inf. Secur. Appl., 61:102897, 2021. https://doi.org/10.1016/j.jisa.2021.102897.

Google Scholar ePrint

[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, 140–160. Springer, 2016. https://doi.org/10.1007/978-3-662-52993-5_8.

Google Scholar ePrint

[TP20]

Quan Quan Tan and Thomas Peyrin. Improved heuristics for short linear programs. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2020(1):203–230, 2020.

Google Scholar ePrint

[WL21]

Qinglin Wang and Jiqiang Lu. Fault analysis of the ARIA and ublock block ciphers. In Ian McLoughlin, editor, 2021 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI), Singapore, December 11-12, 2021, 1–6. IEEE, 2021. https://doi.org/10.1109/SOLI54607.2021.9672378.

Google Scholar ePrint

[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, 327–344. 2011. https://doi.org/10.1007/978-3-642-21554-4_19.

Google Scholar ePrint

[XZL⁺20]

Zejun Xiang, Xiangyong Zeng, Da Lin, Zhenzhen Bao, and Shasha Zhang. Optimizing implementations of linear layers. IACR Trans. Symmetric Cryptol., 2020(2):120–145, 2020. https://doi.org/10.13154/tosc.v2020.i2.120-145.

Google Scholar ePrint

[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. https://doi.org/10.1007/s11432-015-5459-7.

Google Scholar ePrint

[ZWS⁺20]

Jian Zou, Zihao Wei, Siwei Sun, Ximeng Liu, and Wenling Wu. Quantum circuit implementations of AES with fewer qubits. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part II, volume 12492 of Lecture Notes in Computer Science, 697–726. Springer, 2020. https://doi.org/10.1007/978-3-030-64834-3_24.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/anmmp-4c2h

History

Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Jingwen Chen, Qun Liu, Yanhong Fan, Lixuan Wu, Boyun Li, and Meiqin Wang, "New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/anmmp-4c2h.

License

Copyright is held by the author(s)

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

@article{CiC-1-1-31,
    author = "Chen, Jingwen and Liu, Qun and Fan, Yanhong and Wu, Lixuan and Li, Boyun and Wang, Meiqin",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "New {SAT}-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/anmmp-4c2h"
}

TY - JOUR
AU - Chen, Jingwen
AU - Liu, Qun
AU - Fan, Yanhong
AU - Wu, Lixuan
AU - Li, Boyun
AU - Wang, Meiqin
PY  - 2024
TI  - New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/anmmp-4c2h
UR  - https://doi.org/10.62056/anmmp-4c2h
AB  - <p>In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.</p>
ER  -

Jingwen Chen, Qun Liu, Yanhong Fan, Lixuan Wu, Boyun Li, and Meiqin Wang, "New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/anmmp-4c2h.