Efficient Quantum Circuit of Proth Number Modular Multiplication

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

doi:10.1007/978-3-031-08896-4_21

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 proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers
Editors	Jong Hwan Park, Seung-Hyun Seo
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	403-417
Number of pages	15
ISBN (Print)	9783031088957
DOIs	https://doi.org/10.1007/978-3-031-08896-4_21
Publication status	Published - 2022
Event	24th International Conference on Information Security and Cryptology, ICISC 2021 - Seoul, Korea, Republic of Duration: 2021 Dec 1 → 2021 Dec 3

Publication series

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

Conference

Conference	24th International Conference on Information Security and Cryptology, ICISC 2021
Country/Territory	Korea, Republic of
City	Seoul
Period	21/12/1 → 21/12/3

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.

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-08896-4_21

Cite this

Jeon, C., Heo, D., Lee, M. H., Kim, S., & Hong, S. (2022). Efficient Quantum Circuit of Proth Number Modular Multiplication. In J. H. Park, & S.-H. Seo (Eds.), Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers (pp. 403-417). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13218 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-08896-4_21

Efficient Quantum Circuit of Proth Number Modular Multiplication. / Jeon, Chanho; Heo, Donghoe; Lee, Myeong Hoon et al.
Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers. ed. / Jong Hwan Park; Seung-Hyun Seo. Springer Science and Business Media Deutschland GmbH, 2022. p. 403-417 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13218 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Jeon, C, Heo, D, Lee, MH, Kim, S & Hong, S 2022, Efficient Quantum Circuit of Proth Number Modular Multiplication. in JH Park & S-H Seo (eds), Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13218 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 403-417, 24th International Conference on Information Security and Cryptology, ICISC 2021, Seoul, Korea, Republic of, 21/12/1. https://doi.org/10.1007/978-3-031-08896-4_21

Jeon C, Heo D, Lee MH, Kim S, Hong S. Efficient Quantum Circuit of Proth Number Modular Multiplication. In Park JH, Seo SH, editors, Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2022. p. 403-417. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-08896-4_21

Jeon, Chanho ; Heo, Donghoe ; Lee, Myeong Hoon et al. / Efficient Quantum Circuit of Proth Number Modular Multiplication. Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers. editor / Jong Hwan Park ; Seung-Hyun Seo. Springer Science and Business Media Deutschland GmbH, 2022. pp. 403-417 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0c1164649577435f8d732a2bf8616f3e,

title = "Efficient Quantum Circuit of Proth Number Modular Multiplication",

abstract = "The efficient quantum circuit of Post Quantum Cryptography (PQC) impacts both performance and security because Grover{\textquoteright}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.{\textquoteright}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.{\textquoteright}s.",

keywords = "CDKM adder, Lattice, Moduluar multiplication, Number theoretic transform, Proth number, Quantum circuit",

author = "Chanho Jeon and Donghoe Heo and Lee, {Myeong Hoon} and Sunyeop Kim and Seokhie Hong",

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: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 24th International Conference on Information Security and Cryptology, ICISC 2021 ; Conference date: 01-12-2021 Through 03-12-2021",

year = "2022",

doi = "10.1007/978-3-031-08896-4_21",

language = "English",

isbn = "9783031088957",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "403--417",

editor = "Park, {Jong Hwan} and Seung-Hyun Seo",

booktitle = "Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - Efficient Quantum Circuit of Proth Number Modular Multiplication

AU - Jeon, Chanho

AU - Heo, Donghoe

AU - Lee, Myeong Hoon

AU - Kim, Sunyeop

AU - Hong, Seokhie

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

PY - 2022

Y1 - 2022

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

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

KW - CDKM adder

KW - Lattice

KW - Moduluar multiplication

KW - Number theoretic transform

KW - Proth number

KW - Quantum circuit

UR - http://www.scopus.com/inward/record.url?scp=85135170675&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-08896-4_21

DO - 10.1007/978-3-031-08896-4_21

M3 - Conference contribution

AN - SCOPUS:85135170675

SN - 9783031088957

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 403

EP - 417

BT - Information Security and Cryptology – ICISC 2021 - 24th International Conference, Revised Selected Papers

A2 - Park, Jong Hwan

A2 - Seo, Seung-Hyun

PB - Springer Science and Business Media Deutschland GmbH

T2 - 24th International Conference on Information Security and Cryptology, ICISC 2021

Y2 - 1 December 2021 through 3 December 2021

ER -