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

Date

2022-01-01

Author

Aksoy, Berkin
Cenk, Murat

Metadata

Show full item record

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

Item Usage Stats

185
views

0
downloads

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 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 [IACR Transactions on Cryptographic Hardware and Embedded Systems 2020.2: 222-244 (2020)] has been introduced to increase the performance of Toom-Cook and Karatsuba algorithms. This paper shows that the block recombination method [IEEE Transactions on Computers 63(9): 2273-2287 (2014)] is equivalent to lazy interpolation and can be used efficiently on multiplication algorithms. On the practical side, we compare different hybrid multiplications 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

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

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85142779867&origin=inward
https://hdl.handle.net/11511/101658

DOI

https://doi.org/10.1109/iscturkey56345.2022.9931800

Conference Name

15th International Conference on Information Security and Cryptography, ISCTURKEY 2022

Collections

Graduate School of Applied Mathematics, Conference / Seminar

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...
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...
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...
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...
On the efficiency of lattice-based cryptographic schemes on graphical processing unit Yüce Tok, Zaliha; Akyıldız, Ersan; Akleylek, Sedat; Department of Cryptography (2016) Lattice-based cryptography, a quantum-resistant public key alternative, has received a lot of attention due to the asymptotic efficiency. However, there is a bottleneck to get this advantage on practice: scheme-based arithmetic operations and platform-based implementations. In this thesis, we discuss computational aspects of lattice-based cryptographic schemes focused on NTRU and GLP in view of the time complexity on both CPUs and Graphical Processing Units (GPU). We focus on the optimization of polynomial ...

Citation Formats

B. Aksoy and M. Cenk, “Analysis of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber,” presented at the 15th International Conference on Information Security and Cryptography, ISCTURKEY 2022, Ankara, Türkiye, 2022, Accessed: 00, 2023. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85142779867&origin=inward.