Radix-3 NTT-Based Polynomial Multiplication for Lattice-Based Cryptography

Download

thesis_last.pdf

Date

2022-5-31

Author

Hassan, Chenar Abdulla

Metadata

Show full item record

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

Item Usage Stats

694
views

895
downloads

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 this thesis, we focus on and introduce a radix-3 butterfly operation to be used in NTT-based polynomial multiplication. In addition, utilizing the ring structure, we propose two parameter sets of CRYSTALS-KYBER, one of the four round three finalists in the NIST Post-Quantum Competition.

Subject Keywords

Number Theoretic Transformation, Polynomial Multiplication, Kyber, Lattice-Based Cryptography

URI

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

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

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...
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...
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...
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...
Gröbner Basis Attack on STARK-Friendly Symmetric-Key Primitives: JARVIS, MiMC and GMiMCerf Kara, Gizem; Yayla, Oğuz (2022-01-01) A number of arithmetization-oriented ciphers emerge for use in advanced cryptographic protocols such as secure multi-party computation (MPC), fully homomorphic en-cryption (FHE) and zero-knowledge proofs (ZK) in recent years. The standard block ciphers like AES and the hash functions SHA2/SHA3 are proved to be efficient in software and hardware but not optimal to use in this field, for this reason, new kind of cryptographic primitives were proposed recently. However, unlike traditional ones, there is no sta...

Citation Formats

C. A. Hassan, “Radix-3 NTT-Based Polynomial Multiplication for Lattice-Based Cryptography,” M.S. - Master of Science, Middle East Technical University, 2022.