{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T17:41:44Z","timestamp":1773337304754,"version":"3.50.1"},"reference-count":31,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T00:00:00Z","timestamp":1678838400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Institute for Information &amp; communications Technology Planning &amp; Evaluation (IITP)","award":["2019-0-00033"],"award-info":[{"award-number":["2019-0-00033"]}]},{"name":"Institute for Information &amp; communications Technology Planning &amp; Evaluation (IITP)","award":["2018-0-00264"],"award-info":[{"award-number":["2018-0-00264"]}]},{"name":"Institute for Information &amp; communications Technology Promotion(IITP)","award":["2019-0-00033"],"award-info":[{"award-number":["2019-0-00033"]}]},{"name":"Institute for Information &amp; communications Technology Promotion(IITP)","award":["2018-0-00264"],"award-info":[{"award-number":["2018-0-00264"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The Shor\u2019s algorithm can find solutions to the discrete logarithm problem on binary elliptic curves in polynomial time. A major challenge in implementing Shor\u2019s algorithm is the overhead of representing and performing arithmetic on binary elliptic curves using quantum circuits. Multiplication of binary fields is one of the critical operations in the context of elliptic curve arithmetic, and it is especially costly in the quantum setting. Our goal in this paper is to optimize quantum multiplication in the binary field. In the past, efforts to optimize quantum multiplication have centred on reducing the Toffoli gate count or qubits required. However, despite the fact that circuit depth is an important metric for indicating the performance of a quantum circuit, previous studies have lacked sufficient consideration for reducing circuit depth. Our approach to optimizing quantum multiplication differs from previous work in that we aim at reducing the Toffoli depth and full depth. To optimize quantum multiplication, we adopt the Karatsuba multiplication method which is based on the divide-and-conquer approach. In summary, we present an optimized quantum multiplication that has a Toffoli depth of one. Additionally, the full depth of the quantum circuit is also reduced thanks to our Toffoli depth optimization strategy. To demonstrate the effectiveness of our proposed method, we evaluate its performance using various metrics such as the qubit count, quantum gates, and circuit depth, as well as the qubits-depth product. These metrics provide insight into the resource requirements and complexity of the method. Our work achieves the lowest Toffoli depth, full depth, and the best trade-off performance for quantum multiplication. Further, our multiplication is more effective when not used in stand-alone cases. We show this effectiveness by using our multiplication to the Itoh\u2013Tsujii algorithm-based inversion of F(x8+x4+x3+x+1).<\/jats:p>","DOI":"10.3390\/s23063156","type":"journal-article","created":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T03:14:35Z","timestamp":1678936475000},"page":"3156","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Quantum Binary Field Multiplication with Optimized Toffoli Depth and Extension to Quantum Inversion"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5963-7127","authenticated-orcid":false,"given":"Kyungbae","family":"Jang","sequence":"first","affiliation":[{"name":"Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wonwoong","family":"Kim","sequence":"additional","affiliation":[{"name":"Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sejin","family":"Lim","sequence":"additional","affiliation":[{"name":"Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yeajun","family":"Kang","sequence":"additional","affiliation":[{"name":"Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9007-2280","authenticated-orcid":false,"given":"Yujin","family":"Yang","sequence":"additional","affiliation":[{"name":"Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0069-9061","authenticated-orcid":false,"given":"Hwajeong","family":"Seo","sequence":"additional","affiliation":[{"name":"Division of IT Convergence Engineering, Hansung University, Seoul 02876, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/S0036144598347011","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"41","author":"Shor","year":"1999","journal-title":"SIAM Rev."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zou, J., Wei, Z., Sun, S., Liu, X., and Wu, W. (2020, January 7\u201311). Quantum circuit implementations of AES with fewer qubits. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, Republic of Korea.","DOI":"10.1007\/978-3-030-64834-3_24"},{"key":"ref_4","first-page":"1","article-title":"Quantum search for scaled hash function preimages","volume":"20","author":"Bellini","year":"2021","journal-title":"Quantum Inf. Process."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Bijwe, S., Chauhan, A.K., and Sanadhya, S.K. (2022, January 28\u201330). Implementing Grover Oracle for Lightweight Block Ciphers Under Depth Constraints. Proceedings of the Australasian Conference on Information Security and Privacy, Wollongong, Australia.","DOI":"10.1007\/978-3-031-22301-3_5"},{"key":"ref_6","unstructured":"Yadav, T., Kumar, M., Kumar, A., and Pal, S.K. (2022). A Pratical-Quantum Differential Attack on Block Ciphers. Cryptol. Eprint Arch., ePrint:2022\/489."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Jaques, S., Naehrig, M., Roetteler, M., and Virdia, F. (2020, January 10\u201314). Implementing Grover oracles for quantum key search on AES and LowMC. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia.","DOI":"10.1007\/978-3-030-45724-2_10"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Huang, Z., and Sun, S. (2022). Synthesizing Quantum Circuits of AES with Lower T-depth and Less Qubits. Cryptol. Eprint Arch., ePrint:2022\/620.","DOI":"10.1007\/978-3-031-22969-5_21"},{"key":"ref_9","unstructured":"Jang, K., Baksi, A., Kim, H., Song, G., Seo, H., and Chattopadhyay, A. (2022). Quantum analysis of aes. Cryptol. Eprint Arch., ePrint:2022\/683."},{"key":"ref_10","unstructured":"NIST (2023, January 01). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process, Available online: https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/call-for-proposals-final-dec-2016.pdf."},{"key":"ref_11","first-page":"60","article-title":"Design technique for secure embedded devices: Application for creation of integrated cyber-physical security system","volume":"7","author":"Desnitsky","year":"2016","journal-title":"J. Wirel. Mob. Netw. Ubiquitous Comput. Dependable Appl."},{"key":"ref_12","first-page":"31","article-title":"Secure and Scalable Deployment of Resource Public Key Infrastructure (RPKI)","volume":"8","author":"Yan","year":"2018","journal-title":"J. Internet Serv. Inf. Secur."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"H\u00e4ner, T., Roetteler, M., and Svore, K.M. (2016). Factoring using 2n + 2 qubits with Toffoli based modular multiplication. arXiv.","DOI":"10.26421\/QIC17.7-8-7"},{"key":"ref_14","unstructured":"Gidney, C. (2017). Factoring with n + 2 clean qubits and n \u2212 1 dirty qubits. arXiv."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Roetteler, M., Naehrig, M., Svore, K.M., and Lauter, K. (2017, January 3\u20137). Quantum resource estimates for computing elliptic curve discrete logarithms. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China.","DOI":"10.1007\/978-3-319-70697-9_9"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"H\u00e4ner, T., Jaques, S., Naehrig, M., Roetteler, M., and Soeken, M. (2020, January 15\u201317). Improved quantum circuits for elliptic curve discrete logarithms. Proceedings of the International Conference on Post-Quantum Cryptography, Paris, France.","DOI":"10.1007\/978-3-030-44223-1_23"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Banegas, G., Bernstein, D.J., Van Hoof, I., and Lange, T. (2020). Concrete quantum cryptanalysis of binary elliptic curves. Cryptol. Eprint Arch., ePrint:2020\/1296.","DOI":"10.46586\/tches.v2021.i1.451-472"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Van Hoof, I. (2019). Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count. arXiv.","DOI":"10.26421\/QIC20.9-10-1"},{"key":"ref_19","unstructured":"Cheung, D., Maslov, D., Mathew, J., and Pradhan, D.K. (February, January 30). On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography. Proceedings of the Workshop on Quantum Computation, Communication, and Cryptography, Tokyo, Japan."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2373","DOI":"10.1007\/s11128-015-0993-1","article-title":"Quantum circuits for F2n-multiplication with subquadratic gate count","volume":"14","author":"Kepley","year":"2015","journal-title":"Quantum Inf. Process."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Jang, K., Choi, S.J., Kwon, H., Hu, Z., and Seo, H. (2020, January 20\u201322). Impact of Optimized Operations A\u00b7B, A\u00b7C for Binary Field Inversion on Quantum Computers. Proceedings of the International Conference on Information Security Applications, Nanjing, China.","DOI":"10.1007\/978-3-030-65299-9_12"},{"key":"ref_22","unstructured":"Jang, K., Song, G.J., Kim, H., Kwon, H., Lee, W.K., Hu, Z., and Seo, H. (2021). Binary Field Montgomery Multiplication on Quantum Computers. Cryptol. Eprint Arch., ePrint:2021\/980."},{"key":"ref_23","unstructured":"Bhattacharjee, D., and Chattopadhyay, A. (2017). Depth-optimal quantum circuit placement for arbitrary topologies. arXiv."},{"key":"ref_24","unstructured":"Cross, A. (2018, January 5\u20139). The IBM Q experience and Qiskit open-source quantum computing software. Proceedings of the APS March Meeting Abstracts, Los Angeles, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Svore, K., Geller, A., Troyer, M., Azariah, J., Granade, C., Heim, B., Kliuchnikov, V., Mykhailova, M., Paz, A., and Roetteler, M. (2018, January 24). Q# enabling scalable quantum computing and development with a high-level dsl. Proceedings of the Real World Domain Specific Languages Workshop 2018, Vienna, Austria.","DOI":"10.1145\/3183895.3183901"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"49","DOI":"10.22331\/q-2018-01-31-49","article-title":"ProjectQ: An open source software framework for quantum computing","volume":"2","author":"Steiger","year":"2018","journal-title":"Quantum"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0890-5401(88)90024-7","article-title":"A fast algorithm for computing multiplicative inverses in GF(2m) using normal basis","volume":"78","author":"Itoh","year":"1988","journal-title":"Inf. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Jang, k., Kim, W., Lim, S., Kang, Y., Yang, Y., and Seo, H. (2022, January 11\u201313). Optimized implementation of quantum binary field multiplication with toffoli depth one. Proceedings of the International Conference on Information Security Applications, Virtually.","DOI":"10.1007\/978-3-031-25659-2_18"},{"key":"ref_29","first-page":"595","article-title":"Multiplication of multidigit numbers on automata","volume":"7","author":"Karatsuba","year":"1963","journal-title":"Sov. Phys. Dokl."},{"key":"ref_30","unstructured":"KIM, S., KIM, I., Kim, S., and Hong, S. (2022). Toffoli gate count Optimized Space-Efficient Quantum Circuit for Binary Field Multiplication. Cryptol. Eprint Arch., ePrint:2022\/1095."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1109\/TCAD.2013.2244643","article-title":"A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits","volume":"32","author":"Amy","year":"2013","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/6\/3156\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:56:08Z","timestamp":1760122568000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/6\/3156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,15]]},"references-count":31,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["s23063156"],"URL":"https:\/\/doi.org\/10.3390\/s23063156","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,15]]}}}