Cost-Effective Optimization and Implementation of the CRT-Paillier Decryption Algorithm for Enhanced Performance

To address the information leak problem in cloud computing, privacy protection techniques are receiving widespread attention. Among them, the Paillier homomorphism algorithm is an effective one since it allows addition and scalar multiplication operations when information is in dencrypted state. However, its computational efficiency is limited by complex modulo operations due to the ciphertext expansion followed by encryption. To accelerate its decryption, the Chinese Remainder Theorem (CRT) is often used to optimize these modulo operations, which makes the decryption chain undesirably long in turn. To address this issue, we propose an eCRT-Paillier decryption algorithm that shortens the decryption computation chain by combining precomputed parameters and eliminating extra judgment operations introduced by Montgomery modular multiplications. These two improvements reduce 50% modular multiplications and 60% judgment operations in the postprocessing of the CRT-Paillier decryption algorithm. Based on these improvements, we propose a highly parallel full-pipeline architecture to remove stalls caused by multiplier reuse in traditional modular exponentiation operations. This architecture also adopts some optimization methods, such as simplifying modular exponentiation units by dividing the exponent into segments and parallelizing data flow by multi-core instantiation. Finally, a high-throughput and efficient Paillier accelerator named MESA is implemented on the Xilinx Virtex-7 FPGA for evaluation. As the experimental result shows, it can complete a decryption within 0.577ms under a 100 MHz clock when using a 2048-bit key. Compared with previous works in the identical conditions, MESA can achieve a 1.16 × to 313.21 × increase in throughput, as well as 2.59% to 96.04% improvement in the Area Time Product (ATP).