On the generalization and efficiency optimization of hybrid multiplication algorithms

Date

2026-9-1

Author

Cihangir, Mehmet Özgün

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

74
views

0
downloads

Cite This

Cryptography is the science of the privacy and security of the data in our casual lives. This has given rise to the acceleration of the search on powerful and secure cryptographic systems throughout the history. These studies aim to prevent confidential data misuse by malicious or unauthorized parties. Numerous cryptosystems have been designed by cryptanalysts throughout the last 50 years. However, the continuous improvement and relevance of quantum computers pose security threats for the existing classical cryptosystems. The area of post-quantum cryptography deals with the purpose of mitigation of these threats. As a result, the American National Institute of Standards and Technology, NIST, started Post-Quantum Cryptography Standardization, in which 7 candidate algorithms qualified for the final stage of the competition. Among these finalists, CRYSTALS-KYBER, NTRU, SABER, CRYSTALS-Dilithium and FALCON make use of polynomial multiplication over the ring ${\mathbb{Z}_q[x]}/\langle{x^n-1}\rangle$ and matrix-vector multiplications in lattice-based cryptography. This thesis investigates the generalizability of common polynomial multiplication and matrix-vector multiplication algorithms on their usability as a $n$-way algorithm for any given $n$. Moreover, using the attained results, for a fixed $n$, it studies the optimization of the efficiency of $n$-way algorithms, when used individually and hybrid. It has been found that for the specific $k$ values $k=5,6,8,12$, our proposed novel $k$-way Toeplitz matrix-vector multiplication algorithm shows better performance in complexity than the Toeplitz matrix-vector multiplication algorithms present in the literature when the input size $n$ is sufficiently large. For the polynomial multiplication algorithms, our proposed sequential string of polynomial multiplication algorithms with the best possible complexity with the input set $n=2^l$ proves better than the Toom-Cook polynomial multiplication algorithm for the same input set, while for both of the input sets $n=2^l$ and $n=3^l$, our string of algorithms is more efficient than both Karatsuba and Optimized Karatsuba polynomial multiplication algorithms.

Subject Keywords

Polynomial multiplication, Toeplitz matrix-vector product, Subquadratic algorithms, Algebraic complexity, Post-quantum cryptography, Divide and conquer

URI

https://hdl.handle.net/11511/120978

Collections

Graduate School of Applied Mathematics, Thesis