On the Number of Arithmetic Operations in NTT-based Polynomial Multiplication in Kyber and Dilithium Cryptosystems

Ilter M. B., Kocak N., Uslu E., Yayla O., Yuca N.

14th International Conference on Security of Information and Networks (SIN), ELECTR NETWORK, 15 - 17 December 2021 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/sin54109.2021.9699310
  • Country: ELECTR NETWORK
  • Keywords: Post-quantum cryptography, lattice-based cryptography, polynomial multiplication, number theoretic transform, Crystals-Kyber, Crystals-Dilithium
  • Middle East Technical University Affiliated: Yes

Abstract

National Institute of Standards and Technology (NIST) initiated a post-quantum standardization process in 2016, and as of July 2020, Round 3 candidates were announced. Among these candidates, Crystals-Kyber and Crystals-Dilithium are the most promising lattice-based key encapsulation mechanism (KEM) and signature algorithm that rely on the module learning with errors (Module-LWE) problem. In general, polynomial multiplication is one of the most time-consuming operations in Module-LWE based cryptosystems. There are several polynomial multiplication methods for multiplying two polynomials effectively. One of the most efficient methods is Number Theoretic Transform (NTT). This paper analyzes the number of arithmetic operations occupied in NTT multiplication for Kyber and Dilithium cryptosystems. The general formula on the number of multiplications and additions used in NTT operation for the lattice-based algorithms which have a ring structure similar to Kyber and Dilithium is given for q < 2(w-1) where w is the word size and q is the modulus. Also, cycle counts of arithmetic operations of Kyber and Dilithium are calculated on reference implementations to determine the relationship between our formulations and cycle counts.