High- and Half-Degree Quantum Multiplication for Post-Quantum Security Evaluation
Rini Wisnu Wardhani, Dedy Septono Catur Putranto, Howon Kim · IEEE Access · 2024
This paper provides a thorough examination of strategies related to the design of the polynomial multiplication approach, which is essential to resolving large number operations, including multiplication in the post-quantum cryptography algorithm. Our research specifically centers on the implementation of Toom-Cook-based multiplication algorithms for high- and half-degree quantum multiplication, up to 20.5-way degrees, considering that existing Toom-Cook lower degrees are combined with a lattice-based approach like the Saber algorithm. In particular, we propose the quantum multiplication design, conduct computation step experiments, and implement the division-free method. In addition to examining the Toom-Cook 20.5-way algorithm, this study also provides an overview of the results obtained from the Toom-Cook 8.5-way and Toom-Cook 10.5-way algorithms. The Toom-Cook 20.5-way design exhibits significant performance improvement over its predecessor, as evidenced by its lower value of asymptotic complexity and lower cost of quantum implementation, with a qubit count ofn1.186, approximately 522nlog2141- 540nToffoli count, andn1.033Toffoli depth. Concerning the asymptotic performance analysis and quantum cost compared to alternative Toom-Cook-based multiplication, the results indicate the development of a more efficient multiplication polynomial that may be utilized in the evaluation of post-quantum security.