Additive Fast Fourier Polynomial Multiplier For Code Based Algorithms

In the modern era, devices require cryptography to protect information against malicious behavior that could exploit and damage the user. To address this, various algorithms have been developed for different purposes. These algorithms leverage complex mathematical problems to make it computationally infeasible to break a system within a reasonable timeframe, even for powerful computers. However, the advent of quantum computers has the potential to significantly impact cryptography by rendering many traditional algorithms vulnerable to attacks. For example, Shor's Algorithm can break the factoring problem of RSA in polynomial time. In response, NIST initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptography algorithms. Different categories of algorithms were proposed. After four rounds of submission, NIST recommends two primary algorithms to be implemented for most use cases: CRYSTALS-KYBER and CRYSTALS-Dilithium, FALCON, and SPHINCS+. Now, NIST will create new draft standards for the algorithms to be standardized and will coordinate with the submission teams to ensure that the standards comply with the specifications. NIST expects to select at most one of these two candidates for standardization at the conclusion of the fourth round. Therefore, in this study, code-based algorithms were selected. The study focused on improving the execution of polynomial multiplication within HQC and McEliece, as it was one of the heaviest operations from a computational standpoint in the respective lattice-based algorithms. The primary objective centers on the development of a polynomial multiplier based on the Fast Fourier Transform. The exploration of the finite fields used by HQC and McEliece led to the subsequent decision to utilize a new class of FFTs, the additive FFTs, which have the advantage of evaluating and interpolating polynomials in fields that do not have the desired nth roots of unity, by exploiting the additive vector space construction of the finite fields. For this specific purpose, the Additive Fast Fourier Transform developed by Gao and Mateer was chosen for multiplying polynomials that lie in finite fields of characteristic two, as the one present in HQC and McEliece. The research is conducted in two main stages. Initially, a software model of the polynomial multiplier was created to run on all levels of security of HQC and McEliece. Subsequently, The model was then integrated into the official algorithms to verify the correct functioning of the algorithms when working with the multiplier. The second phase involved the development of the hardware structure of the multiplier based on the software model. Employing a memory-based approach to tackle the high number of points to evaluate and interpolate, thereby reducing the hardware cost by minimizing the required number of processing elements.