In the era of Big Data, enterprises and individuals often upload databases to the cloud for storage and querying, which involves the risk of data leakage. Encrypted databases based on fully homomorphic encryption (FHE) theoretically solve the leakage problem, but the actual deployment of such encrypted databases faces the challenge of high economic costs. Cloud service providers charge for data transfer volume and computation time. Unfortunately, FHE is very expensive in both aspects, with more than five orders of magnitude deterioration compared to directly transmitting and computing plaintext. In this paper, we present STEED, a low-cost encrypted database that tackles both bottlenecks simultaneously. In STEED, we first introduce a FHE framework called BatchPBS, a batch pro grammable bootstrapping framework that improves the recent Liu and Wang (ASIACRYPT 2023) amortised scheme from 6.7 ms to 3 msper ciphertext while adding multi-value bootstrapping (MVB) support. Based on BatchPBS, we propose efficient SQL algorithms in SIMD-style to reduce the computation time and a novel AES transcipher protocol to reduce the data transfer volume. Thus, STEED reduces query time by 13 × and data transfer amount by 165 to 534.9 × compared with SOTA work. Considering end-to-end economic cost of TPC-H query on a database with 1 million rows, STEED reduces the expense of deploying on AWS by $28444.8 per 100 queries. (The code can be found at https://github.com/alibaba-damo-academy/ctl-he)

In order to reduce the multiplicative depth required by high-order polynomial evaluation for homomorphic encrypted data, we propose two novel and low multiplicative depth polynomial evaluation algorithms: an x4-step nesting algorithm based on parity extraction (x4-NAPE) and a parallel algorithm with high data utilization (PAHU). Compared with the conventional Schoolbook method and Horner's rule, x4-NAPE can reduce about 50% of the ciphertext-ciphertext multiplication (CCM) and 75% of the multiplicative depth in the ideal limiting case. While PAHU does not reduce CCM, it can achieve a logarithmic growth of multiplicative depth, with the increase of polynomial length, the growth rate is much slower than x4-NAPE, Schoolbook method, and Horner's rule. Moreover, the hardware architectures of the above polynomial evaluation algorithms for homomorphic encrypted data are investigated and proposed. The proposed hardware architectures are assessed on the FPGA-based reconfigurable hardware platform for FHE named ReMCA. The assessment results demonstrate that under a fixed upper limit of multiplicative depth, our proposed architectures of x4-NAPE and PAHU support 2.67× and 14.3× the range of polynomial lengths of Schoolbook and Horner's rule, respectively. For polynomial evaluation of the same length, compared with architectures of Schoolbook and Horner's rule, our proposed architectures of x4-NAPE and PAHU can achieve up to 1.13× improvement in execution time, up to 50% reduction in multiplicative depth, and up to 2.39× improvement in the depth-time product.

Out-of-place constant-geometry (CG) NTT usually has a simple and uniform memory access pattern. However, out-of-place CG NTT always requires ping-pong memory, resulting in a memory capacity requirement of$2N$. Therefore, we propose a novel radix-4 in-place CG (IPCG) NTT/INTT that reduces the capacity requirement from$2N$to N. An area-efficient and dynamical reconfigurable polynomial multiplier (RAEPM) based on IPCG NTT is proposed to speed up polynomial multiplication over rings. In RAEPM, a Barrett modular multiplier using area-efficient radix-4 booth multiplier is designed to reduce area. In addition, an odd-bank buffer structure is proposed to achieve conflict-free memory mapping independent of polynomial length N and NTT/INTT stage. Moreover, we also proposed an efficient modular reduction for specific numbers and introduced a division equivalent method to eliminate the odd number modular reduction and odd number division in addressing. RAEPM is implemented on Xilinx VC709 FPGA and runs at 294MHz clock frequency. Compared with the prior pure NTT accelerators, under the same parameters, RAEPM achieves a decrease of 39.02%$\sim ~57.63$% in area-time complexity of equivalent LUT, and a decrease of 15.97%$\sim ~49.24$% in area-time complexity of equivalent FF. Compared with the prior NTT-based polynomial multipliers, under the same parameters, RAEPM achieves a decrease of 35.48%$\sim ~90.81$% in area-time complexity of equivalent LUT, and a decrease of 24.24%$\sim ~88.41$% in area-time complexity of equivalent FF.

Efficient binary polynomial multiplication (BPM) implementations are crucial for the practical deployment of bit flipping key encapsulation (BIKE) postquantum cryptography (PQC) due to its computation-intensive nature. To speed up BPM, this brief proposes a scalable and efficient architecture. The proposed architecture employs a novel blockwise sparsity algorithm, which segments sparse polynomials into blocks and leverages interblock and inner block sparsity to eliminate invalid computations, thereby significantly reducing computational operations. Moreover, a scalable block-by-block pipeline structure, along with a multibank random access memory (RAM) for sparse polynomials, is designed to effectively process blocks, resulting in substantial enhancement in performance. Experimental results on Xilinx Artix-7 Field-Programmable Gate Arrays (FPGAs) demonstrate significant performance superiority on the proposed architecture, compared with existing approaches. Across different bandwidth settings of 16, 32, 64, or 128, our design can achieve$4.5\times \sim 35.1\times $,$4.9\times \sim 78.8\times $,$2.5\times \sim 112.7\times $, and$0.5\times \sim 164.2\times $speedup, respectively. Compared with state-of-the-art works, our design achieves$2.8\times \sim 152.0\times $improvements in area efficiency.

Polynomial multiplication over rings constitutes one of the most computationally expensive operations in lattice-based cryptography. To accelerate it, the algorithm based on divide-and-conquer has received extensive attention because it has no strict parameter restrictions compared with the number theoretic transform (NTT). Among divide-and-conquer algorithms, apart from algorithms like Karatsuba and Schoolbook, the Winograd-based method has emerged as a new approach. This is because it can reduce the amount of computation while maintaining the scalability of parallelism. However, the parameters of the existing Winograd-based polynomial multiplication algorithm are conservative, and there is potential for further reducing the computational load. Therefore, we propose a novel and efficient 2-D Winograd-based polynomial multiplication (2-D WPM) algorithm. In this algorithm, we adopt the 2-D Winograd to alleviate the large denominator divisions and large-number multiplications that occur in the conventional 1-D Winograd as the parameter increases. We also propose a division elimination method to eliminate the inevitable divisions in the 2-D Winograd. When the polynomial length is 1024, compared with Schoolbook, 2-D WPM (${m} =3$,${r} =3$) can reduce the number of basic multiplications by 69%. In addition, an efficient polynomial multiplication accelerator for lattice-based cryptography named EPMA is proposed. In EPMA, we design reconfigurable modular arithmetic units to support both prime moduli and power-of-2 moduli. Keeping the full pipelined structure of EPMA, we also fully reuse the input data and the Winograd transformation results to achieve the conservation of hardware resources. EPMA is implemented on Xilinx FPGAs. Compared with previous works on FPGAs, under the same platform and parameters, the area efficiency of EPMA achieves an improvement of$1.22\times $to$18.02\times $. Compared with previous works on CPUs and GPUs, the computing speed of EPMA achieves an improvement of 9.25 to$1294.51\times $.

Polynomial multiplication over rings is a significant bottleneck of ring learning with error (RLWE)-based encryption. To speed it up, the number theoretic transform (NTT) and Toom-Cook-4 (TC4) are commonly used algorithms. Compared with NTT, TC4 is less restrictive and more flexible. However, there is a large opportunity at the algorithm level to improve the Schoolbook algorithm and postprocessing of TC4. Therefore, we propose a novel and efficient Winograd-Schoolbook algorithm that reduces multiplication by 29.1% (N = 256). We also propose a fused and low-density postprocessing that simplifies the algorithm flow and reduces multiplication by 56.25%. In total, these two-part improvements reduce the multiplication of TC4 by 32.47%. A high throughput and efficiency TC4 polynomial multiplier (TCMW) is proposed to speed up polynomial multiplication over rings. In TCMW, a highly parallel full pipelined structure without data waiting between modules is designed to make the parallelism of each module match and avoid the storage of intermediate results. In addition, based on the improved TC4, data buffers with data reuse, elementwise vector multiplication (EWVM) arrays, and efficient interpolation arrays are all designed to improve the performance and efficiency of TCMW. Implemented on the Xilinx VC709 field programmable gate array (FPGA) platform, TCMW can perform a TC4-based$256\times 256$polynomial multiplication over rings with an unrestricted modulus (as long as its factors do not contain 3 or 5) every$1.89~\mu $s at a 385 MHz clock frequency. Compared with prior designs of TC4, under the same conditions, the throughput of TCMW achieves an improvement of$1.91\times \,\,\sim \,\,7.71\times $, and the efficiency of LUT and DSP achieve improvements of$1.31\times \,\,\sim \,\,3.67\times $and$1.87\times \,\,\sim \,\,4.92\times $, respectively.

The growing number of data privacy breaches and associated financial losses have driven the demand for private database queries. Clients typically submit queries that involve both search and computation operations, such as counting students under a certain age or calculating the BMI of employees above a specific age. Existing protocols often face limitations due to reliance on specific-purpose encryption schemes or multiple communication rounds between clients and servers. In this work, we present a unified framework utilizing fully homomorphic encryption techniques to efficiently and privately process queries with search and computation operations. Our contributions include a homomorphic encryption-based private comparison algorithm, called the layered comparison algorithm, which achieves a 2.6-6.6X performance improvement compared to algorithms from prior work; a fast Fourier transform-based preprocessing method enabling accurate large integer arithmetic operations in the encrypted domain; and a scalable database encoding method. Evaluation results demonstrate the practicality of our system, as it processes an aggregated query for a 1k-row encrypted database in approximately 4.53 seconds.

Polynomial multiplication over rings is a significant bottleneck of ring learning with error (RLWE)-based encryption. To speed it up, three algorithms are widely used, i.e., number theoretic transform (NTT), Schoolbook, and Toom-Cook. Compared with Schoolbook and NTT, Toom-Cook can achieve a better trade-off between performance and flexibility. However, in Toom-Cook postprocessing, there are many redundant steps and calculations that have not been eliminated. Therefore, we propose an efficient, compressed, and fused Toom-Cook postprocessing algorithm that reduces the number of steps and at least 33.33% of the arithmetic operations of postprocessing. A highly reconfigurable and efficient Toom-Cook-based polynomial multiplier (TCPM) is proposed to speed up polynomial multiplication over rings. In TCPM, a high-throughput and efficient heterogeneous processing element (PE) array is designed to exploit the parallelism of Toom-Cook, and based on the compressed algorithm, the PE array for postprocessing is scaled down. In addition, as it is provided with a reconfigurable evaluation module, a flexible polynomial data storage module and a universal PE array, TCPM can efficiently map and execute Toom-Cook-2, 3, and 4 on a unified hardware architecture. Implemented on the Xilinx VC709 field-programmable gate array (FPGA) platform, TCPM can perform a Toom-Cook-4-based$256\times256$polynomial multiplication over rings with a modulus of a power of two or a prime every 3.28$\mu \text{s}$at a 360-MHz clock frequency. It achieves a$2.47\times $to$50.11\times $speedup compared with the previous designs.