High- and Half-Degree Quantum Multiplication for Post-Quantum Security Evaluation

Abstract

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 of $n^{1.186}$ , approximately $522n^{\log _{21} 41}- 540n$ Toffoli count, and $n^{1.033}$ Toffoli 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.

Keywords

• Toom-cook
• high- and half-degree quantum multiplication
• asymptotic performance analysis
• quantum cost