Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
NEW TMVP-BASED MULTIPLICATION ALGORITHMS FOR POLYNOMIAL QUOTIENT RINGS AND APPLICATION TO POST-QUANTUM CRYPTOGRAPHY
Download
irem_phd_thesis.pdf
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
517
views
135
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
Suggestions
OpenMETU
Core
Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber
Aksoy, Berkin; Cenk, Murat; Department of Cryptography (2022-2-28)
Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptography (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type {Z}_{q}[x] / f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC S...
TMVP-Friendly Primes for Efficient Elliptic Curve Cryptography
Taskin, Halil Kemal; Cenk, Murat (2020-12-03)
The need for faster and practical cryptography is a research topic for decades. In case of elliptic curve cryptography, which was proposed by Koblitz and Miller in 1985 as a more efficient alternative to RSA, the applications in real life started after 2000s. Today, most of the popular applications and protocols like Whatsapp, Signal, iOS, Android, TLS, SSH, Bitcoin etc. make use of Elliptic curve cryptography. One of the important factor for high performance elliptic curve cryptography is the finite field ...
Analysis of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber
Aksoy, Berkin; Cenk, Murat (2022-01-01)
Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptog-raphy (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type Zq [x]/f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC Standa...
NEW EFFICIENT CHARACTERISTIC THREE POLYNOMIAL MULTIPLICATION ALGORITHMS AND THEIR APPLICATIONS TO NTRU PRIME
Yeniaras, Esra; Cenk, Murat; Department of Cryptography (2022-1-21)
Some of the post-quantum cryptographic protocols require polynomial multiplication in characteristic three fields, thus the efficiency of such multiplication algorithms gain more importance recently. In this thesis, we propose four new polynomial multiplication algorithms in characteristic three fields and we show that they are more efficient than the current state-of-the-art methods. We first analyze the well-known algorithms such as the schoolbook method, Karatsuba 2-way and 3-way split methods, Bernstein...
Radix-3 NTT-Based Polynomial Multiplication for Lattice-Based Cryptography
Hassan, Chenar Abdulla; Yayla, Oğuz; Department of Cryptography (2022-5-31)
The lattice-based cryptography is considered as a strong candidate amongst many other proposed quantum-safe schemes for the currently deployed asymmetric cryptosystems that do not seem to stay secure when quantum computers come into play. Lattice-based algorithms possesses a time consuming operation of polynomial multiplication. As it is relatively the highest time consuming operation in lattice-based cryptosystems, one can obtain fast polynomial multiplication by using number theoretic transform (NTT). In ...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
İ. Keskinkurt Paksoy, “NEW TMVP-BASED MULTIPLICATION ALGORITHMS FOR POLYNOMIAL QUOTIENT RINGS AND APPLICATION TO POST-QUANTUM CRYPTOGRAPHY,” Ph.D. - Doctoral Program, Middle East Technical University, 2022.