Miyaji Laboratory

Lattice-based cryptographic schemes are promising candidates for post-quantum cryptography. Among them, the Module Learning with Errors (MLWE) problem is of particular importance, as it underlies two of the three schemes standardized by the U.S. National Institute of Standards and Technology (NIST). The Ring Learning with Errors (RLWE) problem, a structured variant of MLWE, forms the basis of several homomorphic encryption schemes, including Torus Fully Homomorphic Encryption (TFHE) and the Cheon-Kim-Kim-Song (CKKS) scheme. RLWE-based homomorphic encryption enables computations to be performed directly on encrypted data, but repeated homomorphic operations cause ciphertext noise to grow, eventually leading to decryption failure. Bootstrapping techniques address this issue by refreshing ciphertext noise, and Functional Bootstrapping (FBT) further allows the direct evaluation of functions on encrypted data. In TFHE, the Chaining method composes multiple FBT operations while reducing the number of costly FBT applications to linear order; however, TFHE does not support Single Instruction Multiple Data (SIMD) parallelism. This thesis proposes a chaining method with efficient SIMD parallelism for RLWE-based cryptosystems, focusing on multi-precision carry-propagation addition and comparison. By interpreting RLWE samples as CKKS ciphertexts, we construct a chaining structure in which FBT operations are sequentially applied in the CKKS ciphertext space. We show that the number of FBT applications grows linearly as O(D) for D-digit integers, and that correct function outputs are obtained after mapping the ciphertexts back to the RLWE representation. Experimental results demonstrate speedups of 52.9-55.5 × for multi-precision addition and 36.0-42.0 × for multi-precision comparison per SIMD slot compared with TFHE-based chaining. These results provide a foundation for extending chaining methods to a broader class of functions in SIMD-enabled RLWE-based homomorphic encryption schemes.