Fully Homomorphic Encryption (FHE) has become a promising approach to protecting data privacy in emerging application scenarios. Unfortunately, FHE suffers from significant processing speed degradation compared to plaintext computation, with one of the primary bottlenecks being the time-consuming Number Theoretic Transform (NTT). Therefore, accelerating NTT to accommodate various FHE parameters is crucial to advancing FHE towards practical use. With highly reconfigurable and performant logical fabrics, Field Programmable Gate Arrays (FPGAs) have exhibited great potential in NTT acceleration. By decomposing large-point NTT with strong data dependency into independent and simple small-point NTTs, the emerging Ten-step NTT (TNTT) algorithms intuitively enable higher parallelism and thereby have the potential to explore better performance compared to traditional algorithms. However, our quantitative analysis reveals that TNTT exhibits significant performance degradation as parallelism increases due to additional varying-size transpositions and Hadamard products. This paper proposes AutoNest, an efficient and scalable hardware architecture, along with an accelerator auto-generation framework for TNTT. The proposed hardware architecture maximizes performance by 1) adopting a 2D block decomposition dataflow to address critical path delays in transpose logic, thereby improving clock frequency. 2) integrating algorithm-level costfree twiddle factor fusion to reduce the number of modular multiplications in Hadamard products, thereby allowing higher parallelism on chip. Moreover, we also deliver an accelerator generation framework conducting automated design space exploration to elaborate a performant TNTT architecture under the target FPGAs' resource budget for user-defined FHE parameters. Experimental results on the AMD-Xilinx U280 FPGA demonstrate that NTT accelerators generated by AutoNest achieve an average speedup of$2.31 \times$compared to prior designs.

Modular arithmetic, particularly modular reduction, is widely used in cryptographic applications such as homomorphic encryption (HE) and zero-knowledge proofs (ZKP). High-bit-width operations are crucial for enhancing security; however, they are computationally intensive due to the large number of modular operations required. The lookup-table-based (LUT-based) approach, a “space-for-time” technique, reduces computational load by segmenting the input number into smaller bit groups, pre-computing modular reduction results for each segment, and storing these results in LUTs. While effective, this method incurs significant hardware overhead due to extensive LUT usage. In this paper, we introduce ALLMod, a novel approach that improves the area efficiency of LUT-based largenumber modular reduction by employing hybrid workloads. Inspired by the iterative method, ALLMod splits the bit groups into two distinct workloads, achieving lower area costs without compromising throughput. We first develop a template to facilitate workload splitting and ensure balanced distribution. Then, we conduct design space exploration to evaluate the optimal timing for fusing workload results, enabling us to identify the most efficient design under specific constraints. Extensive evaluations show that ALLMod achieves up to $\lt sup\gt1\lt/sup\gt|.65 \times$ and $3 \times$ improvements in area efficiency over conventional LUT-based methods for bit-widths of 128 and 8,192, respectively.

In this article, we present the HiCoP architecture, a high-performance, conflict-free memory access, modular polynomial multiplication design that accelerates the number-theoretic transform (NTT), inverse NTT (INTT), and modular polynomial multiplications. To optimize hardware costs, the HiCoP architecture utilizes a high-radix reconfigurable butterfly unit (RBU) that can be dynamically configured to perform NTT, INTT, and point-wise multiplications, alongside an area-efficient Montgomery modular multiplier (MMM) tailored for NTT-friendly modulus. Moreover, by integrating pre-processing, post-processing, and Montgomery domain transformations into NTT and INTT operations, we effectively minimize the cycle count for modular polynomial multiplication. Additionally, we propose a novel conflict-free memory access algorithm that simplifies the control logic and eliminates the need for ping-pong memory in the HiCoP architecture. Experimental results of modular polynomial multiplications demonstrate significant performance gains for the HiCoP architecture implemented on the Xilinx Virtex-7 field-programmable gate array (FPGA) platform, with up to$8.75\times $,$4.15\times $,$10.57\times $, and$8.50\times $improvements in throughput-to-hardware-cost ratio for LUT count, FF count, BRAM count, and DSP count, respectively.

This article presents an area-efficient Barrett modular multiplication (BMM) algorithm, facilitating the development of cryptosystems like fully homomorphic encryption. Instead of implementing three normal multiplications required by classic BMM, our proposed BMM introduces optimizations for multiplication AB, truncated multiplication$\lfloor AB/2^{f} \rfloor $, and modular multiplication (MM)$AB ~\text {mod}~2^{f}$. Taking the 4-term Karatsuba algorithm as an example, an N-bit multiplication AB can be decomposed into$9~(N/4)$-bit multiplications. Our optimized approaches for truncated multiplication and MM require an area equivalent to only$6.5~(N/4)$-bit multiplications when$f\approx N$. Furthermore, our optimized Karatsuba multiplications introduce efficient (E, I) matrix pairs, circumventing area overhead from complex I matrices and sign extension in multiplication. We also employ encode algorithm to eliminate many additions needed in BMM and inside multiplications, significantly shortening critical path. Experimental results demonstrate the advantages of our proposed BMM in terms of throughput and area efficiency.

Modular multiplication (MM) is a fundamental operation in many cryptographic and arithmetic applications. In this article, we present an improved Barrett modular multiplication (BMM) algorithm and its hardware-efficient implementation. The proposed algorithm leverages parallel computation of quotient and intermediate results, enhancing overall efficiency. To further optimize the algorithm, two optimizations are introduced, replacing expensive multiplications and additions with more efficient compression and encoding operations at each iteration. We first introduce a novel data model that enables the use of a 2-bit adder to handle potential overflow in signed addition. Moreover, by employing a 3-bit addition on intermediate results, we eliminate the need for complete round operations while ensuring the desired result range. The experimental results demonstrate significant improvements in terms of area and computation time compared to existing classic BMM and Montgomery modular multiplication (MMM) designs. Our improved BMM outperforms these designs, particularly in high-radix scenarios. This work provides a valuable contribution to the field of MM, offering a hardware-efficient solution for achieving improved performance in cryptographic and arithmetic systems.

This paper presents a highly efficient iterative Montgomery modular multiplication algorithm, wherein the computations of quotient and intermediate result in each iteration are done in parallel. This parallelism breaks the data dependency and thus reduces the computation latency. Moreover, this paper replaces required multiplications and additions in each iteration with compressions and encoding, thereby achieving a computation latency of order$d+6$where$d=\left\lceil N/m \right\rceil +2$is the number of iterations,$N$denotes the bitwidth of modulus$M$, and$m$is the number of bits of the multiplier that are processed in each iteration of the algorithm. Hardware realization of the proposed Montgomery modular multiplication on a Xilinx Virtex-7 FPGA device shows$> 41\%$computation latency saving and$>31\%$area saving when$N=1,024$and$m=8$, compared with the best of previous state-of-art references. These savings amount to more than 63% reduction in terms of the area-latency product metric.

The proposed herein is a scalable high-radix (i.e.,$2^m$2m) Montgomery Modular (MM) Multiplication circuit replacing the integer multiplications in each iteration of the Montgomery MM algorithm (related to the product of$m$mbits of the multiplier and the multiplicand) with carry-save compressions and completely eliminating costly multiplications. Furthermore, the proposed Montgomery MM decomposes the multiplicand itself using a radix of$2^w$2wwith$w\geq 2m$w≥2m, thereby achieving a scalable design, which can deliver an issue latency of one cycle and a cycle (count) latency of$O(N^2/(wmp))$O(N2/(wmp))where$p$pdenotes the number of available processing elements, each of which is designed to complete the above iteration by computing in part the product of$w$wbits of the multiplicand and$m$mbits of the multiplier. The area complexity of the proposed Montgomery MM is$O(wmp)$O(wmp), and thus, the Area-Latency-Product complexity is$O(N^{2})$O(N2).

This paper presents a fast architecture for Barrett modular multiplication. By replacing the integer multiplications in each iteration with carry-save compressions and using Booth coding plus operation rescheduling to increase parallelism, we eliminate costly multiplications while concurrently avoiding large-bitwidth additions. Our detailed error analysis proves that intermediate results are always less than twice the modulus. Experimental results show that the removal of multiplication eliminates the need for any DSPs. Even not accounting for this key benefit, compared to the best of prior art results, the proposed design results in 46.8% latency reduction with a similar area.

Superconducting digital electronics, especially Single Flux Quantum (SFQ), has emerged as a promising beyond-CMOS technology with Josephson junctions (JJ) as the active device. It has the potential to meet the booming demands of lower power consumption and higher operation speeds in the electronics industry and future exascale supercomputing systems. Despite these promises, scaling SFQ circuits remains a serious challenge that motivates the support of multiple SFQ clock domains. Towards this end, this paper analyzes the impact of setup time violations and metastability in SFQ circuits comparing the derived analytical models to their CMOS counterparts. It also proposes new techniques to reduce the average latency in metastability-tolerant SFQ synchronizers, and evaluates their effects on the layout and critical margin of the design. It further extends the proposed model to estimate the Mean Time Between Failure (MTBF) of flip-flop-based synchronizers and shows that their MTBF with the current feature sizes is unaffected by noise, similar to CMOS. Finally, it curve fits this model to simulations using the state-of-the-art SFQ5ee process and shows that a two-flop SFQ synchronizer with a clock frequency of 25 GHz has an estimated MTBF of ~106years.

Superconducting single flux quantum (SFQ) technology using Josephson junctions (JJs) is an excellent choice for the computing fabrics of the future. Current recycling is a necessary technique for the implementation of large SFQ circuits with energy-efficiency, where circuit partitions with similar bias current requirements are biased serially. Though this technique has been verified for small scale circuits, it has not been implemented for large circuits as there is no trivial way to partition the circuit into circuit blocks with separate ground planes. The major constraints for partitioning are (1) equal bias current and (2) equal area for all the partitions; (3) minimize the connections between adjacent ground planes with high-cost for non-adjacent planes. For the first time, all these constraints are formulated into a cost function and it is minimized with the gradient descent method. The algorithm takes a circuit netlist and the intended number of partitions as inputs and gives the output as groups of cells belonging to separate ground planes. It minimizes the connections among different ground planes and gives a solution on which the current recycling technique can be implemented. The parameters of cost function have been initialized randomly along with minimizing the dimensions to find the solution quickly. On average, 30% of connections are between non-adjacent ground planes for the given benchmark circuits.

This paper presents a low-cost, timing uncertainty-aware synchronous clock tree topology generation algorithm for single flux quantum (SFQ) logic circuits. The proposed method considers the criticality of the data paths in terms of timing slacks as well as the total wirelength of the clock tree and generates a (height-) balanced binary clock tree using a bottom-up approach and an integer linear programming (ILP) formulation. The statistical timing analysis results for ten benchmark circuits show that the proposed method improves the total wirelength and the total negative hold slack by 4.2% and 64.6%, respectively, on average, compared with a wirelength-driven state-of-the-art balanced topology generation approach.

This paper presents a novel method for accurate margin calculation of single flux quantum (SFQ) logic cells in a superconducting electronic circuit. The proposed method can be utilized as a figure of merit to estimate the robustness of a logic cell without the need for expensive Monte-Carlo simulations. This is achieved through efficient state-space exploration of all parameters in the cell structure. Using the proposed approach, distinct parameter dispersion (DPD) based yield of SFQ cells increases by 55% on average, compared with state-of-the-art techniques.