Quantum Circuits for High-Degree and Half-Multiplication for Post-quantum Analysis

Quantum Circuits for High-Degree and Half-Multiplication for Post-quantum Analysis

연구 분야: Cryptography

학회: International Conference on Information Security and Cryptology

Along with the possibility of accelerated polynomial multiplication, the Toom-Cook k–way multiplication technique has drawn significant interest in the field of post-quantum cryptography due to its ability to serve as a part of the lattice-based algorithm. In contrast, the growing likelihood of attacks based on multiplication, specifically correlation power analysis attacks, has heightened vulnerability and emphasized the need to examine the feasibility of employing the polynomial multiplication method as a potential alternative in the era of post-quantum. This study examines thoroughly an elaborate mathematical procedure designated as high-degree and half-multiplication, focusing on the design of an efficient multiplication technique. The proposed polynomial multiplication is intended to be enhanced in terms of asymptotic performance analysis and quantum resource utilization. Through the utilization of the Toom-Cook 8.5-way method, we reach the lowest asymptotic performance and quantum resources usage for multiplication operation in comparison to the existing Toom-Cook-based multiplication designs with \(186n^{\log _9 17}- 202n\) Toffoli count and \(n(\frac{17}{9})^{1-\frac{\log 17}{(2\log 17 - \log 9)} \log _9 n }\approx n^{1.053}\) Toffoli depth. The designed multiplication yields a qubit count of \(n(\frac{17}{9})^{\frac{\log 17}{(2\log 17 - \log 9)} \log _9 n }\), or approximately \(n^{1.236}\). We further compare its asymptotic performance and quantum resource efficiency to other Toom-Cook-based multiplications to determine its efficacy.