Efficient Quantum Circuit of Proth Number Modular Multiplication

Chanho Jeon, Donghoe Heo, Myeong Hoon Lee, Sunyeop Kim, Seokhie Hong

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The efficient quantum circuit of Post Quantum Cryptography (PQC) impacts both performance and security because Grover’s algorithm, upon which various attacks are based, also requires a circuit. Therefore, the implementation of cryptographic operations in a quantum environment is considered to be one of the main concerns for PQC. Most lattice-based cryptography schemes employ Number Theoretic Transform (NTT). Moreover, NTT can be efficiently implemented using the modulus p= k· 2 m+ 1, called Proth number, and there is a need to elaborate on the quantum circuit for a modular multiplication over p. However, to the best of our knowledge, only quantum circuits for modular multiplication of the general odd modulus have been proposed, and quantum circuits for specific odd modulus are not presented. Thus, this paper addresses this issue and presents a new optimized quantum circuit for Proth Number Modular Multiplication (PNMM) which is faster than Rines et al.’s modular multiplication circuit. According to the evaluation with commonly used modulus parameters for lattice-based cryptography, our circuit requires an approximately 22%–45% less T-depth than that of Rines et al.’s.

Original languageEnglish
Title of host publicationInformation Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers
EditorsJong Hwan Park, Seung-Hyun Seo
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages15
ISBN (Print)9783031088957
Publication statusPublished - 2022
Event24th International Conference on Information Security and Cryptology, ICISC 2021 - Seoul, Korea, Republic of
Duration: 2021 Dec 12021 Dec 3

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13218 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Information Security and Cryptology, ICISC 2021
Country/TerritoryKorea, Republic of

Bibliographical note

Funding Information:
Acknowledgments. This work was supported by Institute for Information and communications Technology Planning and Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2019-0-00033, Study on Quantum Security Evaluation of Cryptography based on Computational Quantum Complexity).

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.


  • CDKM adder
  • Lattice
  • Moduluar multiplication
  • Number theoretic transform
  • Proth number
  • Quantum circuit

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient Quantum Circuit of Proth Number Modular Multiplication'. Together they form a unique fingerprint.

Cite this