This paper proposes two architectures for the acceleration of Number Theoretic Transforms (NTTs) using a novel Montgomery-based butterfly. We first design a custom NTT hardware accelerator for Field-Programmable Gate Arrays (FPGAs). The butterfly architecture is expanded to a Modular Arithmetic Logic Unit (MALU) and for greater reuse and easier programmability a six-stage pipeline Linux-ready RISC-V core is extended with custom instructions. The performance of the proposed architectures is assessed on a Xilinx Ultrascale+ FPGA and with an Application-Specific Integrated Circuit (ASIC) on$28{n}\text{m}$CMOS technology. In FPGA, the results for custom acceleration show reductions of 30%, 90% and 42% in the number of Lookup tables (LUTs) and registers, Block RAMs (BRAMs) and Digital Signal Processors (DSPs), while providing a speedup of 1.9 times, in comparison with the state of the art. The ASIC results show that at 1 GHz the proposed architecture is in average 45% and 52% less area and power hungry, respectively, compared to the state of the art. Furthermore, the proposed MALU, operating as an additional execution unit, increases the overall area of the extended RISC-V core by only 10%, without significant changes in the frequency of operation.

The conference offers a note of thanks and lists its reviewers.

The Number Theoretic Transform (NTT) plays a central role for supporting high-performance polynomial multiplication on Post-Quantum Cryptography (PQC) and Fully-Homomorphic Encryption (FHE). This paper proposes a novel Montgomery-based butterfly to efficiently implement NTTs on FPGAs. This proposal is supported on prime moduli suitable for FHE, which minimizes the requirements to allow the speedup of the computation of the butterfly. A search algorithm is presented to select these moduli, while flexibility is a target in all parameters making the proposed architectures well-suited for FHE and PQC schemes. We experimentally evaluate the effectiveness of the novel butterfly-core on a Xilinx Virtex-7 device. The results show reductions up to 19%, 41%, 37%, and 67% in the number of lookup tables, slices, flip-flops, and Digital Signal Processors (DSPs), respectively, in comparison to the related state of the art. By integrating the proposed butterflies in a complete NTT accelerator, a speedup of up to 1.42 is achieved, while less than half of the number of DSPs are required, when compared to the other proposals. Moreover, the integration of the proposed accelerators to design FHE-based processors is discussed.

The conversion from a Residue Number System (RNS) to a weighted representation is a costly inter-modulo operation that introduces delay and area overhead to RNS processors, while also increasing power consumption. This paper proposes a new approach to decompose the reverse conversion into operations that can be processed by the arithmetic units already present in the RNS independent channels. This leads to a more effective reuse of the processor circuitry while enhancing parallelism. Experimental results show that, when the proposed techniques are applied to architectures based on ripple-carry adders for the traditional 3-moduli set, the delay is improved in average by 16 percent, the circuit area by 36 percent and the power consumption by 47 percent. When carry-lookahead adder topologies are considered, these improvements are in average of 45 percent for the circuit area and 58 percent for the power consumption while the delay is only slightly reduced. The proposed techniques are applied to a use case in digital filtering, showing an increase in throughput/area of up to 1.25 times, and average reductions in energy consumption of 15.6 percent. This work is a step forward to the usage of RNS in practice, since reverse conversion underpins other hard inter-modulo operations, like comparison, scaling and division.

This paper presents a procedure to optimize modular multiplication by constants. Such operations have been demonstrated to be crucial to design efficient reverse converters, which are the bottleneck of RNS. The focus of this work is the use of Residue Number System (RNS) moduli sets without limitation of the number of channels, which are useful for Digital Signal Processing (DSP) applications. Moreover, an improved hardware architecture for a reverse converter algorithm by using balanced generic moduli sets is presented too. The experimental results show that the optimization of modular multiplication by constant on reverse converters provides a speedup of 1.40 times and average area reduction of 27% for maximum dynamic ranges presented in the state of the art.