Nari Im, Heehun Yang, Yujin Eom et al. · Electronics · 2024
Fully Homomorphic Encryption (FHE) allows computations on encrypted data without decryption, providing strong security for sensitive information. However, computational and memory demands for FHE are significant challenges, particularly in the Number Theoretic Transform (NTT) phase. This paper presents three efficient Twiddle Factor Generators (TFGs) to address these challenges: the Half-Memory TFG, the On-the-fly Serial TFG, and the On-the-fly Parallel TFG. The Half-Memory TFG reduces memory usage by storing only half of the twiddle factors and calculating the rest as needed. The On-the-fly Serial TFG eliminates memory requirements by computing twiddle factors, while the On-the-fly Parallel TFG enhances computational speed through parallel processing. Implemented on the FPGA KCU105 board, these TFGs demonstrated significant improvements in hardware resource utilization and computational efficiency. The Half-Memory TFG effectively reduces memory footprint, the On-the-fly Serial TFG eliminates memory usage with acceptable computational overhead, and the On-the-fly Parallel TFG offers superior performance for high-throughput applications. These innovations make FHE more practical for real-world applications, contributing to the broader goal of enabling secure, privacy-preserving computations on encrypted data.
Cited by 2Open access
Tianjiong Tao, Shenggang Liu, Heli Ma et al. · Review of Scientific Instruments · 2014
Twiddle factor is considered to be the dominant error source of frequency estimate by Fourier transformation (FT), and thus impacts the accuracy in FT-based heterodyne velocimetry. Here we report a novel data analysis method for heterodyne velocimetry, which utilizes the change law of frequency errors with signals' phases to develop twiddle factor neutralization method, improving the performance of heterodyne velocimetry. Numerical simulations show that this method can improve velocity resolution by many times as compared to the boxcar, Hamming, and Hann window functions under different noise conditions. A 90° optical hybrid is used to generate four phase shifted signals for this method, and 1 m/s level velocity resolution and 100 ps level time resolution are simultaneously achieved in laser-shock experiments.
Cited by 4
Chulwoo Lee, Hanyoung Lee, Phap Duong-Ngoc et al. · 2023
The computational complexity and the large off-chip memory access of the Number Theoretic Transform (NTT) in Fully Homomorphic Encryption (FHE) are the most dominant processes in terms of the overall execution time. Furthermore, it becomes even more complicated with the Residue Number System (RNS) due to the requirement of multiple executions with different moduli. Therefore, modern RNS-based homomorphic encryption hardware architectures need the twiddle factor sets to be frequently changed from off-chip memory. To address this problem, this paper proposes an FPGA implementation of a twiddle factor generator for NTT, which can reduce off-chip memory access for different twiddle factor sets.
Cited by 2
Teemu Pitkänen, Tero Partanen, Jarmo Takala · Lecture notes in computer science · 2007
Cited by 13
Suraj N. Shinde · 2015
Fingerprint applications are widely used to identify person's authenticity. The frequency domain analysis of fingerprint plays an important role for authentication of noisy fingerprint images. This paper proposes a CORDIC algorithm: a unique computing technique suitable for solving trigonometric functions like sine, cosine and arctanto extract features of fingerprint image using FFT for perfect matching. The idea is to reduce the computational complexity of FFT using CORDIC processor. The CORDIC processor is hardware efficient which minimizes the computational complexity for twiddle factor computations. The FFT extract features of fingerprint and is implemented using CORDIC processor which consumes 390 LUTs on VIRTEX 4 FPGA.
Cited by 2
Shakeel Ahmad, Simari Guillermo R., Aditi Chandrakar et al. · 2025
Efficient polynomial multiplication is essential for lattice-based quantum-resistant cryptographic algorithms such as CRYSTALS-Kyber. Therefore, this paper presents an area- efficient twiddle factor design for Number Theoretic Transform (NTT) and inverse NTT (INTT) that significantly reduces on- chip memory utilization. The NTT is widely used for polynomial multiplication in cryptographic operations. The core of NTT is the butterfly unit that performs the modular operations with precomputed twiddle factors (roots of unity). This paper proposes a twiddle factor design based on two- and four-fold techniques. The total number of precomputed values required during the NTT/INTT process is 254 (127 values for NTT and 127 for INTT). Our design reduces the number of values required to be stored in read-only memory (ROM) to 148(+4) and 106(+4) for two-fold and four-fold techniques, respectively. The design reduces memory utilization by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{4 0. 1 6 \%}$</tex> for the two-fold unit and 56.69% for the four-fold unit compared to the conventional design. We implemented the proposed design using Kyber-digital signal processing (K-DSP) as a modular multiplication unit. The resource consumption by the proposed design on the Artix-7 FPGA platform are presented as follows: 113 LUTs, 97 FFs, 301 SLICEs for twofold computation unit, and 220 LUTs, 111 FFs, 473 SLICEs for four-fold computation units.
Cited by 0
Muhammad Ogin Hasanuddin, Hanho Lee · 2025
The Number Theoretic Transform (NTT) and its inverse (INTT) are essential operations in Fully Homomorphic Encryption (FHE), converting expensive polynomial convolution into element-wise multiplication in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n)$</tex> time while each transform itself costs <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n\log n)$</tex>. However, these transformations require storing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(n)$</tex> twiddle factors (TF). As the polynomial degree increases, storing these TFs imposes significant memory overhead, limiting available resources for ciphertexts and intermediate data in hardware accelerators. Prior work has used a separate TF generation datapath, leading to higher additional resource overhead. To address this, we propose an on-the-fly TF generation method using a reused butterfly array, which eliminates the need for dedicated TF logic. The design reduces memory usage from ~12.09 MB to only ~0.38 MB, a 96.9% reduction, with zero DSP overhead. Compared to prior designs, it achieves up to 9.6 × better resource efficiency in terms of equivalent normalized slices (ENS), enabling more area- and memory-efficient FHE hardware accelerators.
Cited by 0
Jin-Sam Kim, In‐Cheol Park · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2007
In this paper, we present a new fast Fourier transform (FFT) algorithm to reduce the table size of twiddle factors required in pipelined FFT processing. The table size is large enough to occupy significant area and power consumption in long-point FFT processing. The proposed algorithm can reduce the table size to half, compared to the radix-22 algorithm, while retaining the simple structure. To verify the proposed algorithm, a 2048-point pipelined FFT processor is designed using a 0.18 μm CMOS process. By combining the proposed algorithm and the radix-22 algorithm, the table size is reduced to 34% and 51% compared to the radix-2 and radix-22 algorithms, respectively. The FFT processor occupies 1.28 mm2 and achieves a signal-to-quantization-noise ratio (SQNR) of more than 50 dB.
Cited by 2
Ghattas Akkad, Ali Mansour, Elhassan Boudaia et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2018
International audience
Cited by 0
Hyeong‐Ju Kang, Byung‐Do Yang, Jong‐Yeol Lee · Electronics Letters · 2013
Proposed is a low‐complexity twiddle factor multiplication structure for fast Fourier transform (FFT). In an FFT implementation, the twiddle factor multiplication requires a large ROM to store the twiddle factors. In the proposed structure, the ROM is partitioned into two small ROMs, whose sum of areas is much smaller than that of the original ROM. The proposed structure requires an additional multiplier, but the multiplier is shown to be small in the experimental results. The results show that the proposed structure reduces the area of the twiddle factor multiplication by around 30% with a marginal degradation in SQNR performance.
Cited by 7
Zhenmin Li, Jingwei Ren, Gaoming Du et al. · IEEE Transactions on Circuits & Systems II Express Briefs · 2022
Number theoretic transform (NTT) method shows great advantages in speed and efficiency for applications such as homomorphic encryption. However, the twiddle factor data consumes a lot of memories. In this brief, we propose a novel data compression method, together with the corresponding data storage scheme and addressing algorithm. Furthermore, we design a 768k-bit multiplier with a full pipeline structure. Our proposed compression method has achieved a compression rate of 98.8% for the twiddle factor data. Compared with the state-of-the-art FPGA implementations, our design shows up to 44.2% improvement in terms of area-efficiency.
Cited by 11
Li Jin Cheng, Yang Hua Zhong · 2003
A low power 16-bit ROMless twiddle factor generator for radix-2 1024-point FFT is designed. This twiddle factor generator consists of several simple logic units and each of them is used to regenerate one group of the twiddle factors that is summed together by a bus. The power analysis with Synopsys power compiler shows that the power consumed by this twiddle factor generator is less than the power cost by a 128-word ROM, the smallest ROM needed by the twiddle factor generator for a radix-2 1024-point FFT. This twiddle factor generator is much suitable for the applications of mobile communications and other portable devices.
Cited by 2
Sidinei Ghissoni, Eduardo Costa, José Monteiro et al. · 2012
This paper presents an efficient area and power multiplication part of radix-2 FFT (Fast Fourier Transform) architecture. The butterfly plays a central role in the FFT computation, and the multiplication part dominates its complexity. It is composed by a product of complex data and complex coefficients named twiddle factors. The proposed strategy consists on the decomposition of the real and imaginary coefficients of the twiddle factors into less complex ones, so that the multiplication part of the butterfly can be implemented with less area, what leads to the reduction of its power consumption. The strategy also includes the use of Constant Matrix Multiplication (CMM) and gate level approaches in the decomposed coefficients. A control unit is responsible for selecting the correct constant to be used after the decomposition. The proposed architectures were synthesized using SYNOPSYS Design Compiler and the UMC130nm technology. The results show that reductions of 10% in area and 8% in power could be achieved on average, when compared with state of the art solutions.
Cited by 4
Ghada Alsuhli, Hani Saleh, Mahmoud Al‐Qutayri et al. · 2024
Area and power-efficient hardware implementations are crucial for the widespread adoption of post-quantum cryptography (PQC) algorithms like FALCON. One of the main operations in FALCON is the Number Theoretic Transform (NTT), which needs to be performed with many prime numbers. Having one set of twiddle factors (TFs) for each prime makes storing all of these TFs impractical. In this paper, we propose an architecture for generating TFs on the fly for FALCON-oriented NTT, designed for area and power efficiency. Our approach dynamically generates TFs during NTT computations, significantly reducing on-chip memory requirements. The ASIC implementation results demonstrate significant improvements, with the proposed design reducing on-chip memory requirements by 99%, occupying 95% less area, and consuming 87.4% less power compared to the traditional ROM-based implementation. Furthermore, our design achieved a much higher maximum clock frequency, indicating superior performance in accessing twiddle factors. These findings highlight the potential of our proposed architecture for efficient hardware implementations of FALCON-based cryptographic systems.
Cited by 2Open access
Priya Mule, Sudhakar Mande · International Journal of Ad Hoc and Ubiquitous Computing · 2024
In conventional FFT, techniques reducing twiddle factor complex multiplication have become a research hotspot topic. CORDIC FFT architecture overcomes the existence of multiplier blocks, which raise hardware complexity costs, increase power consumption, and lower maximum operating clock frequency. An iterative-based CORDIC architecture with a compensated barrel shifting network to provide gain k = 0.6 is proposed. This algorithm substitutes sine and cosine convolution factors with repeated KORDIC convolutions, allowing for reduced ROM. A high-speed FFT processor comprising of twiddle factor WN is replaced with an embedded CORDIC module on FPGA. It is observed that CORDIC FFT eliminates the use of 20 DSP components thereby reducing computational complexity at the maximum achievable speed of 75 MHZ. Output is shown successfully on the Artix7 board with a minimal error of approx. 0.25% and an accuracy of 99.75%. Latency and throughput issues are improved in this. Static power in CORDIC FFT is approximately 114 mw.
Cited by 0
Sudhakar Mande, Priya Mule · International Journal of Ad Hoc and Ubiquitous Computing · 2024
In conventional FFT, techniques reducing twiddle factor complex multiplication have become a research hotspot topic. CORDIC FFT architecture overcomes the existence of multiplier blocks, which raise hardware complexity costs, increase power consumption, and lower maximum operating clock frequency. An iterative-based CORDIC architecture with a compensated barrel shifting network to provide gain k = 0.6 is proposed. This algorithm substitutes sine and cosine convolution factors with repeated KORDIC convolutions, allowing for reduced ROM. A high-speed FFT processor comprising of twiddle factor WN is replaced with an embedded CORDIC module on FPGA. It is observed that CORDIC FFT eliminates the use of 20 DSP components thereby reducing computational complexity at the maximum achievable speed of 75 MHZ. Output is shown successfully on the Artix7 board with a minimal error of approx. 0.25% and an accuracy of 99.75%. Latency and throughput issues are improved in this. Static power in CORDIC FFT is approximately 114 mw.
Cited by 0
Qing Liu, Yanping Yu, Kuang Wang · IET International Conference on Wireless Mobile and Multimedia Networks Proceedings (ICWMMN 2006) · 2006
The generation of twiddle factor is an important part in FFT processor design. This paper presents a new method using small ROM spaces and a few control logic to generate twiddle factor in radix_4 FFT processor. The FPGA simulation results show that it can satisfy the high speed and real time requirement of the pipeline FFT processor. (3 pages)
Cited by 0
Bang Chul Jung, Choul‐Young Kim, Hyoungho Ko et al. · Advanced Science Letters · 2016
Cited by 0
Ziwei Wang, Weiwei Shi, Jiasheng Wu · 2025
Hardware implementation of the Fast Fourier Transform (FFT) for low-power edge applications is constrained by area and power overhead of twiddle factor ROMs. This paper presents an area- and energy-efficient, reconfigurable FFT processor op-timized for single-bit data streams. The design features a ROM-less twiddle factor generation unit based on approximate plane-fitting complex multiplication. Implemented using a binary-tree-optimized Single-path Delay Feedback (SDF) architecture, the processor supports dynamic reconfiguration for 8192/4096/2048/1024-point transforms. Designed for 40nm CMOS technology, the processor demonstrates significant advantages in area and energy efficiency over conventional ROM-based designs.
Cited by 0
Thao Thi Phuong Vo, Quynh Thi Nhu Truong, Thuc Trong Hoang et al. · Greater South Information System · 2017
In this paper, a single-precision floating-point FFT twiddle factor (TF) implementation is proposed. The architecture is based on the Adaptive Angle Recoding CORDIC (AARC) algorithm. The TF design was built and verified on Altera Stratix IV FPGA chip and 65nm SOTB synthesis. The FPGA implementation had 103.9 MHz maximum frequency, throughput result of 16.966 Mega-Sample per second (MSps), and resources utilization of 7.747 ALUTs and 625 registers. On the other hand, the SOTB synthesis has 16.858 standard cells on an area of 298x291 μm2, 166 MHz maximum frequency, and the speed of 27.107 MSps. The accuracy results were 1.133E-10 Mean-Square-Error (MSE) and about 26 part-per-million (ppm) maximum error.
Cited by 0Open access