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

Abstract

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 performance analysis or qubit count in terms of space efficiency, with $n\left({\frac {15}{8}}\right)^{\frac {\log 15}{(2\log 15 - \log 8)} \log _{8} n}$ or asymptotically $\mathcal {O} (n^{1.245})$ . The design has the lowest logical Toffoli counts bound at $112n^{\log _{8} 15}-128n $ and Toffoli depth of $n\left({\frac {15}{8}}\right)^{1-\frac {\log 15}{(2\log 15 - \log 8)} \log _{8} n }$ , asymptotically close to $\mathcal {O}(n^{1.0569})$ , which corresponds to a space- and time-efficient multiplication.

Keywords

• Post quantum cryptography
• quantum multiplication
• Karatsuba
• Toom-Cook 8-way
• asymptotic performance