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

622
views

176
downloads

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

İ. 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.