Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber

Download

Thesis_Berkin_Aksoy_1740398_submitted.pdf

Date

2022-2-28

Author

Aksoy, Berkin

Metadata

Show full item record

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

Item Usage Stats

561
views

115
downloads

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 Standardization Process. On the other hand, if the q value of the scheme is a power of 2, as in NTRU and Saber, which are among the other lattice-based finalists, NTT can not be used explicitly. Hence multiplications are performed by the combination of Toom-Cook and Karatsuba algorithms. Recently, a novel technique called lazy interpolation has been introduced to increase the performance of Toom-Cook and Karatsuba algorithms. This thesis shows that the block recombination method is equivalent to lazy interpolation and can be used efficiently on multiplication algorithms. On the practical side, we compare different hybrid multiplication algorithms, then implement the block recombination method for Saber. Performance results are given in cycle values on general-purpose Intel processors with C implementation. Our work speeds up key generation, encapsulation, and decapsulation parts of Saber than the previous C implementations in the literature with a rate of between 10%-13%.

Subject Keywords

Post-Quantum Cryptography, Lattice-Based Cryptography, Saber, Efficient Algorithm Implementations, Block Recombination, Lazy Interpolation

URI

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

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

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 TMVP-BASED MULTIPLICATION ALGORITHMS FOR POLYNOMIAL QUOTIENT RINGS AND APPLICATION TO POST-QUANTUM CRYPTOGRAPHY Keskinkurt Paksoy, İrem; Cenk, Murat; Department of Cryptography (2022-7-28) 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 standardizati...
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...
Mutual correlation of NIST statistical randomness tests and comparison of their sensitivities on transformed sequences Doğanaksoy, Ali; Uğuz, Muhiddin; Akcengiz, Ziya (2017-01-01) Random sequences are widely used in many cryptographic applications and hence their generation is one of the main research areas in cryptography. Statistical randomness tests are introduced to detect the weaknesses or nonrandom characteristics that a sequence under consideration may have. In the literature, there exist various statistical randomness tests and test suites, defined as a collection of tests. An efficient test suite should consist of a number of uncorrelated statistical tests each of which meas...
Related-key attacks on block ciphers Darbuka, Aslı; Doğanaksoy, Ali; Department of Cryptography (2009) One of the most important cryptographic primitives is the concept of block ciphers which yields confidentiality for data transmission in communication. Therefore, to be sure that confidentiality is provided, it is necessary to analyse the security of block ciphers by investigating their resistance to existing attacks. For this reason, related-key attacks gain much popularity in recent years and have been applied to many block ciphers with weak key schedules. In this work, our main motivation is to cover typ...

Citation Formats

B. Aksoy, “Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber,” M.S. - Master of Science, Middle East Technical University, 2022.