Date

2022-7-28

Author

Keskinkurt Paksoy, İrem

Metadata

Show full item record

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

Item Usage Stats

413
views

111
downloads

Cite This

One of the quantum-safe cryptography research areas is lattice-based cryptography. Most lattice-based schemes need efficient algorithms for multiplication in polynomial quotient rings. The fastest algorithm known for multiplication is the Number Theoretic Transform (NTT), which requires certain restrictions on the parameters of the ring, such as prime modulus. Direct NTT application is not an option for some schemes that do not comply with these restrictions, e.g., the two finalists of the PQC standardization competition, Saber and NTRU, which use a power-of-two modulus. Toom-Cook and Karatsuba are the most commonly used non-NTT multiplication algorithms. Even though a method of using NTT in NTT-unfriendly rings with larger parameters that prevent any modular reduction on the original result is proposed, developing non-NTT multiplication algorithms can also improve the efficiency of multiplication in such rings. In this thesis, we focused on developing Toeplitz Matrix-Vector Product (TMVP) based multiplication algorithms for PQC schemes. First, we propose new three- and four-way TMVP split formulas with five and seven multiplications. We choose Saber and NTRU schemes for our case study. We develop TMVP-based multiplication algorithms using the new four-way formula for the rings on which Saber and NTRU are defined. We also propose an improved version of the algorithm for Saber and present a padding method for NTRU to utilize TMVP split formulas. Moreover, we implement the proposed algorithms on ARM Cortex-M4, which NISTrecommends as an evaluation platform for PQC candidates on microprocessors. We improve performance and stack memory consumption compared to all Toom implementations. We also observe that our TMVP-based algorithms are faster than NTT for three of the parameter sets of NTRU, and they reduce the stack usage for all. We integrate our codes into state-of-the-art implementations of Saber and NTRU in the literature to see the effect of our algorithm on the total performance of the schemes. For Saber, our algorithm achieves improvements up to 18.6% in performance and up to 44.2% in memory consumption compared to the Toom method. For all parameter sets of NTRU, we reduce stack usage between 5.9%−20.9% compared to Toom and 5.1% − 19.3% compared to NTT. Moreover, we observe performance improvements between 4.4%−17.5% compared to Toom for all parameter sets. Except for one of the parameter sets of NTRU, our algorithms outperform the NTT method. Furthermore, we propose new formulas for non-square TMVP calculations and a new approach for deriving new TMVP split formulas using the non-square formulas. The arithmetic complexity calculations and theoretical efficiency comparisons are also presented in this thesis.

Subject Keywords

Toeplitz matrix-vector product, lattice-based cryptography, post-quantum cryptography, Saber, NTRU, key encapsulation mechanism, polynomial multiplication, ARM Cortex-M4

URI

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

Collections

Graduate School of Applied Mathematics, Thesis