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
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
Cryptography · Multidisciplinary Digital Publishing Institute · article · 2025
Abstract
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.
Open the resolved locator · 10.3390/cryptography9010014
Metadata licence: OpenAlex metadata (CC0)