Optimizing Message Range and Ciphertext Storage in Gentry–Sahai–Waters Encryption Using Chinese Remainder Theorem and PVW-like Compression Scheme
Kung-Wei Hu, Huan-Chih Wang, Wun-Ting Lin, Ja‐Ling Wu · Cryptography · 2025
This paper explores advancements in the Gentry-Sahai-Waters (GSW) fully homomorphic encryption scheme (FHE), addressing challenges related to message data range limitations and ciphertext size constraints. We leverage the well-known parallelizing technology—the Chinese Remainder Theorem (CRT)—to tackle the message decomposition, significantly expanding the allowable input message range to the entire plaintext space. This approach enables unrestricted message selection in the GSW scheme and supports parallel homomorphic operations without intermediate decryption. Additionally, we adapt existing ciphertext compression techniques, such as the PVW-like scheme, to reduce the memory overhead associated with ciphertexts. Our experimental results demonstrate the effectiveness of combining the proposed CRT-based decomposition with the PVW-like compression in increasing the upper bound of message values and improving the scheme’s capacity for consecutive homomorphic operations. However, compression introduces a trade-off, necessitating a reduced message range due to error accumulation in successive HE operations. This research contributes to enhancing the practicality and efficiency of the GSW encryption scheme for complex computational scenarios while managing the balance between expanded message range, computational complexity, and storage requirements.