Lattice-based post-quantum cryptographic algorithm FALCON needs to execute the time-critical Fast-Fourier Transformation (FFT). Existing works in the literature have explored hardware for FFT of FALCON using Cooley-Tukey. In this work, we have designed an efficient hardware-software co-design of FFT for FALCON using Winograd’s FFT method. Winograd’s FFT is a widely adopted technique for FFT and reduces the multiplication counts for higher-radix FFT than the Cooley-Tukey, with a penalty of some extra addition/subtraction. Our Winograd radix-8 framework for FFT outperforms the traditional Cooley-Tukey method. Moreover,our proposed architecture is flexible in adopting different instruction sets and can also be configured for any type of FFT method with specific instruction sets.

Number Theoretic Transform (NTT) plays an important role in efficiently implementing lattice-based cryptographic algorithms like CRYSTALS-Kyber, Dilithium, and FALCON. Existing implementations of NTT for these algorithms are mostly based on radix-2 or radix-4 realization of Cooley-Tukey and Gentleman-Sande architectures. In this work, we explore an alternative method of performing NTT known as Winograd’s NTT that requires fewer number of modular multipliers than the conventional Coole-Tukey/Gentleman-Sande for higher radix NTT. We have proposed three different low-latency implementations of Winograd’s NTT, applicable to CRYSTALS-Dilithium, FALCON, and CRYSTALS-Kyber, respectively. Our first implementation of Winograd NTT focuses on radix-16 NTT multiplication unit for polynomials of length 256 and can be directly used for CRYSTALS-Dilithium. The NTT of CRYSTALS-Dilithium is also benefited from our proposed K-RED modular multiplication. Our radix-16-based Winograd outperforms existing Cooley-Tukey/Gentleman-Sande based NTT multipliers of CRYSTALS-Dilithium. Our second implementation of NTT is based on radix-8 Winograd structure with a novel modular multiplication method that targets polynomials of length 512 and can be directly applied for FALCON. For CRYSTALS-Kyber, we have designed a radix-16 Winograd Butterfly Unit (BFU) that can be configured as two parallel radix-8 Winograd BFUs during mixed-radix computation. To the best of our knowledge, this is the first work that applied the Winograd technique for NTT multiplication for post-quantum secure lattice-based cryptographic algorithms.

Secure authentication of any Internet-of-Things (IoT) device becomes the utmost necessity due to the lack of specifically designed IoT standards and intrinsic vulnerabilities with limited resources and heterogeneous technologies. Despite the suitability of arbiter physically unclonable function (APUF) among other PUF variants for the IoT applications, implementing it on field-programmable gate arrays (FPGAs) is challenging. This work presents the complete characterization of the path changing switch (PCS) 1 based APUF on two different families of FPGA, like Spartan-3E (90 nm CMOS) and Artix-7 (28 nm CMOS). A comprehensive study of the existing tuning concept for programmable delay logic (PDL) based APUF implemented on FPGA is presented, leading to establishment of its practical infeasibility. We investigate the entropy, randomness properties of the PCS based APUF suitable for practical applications, and the effect of temperature variation signifying the adequate tolerance against environmental variation. The XOR composition of PCS based APUF is introduced to boost performance and security. The robustness of the PCS based APUF against machine learning based modeling attack is evaluated, showing similar characteristics as the conventional APUF. Experimental results validate the efficacy of PCS based APUF with a little hardware footprint removing the paucity of lightweight security primitive for IoT.