본문 바로가기

Space and Time-Efficient Quantum Multiplier in Post Quantum Cryptography Era

문서 유형
연구출판물 · 학술지 논문
등재
SCIEScopus
저널 순위
JCR Q2Scopus Q1
저널
IEEE ACCESS11 · pp.21848 · 2023
피인용
Web of Science 22Scopus 37
FWCI (Scopus)
2.45
JCR IF
JCR 2022 3.9
ISSN
2169-3536

저자

  1. 데디 셉토노 차투르제1저자Pusan Natl Univ, IoT Res Ctr, Busan 609735, South Korea
  2. 와다니 리니 위스누Pusan Natl Univ, Sch Comp Sci & Engn, Pusan 609735, South Korea
  3. 라라사티 하라스타 타티마Pusan Natl Univ, Sch Comp Sci & Engn, Pusan 609735, South Korea
  4. 김호원교신저자Pusan Natl Univ, Sch Comp Sci & Engn, Pusan 609735, South Korea

초록

This paper examines the asymptotic performance of multiplication and the cost of quantum implementation for the Naive schoolbook, Karatsuba, and Toom-Cook methods in the classical and quantum cases and provides insights into multiplication roles in the post-quantum cryptography (PQC) era. Further, considering that the lattice-based PQC algorithm is based on polynomial multiplication algorithms, including the Toom-Cook 4-way multiplier as its fundamental building block, we propose a higher-degree multiplier, the Toom-Cook 8-way multiplier, which has the lowest asymptotic performance and implementation cost. Additionally, the designed multiplication will include additional sub-operations to complete the multiplication of large integers in order to prevent side-channel attacks. To design our Toom-Cook 8-way in detail, we employ detailed step computations such as splitting, evaluation, point-wise multiplication, interpolation, and recomposition, as well as several strategies to reduce space and time requirements. Existing asymptotic performance and quantum implementation cost multipliers are compared with our 2-way, 4-way, and 8-way Toom-Cook multiplier designs. Our Toom-Cook 8-way quantum multiplier has the lowest asymptotic log 15 performance analysis or qubit count in terms of space efficiency, with n((15)/(8) ) (log 15)/(2log 15-log 8) log(8) n or asymptotically O(n(1.245)). The design has the lowest logical Toffoli counts bound at 112n(log)8 (15) - 128n and Toffoli depth of n( (15)/(8) )1-( log 15 )/((2 log 15-log 8)) log(8) n, asymptotically close to O(n(1.0569)), which corresponds to a space-and time-efficient multiplication.

키워드

CryptographyComplexity theoryQuantum computingQubitNISTLogic gatesQuantum circuitPost quantum cryptographyquantum multiplicationKaratsubaToom-Cook 8-wayasymptotic performanceCORRELATION POWER ANALYSISCOMPUTATIONPOLYNOMIALSNETWORKSLATTICE

식별자

Scopus EID
2-s2.0-85149363593
WoS UID
000947562500001