{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T20:35:04Z","timestamp":1770842104996,"version":"3.50.1"},"reference-count":37,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,3,5]]},"abstract":"<jats: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.<\/jats:p>","DOI":"10.62056\/anmmp-4c2h","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T19:27:10Z","timestamp":1712690830000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":9,"title":["New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-3247-7601","authenticated-orcid":false,"given":"Jingwen","family":"Chen","sequence":"first","affiliation":[{"name":"School of Cyber Science and Technology, Shandong University, Qingdao","place":["China"]},{"name":"Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan","place":["China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6740-8223","authenticated-orcid":false,"given":"Qun","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Cyber Science and Technology, Shandong University, Qingdao","place":["China"]},{"name":"Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan","place":["China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7080-8615","authenticated-orcid":false,"given":"Yanhong","family":"Fan","sequence":"additional","affiliation":[{"name":"School of Cyber Science and Technology, Shandong University, Qingdao","place":["China"]},{"name":"Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan","place":["China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5020-4363","authenticated-orcid":false,"given":"Lixuan","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Cyber Science and Technology, Shandong University, Qingdao","place":["China"]},{"name":"Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan","place":["China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4092-9630","authenticated-orcid":false,"given":"Boyun","family":"Li","sequence":"additional","affiliation":[{"name":"School of Cyber Science and Technology, Shandong University, Qingdao","place":["China"]},{"name":"Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan","place":["China"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1580-6544","authenticated-orcid":false,"given":"Meiqin","family":"Wang","sequence":"additional","affiliation":[{"name":"Quan Cheng Shandong Laboratory, Jinan","place":["China"]},{"name":"School of Cyber Science and Technology, Shandong University, Qingdao","place":["China"]},{"name":"Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan","place":["China"]}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:214441","article-title":"Report on Post-Quantum Cryptography","author":"Lidong Chen","year":"2016"},{"key":"ref2:DBLP:conf\/stoc\/Grover96","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/237814.237866","article-title":"A Fast Quantum Mechanical Algorithm for Database Search","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on\n  the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996","author":"Lov K. Grover","year":"1996"},{"key":"ref3:DBLP:conf\/asiacrypt\/BanikBISHAR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-662-48800-3_17","article-title":"Midori: A Block Cipher for Low Energy","volume-title":"Advances in Cryptology - ASIACRYPT 2015 - 21st\n  International Conference on the Theory and Application of Cryptology and\n  Information Security, Auckland, New Zealand, November 29 - December 3, 2015,\n  Proceedings, Part II","volume":"9453","author":"Subhadeep Banik","year":"2015"},{"key":"ref4:Jean2017OptimizingIO","doi-asserted-by":"crossref","first-page":"130","DOI":"10.46586\/tosc.v2017.i4.130-168","article-title":"Optimizing Implementations of Lightweight Building Blocks","volume":"2017","author":"J\u00e9r\u00e9my Jean","year":"2017","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref5:DBLP:journals\/tosc\/BaoGLS19","first-page":"330","article-title":"PEIGEN - a Platform for Evaluation, Implementation, and\n  Generation of S-boxes","volume":"2019","author":"Zhenzhen Bao","year":"2019","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref6:Boyar2008","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/978-3-540-85238-4_13","article-title":"On the Shortest Linear Straight-Line Program for Computing\n  Linear Forms","volume-title":"Mathematical Foundations of Computer Science 2008, 33rd\n  International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008,\n  Proceedings","volume":"5162","author":"Joan Boyar","year":"2008"},{"key":"ref7:Boyar2013","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/s00145-012-9124-7","article-title":"Logic Minimization Techniques with Applications to\n  Cryptology","volume":"26","author":"Joan Boyar","year":"2013","journal-title":"J. Cryptol."},{"key":"ref8:Kranz2017","doi-asserted-by":"crossref","first-page":"188","DOI":"10.46586\/tosc.v2017.i4.188-211","article-title":"Shorter Linear Straight-Line Programs for MDS Matrices","volume":"2017","author":"Thorsten Kranz","year":"2017","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref9:Tan2020","first-page":"203","article-title":"Improved Heuristics for Short Linear Programs","volume":"2020","author":"Quan Quan Tan","year":"2020","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref10:DBLP:journals\/tosc\/XiangZLBZ20","doi-asserted-by":"publisher","first-page":"120","DOI":"10.13154\/tosc.v2020.i2.120-145","article-title":"Optimizing Implementations of Linear Layers","volume":"2020","author":"Zejun Xiang","year":"2020","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref11:DBLP:conf\/indocrypt\/BaksiDKCI21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-3-030-92518-5_7","article-title":"Three Input Exclusive-OR Gate Support for Boyar-Peralta's\n  Algorithm","volume-title":"Progress in Cryptology - INDOCRYPT 2021 - 22nd\n  International Conference on Cryptology in India, Jaipur, India, December\n  12-15, 2021, Proceedings","volume":"13143","author":"Anubhab Baksi","year":"2021"},{"key":"ref12:DBLP:journals\/tosc\/LiuWFWSW22","first-page":"158","article-title":"Towards Low-Latency Implementation of Linear Layers","volume":"2022","author":"Qun Liu","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref13:Liu_Wang_Sun_Fan_Wu_Wang_2022","first-page":"351","article-title":"More Inputs Makes Difference: Implementations of Linear\n  Layers Using Gates with More Than Two Inputs","volume":"2022","author":"Qun Liu","year":"2022","journal-title":"IACR Transactions on Symmetric Cryptology"},{"key":"ref14:grassl2015applying","article-title":"Applying Grover's algorithm to AES: quantum resource\n  estimates","author":"Markus Grassl","year":"2015"},{"key":"ref15:8961201","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2020.2965697","article-title":"Reducing the Cost of Implementing the Advanced Encryption\n  Standard as a Quantum Circuit","volume":"1","author":"Brandon Langenberg","year":"2020","journal-title":"IEEE Transactions on Quantum Engineering"},{"key":"ref16:DBLP:journals\/qip\/AlmazrooieSAM18","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/s11128-018-1864-3","article-title":"Quantum reversible circuit of AES-128","volume":"17","author":"Mishal Almazrooie","year":"2018","journal-title":"Quantum Inf. Process."},{"key":"ref17:DBLP:conf\/eurocrypt\/JaquesNRV20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-030-45724-2_10","article-title":"Implementing Grover Oracles for Quantum Key Search on AES\n  and LowMC","volume-title":"Advances in Cryptology - EUROCRYPT 2020 - 39th Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II","volume":"12106","author":"Samuel Jaques","year":"2020"},{"key":"ref18:DBLP:conf\/asiacrypt\/ZouWSLW20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/978-3-030-64834-3_24","article-title":"Quantum Circuit Implementations of AES with Fewer Qubits","volume-title":"Advances in Cryptology - ASIACRYPT 2020 - 26th\n  International Conference on the Theory and Application of Cryptology and\n  Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings,\n  Part II","volume":"12492","author":"Jian Zou","year":"2020"},{"key":"ref19:DBLP:conf\/asiacrypt\/HuangS22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1007\/978-3-031-22969-5_21","article-title":"Synthesizing Quantum Circuits of AES with Lower T-depth\n  and Less Qubits","volume-title":"Advances in Cryptology - ASIACRYPT 2022 - 28th\n  International Conference on the Theory and Application of Cryptology and\n  Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part\n  III","volume":"13793","author":"Zhenyu Huang","year":"2022"},{"key":"ref20:DBLP:journals\/iacr\/JangBSKSC22","first-page":"683","article-title":"Quantum Analysis of AES","author":"Kyungbae Jang","year":"2022","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref21:DBLP:conf\/asiacrypt\/LiuPZW23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-981-99-8727-6_3","article-title":"Improved Quantum Circuits for AES: Reducing the Depth and\n  the Number of Qubits","volume-title":"Advances in Cryptology - ASIACRYPT 2023 - 29th\n  International Conference on the Theory and Application of Cryptology and\n  Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part\n  III","volume":"14440","author":"Qun Liu","year":"2023"},{"key":"ref22:DBLP:conf\/socc\/DasuBSC19","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/SOCC46988.2019.1570548320","article-title":"LIGHTER-R: Optimized Reversible Circuit Implementation For\n  SBoxes","volume-title":"32nd IEEE International System-on-Chip Conference, SOCC\n  2019, Singapore, September 3-6, 2019","author":"Vishnu Asutosh Dasu","year":"2019"},{"key":"ref23:DBLP:journals\/iacr\/ChunBC23","first-page":"286","article-title":"DORCIS: Depth Optimized Quantum Implementation of\n  Substitution Boxes","author":"Matthew Chun","year":"2023","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref24:DBLP:conf\/indocrypt\/LuWHFWW21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-030-92518-5_8","article-title":"Pushing the Limits: Searching for Implementations with the\n  Smallest Area for Lightweight S-Boxes","volume-title":"Progress in Cryptology - INDOCRYPT 2021 - 22nd\n  International Conference on Cryptology in India, Jaipur, India, December\n  12-15, 2021, Proceedings","volume":"13143","author":"Zhenyu Lu","year":"2021"},{"key":"ref25:DBLP:conf\/fse\/Stoffelen16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-662-52993-5_8","article-title":"Optimizing S-Box Implementations for Several Criteria Using\n  SAT Solvers","volume-title":"Fast Software Encryption - 23rd International Conference,\n  FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers","volume":"9783","author":"Ko Stoffelen","year":"2016"},{"key":"ref26:DBLP:journals\/chinaf\/ZhangBLR0V15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-015-5459-7","article-title":"RECTANGLE: a bit-slice lightweight block cipher suitable\n  for multiple platforms","volume":"58","author":"Wentao Zhang","year":"2015","journal-title":"Sci. China Inf. Sci."},{"key":"ref27:DBLP:conf\/ches\/BanikPPSST17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-319-66787-4_16","article-title":"GIFT: A Small Present - Towards Reaching the Limit of\n  Lightweight Encryption","volume-title":"Cryptographic Hardware and Embedded Systems - CHES 2017 -\n  19th International Conference, Taipei, Taiwan, September 25-28, 2017,\n  Proceedings","volume":"10529","author":"Subhadeep Banik","year":"2017"},{"key":"ref28:DBLP:journals\/istr\/SlimanOTSR21","doi-asserted-by":"publisher","first-page":"102897","DOI":"10.1016\/j.jisa.2021.102897","article-title":"Towards an ultra lightweight block ciphers for Internet of\n  Things","volume":"61","author":"Layth Sliman","year":"2021","journal-title":"J. Inf. Secur. Appl."},{"key":"ref29:DBLP:conf\/crypto\/BeierleJKL0PSSS16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-662-53008-5_5","article-title":"The SKINNY Family of Block Ciphers and Its Low-Latency\n  Variant MANTIS","volume-title":"Advances in Cryptology - CRYPTO 2016 - 36th Annual\n  International Cryptology Conference, Santa Barbara, CA, USA, August 14-18,\n  2016, Proceedings, Part II","volume":"9815","author":"Christof Beierle","year":"2016"},{"key":"ref30:cryptoeprint:2023\/146","article-title":"Optimized Quantum Implementation of AES","author":"Da Lin","year":"2023"},{"key":"ref31:DBLP:conf\/sacrypt\/BeyneCDM21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-030-99277-4_8","article-title":"Multi-user Security of the Elephant v2 Authenticated\n  Encryption Mode","volume-title":"Selected Areas in Cryptography - 28th International\n  Conference, SAC 2021, Virtual Event, September 29 - October 1, 2021,\n  Revised Selected Papers","volume":"13203","author":"Tim Beyne","year":"2021"},{"key":"ref32:DBLP:conf\/acns\/WuZ11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-21554-4_19","article-title":"LBlock: A Lightweight Block Cipher","volume-title":"Applied Cryptography and Network Security - 9th\n  International Conference, ACNS 2011, Nerja, Spain, June 7-10, 2011.\n  Proceedings","volume":"6715","author":"Wenling Wu","year":"2011"},{"key":"ref33:DBLP:conf\/soli\/WangL21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/SOLI54607.2021.9672378","article-title":"Fault Analysis of the ARIA and uBlock Block Ciphers","volume-title":"2021 IEEE International Conference on Service Operations\n  and Logistics, and Informatics (SOLI), Singapore, December 11-12, 2021","author":"Qinglin Wang","year":"2021"},{"key":"ref34:selinger2013quantum","doi-asserted-by":"crossref","first-page":"42302","DOI":"10.1103\/PhysRevA.87.042302","article-title":"Quantum circuits of T-depth one","volume":"87","author":"Peter Selinger","year":"2013","journal-title":"Physical Review A"},{"key":"ref35:Amy2012AMA","first-page":"818","article-title":"A Meet-in-the-Middle Algorithm for Fast Synthesis of\n  Depth-Optimal Quantum Circuits","volume":"32","author":"Matthew Amy","year":"2012","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated\n  Circuits and Systems"},{"key":"ref36:Saeedi_2013","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2431211.2431220","article-title":"Synthesis and optimization of reversible circuits\u2014a\n  survey","volume":"45","author":"Mehdi Saeedi","year":"2013","journal-title":"ACM Computing Surveys","ISSN":"https:\/\/id.crossref.org\/issn\/1557-7341","issn-type":"electronic"},{"key":"ref37:DBLP:books\/daglib\/0046438","article-title":"Quantum computation and quantum information","volume":"2","author":"Isaac L Nielsen Michael A and Chuang","year":"2001"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:25:24Z","timestamp":1733865924000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":37,"URL":"https:\/\/doi.org\/10.62056\/anmmp-4c2h","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2024-01-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-101"}}