The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity O ( n log n ) has made it a key component in modern cryptography. NTT is particularly useful in lattice-based cryptography, which relies on the hardness of certain mathematical problems to ensure security. Its importance in these fields continues to grow as quantum computing technology advances and traditional encryption methods become vulnerable. In this report, we discuss the mathematical concepts of polynomial multiplications using NTT and provide a comprehensive review of the latest implementation and state-of-the-art of NTT in both PQC and HE schemes.
Fully homomorphic encryption (FHE) provides a solution to privacy-preserving applications because of its ability to perform computations on encrypted data without exposing raw data. However, FHE suffers from implementation bottlenecks owing to the large computations involved, particularly with bootstrapping. Bootstrapping is necessary in FHE to enable an unlimited number of multiplication. Nonetheless, implementing bootstrapping requires a significantly large polynomial length, $N=2^{16}$ or 217, to considerably secure the system. Thus, polynomial multiplication will be challenging in terms of resources and time. This problem can be resolved by implementing the number theoretic transform (NTT) that can perform polynomial multiplication in quasi-linear complexity. However, designing an NTT architecture for FHE is challenging because it requires various parameters, particularly the high polynomial degree that will require a considerable amount of hardware resources and clock latency. This study proposes a design for FPGA implementation of the NTT architecture with flexible input lengths: 216 and 217 by combining radix-2 and radix-24. Twiddle factor generator (TFG) and efficient configurable modular multiplication (MM) unit are also utilized to achieve time and area-efficient architecture. The proposed design was synthesized on the FPGA Xilinx ALVEO U250 and demonstrated higher hardware efficiency and optimum latency that outperforms those reported in previous studies.
12 August 2024 in IEEE Transactions on Circuits and Systems II: Express Briefs
The development of quantum computers has created a need for new Post-Quantum cryptography (PQC) to address the potential threat to the current cryptography systems. The Module-Lattice-based Key-Encapsulation Mechanism (ML-KEM) – previously known as CRYSTALS-Kyber – is a lattice-based algorithm that offers smaller keys and high security. In this brief, we present a configurable hardware architecture that can perform key encapsulation mechanisms: key generation, encapsulation, and decapsulation of ML-KEM/Kyber. The proposed configurable architecture includes a Memory-based Number Theoretic Transform (NTT) and its inverse (INTT) module to reduce the complexity of polynomial multiplication. By designing the NTT/INTT module to be configurable, resource usage is minimized. We implemented the proposed ML-KEM architecture on the Artix-7 FPGA platform. Compared to existing state-of-the-art approaches, we achieved an Area-Time Product (ATP) performance improvement of $1.03\times $ at security level 1, $1.10\times $ at security level 3, and $1.23\times $ at security level 5.
Losing a hand can significantly impact an individual’s physical and emotional well-being. Prosthetic hands can help restore some function and independence for individuals who have lost a hand. However, the prosthetic hands available on the market are prohibitively expensive, especially for developing countries, such as Indonesia. Commercial electronically powered prosthetic hands can be expensive, having prices ranging from $25,000 to $75,000 and annual maintenance costs ranging from $500 to $3000. In contrast, body-powered prosthetic hands are generally cheaper, ranging from $2000 to $10,000, but are still considered expensive for many people in developing countries. To make prosthetic hands more accessible, we have designed a body-powered prosthetic hand, “Karla”, using affordable materials and with as few components as possible. This report presents our proposed designs, the innovations, the parts in detail, and experiences using the designed prosthetic hand. The highlight of our design is a novel whippletree-like mechanism that utilizes the 3-D space to contract the fingers of the prosthetic hand.
In recent years, measuring and monitoring analyte concentrations continuously, frequently, and periodically has been a vital necessity for certain individuals. We developed a cotton-based millifluidic fabric-based electrochemical device (mFED) to monitor glucose continuously and evaluate the effects of mechanical deformation on the device’s electrochemical performance. The mFED was fabricated using stencil printing (thick film method) for patterning the electrodes and wax-patterning to make the reaction zone. The analytical performance of the device was carried out using the chronoamperometry method at a detection potential of −0.2 V. The mFED has a linear working range of 0–20 mM of glucose, with LOD and LOQ of 0.98 mM and 3.26 mM. The 3D mFED shows the potential to be integrated as a wearable sensor that can continuously measure glucose under mechanical deformation.
Modular arithmetic calculations, such as modular addition and multiplication, are fundamental building blocks to Post-Quantum Cryptography (PQC) and Homomorphic Encryption (HE) systems. While modular addition has straightforward hardware implementations, integer modular multiplication is more challenging to implement. This work focuses on integer modular multiplication with Barrett modular reduction, or in short, the Barrett modular multiplication (BMM) technique, presenting an overview of its original algorithm, variants, and subsequent optimizations. The study offers comparative examples and a comprehensive analysis of the theoretical complexity and both empirical and experimental results for each BMM variant.