Provable Security of RM Code based FHE Scheme

Abstract

Based on the hardness of decoding noisy codewords, coding theory was recently recognized as a potential and well established cryptographic primitive. While keeping the benefit of decoding noisy codewords, coding theory may be utilized to develop implementable homomorphic encryption systems with restricted capacity. Using error correction codes (ECC), a code-based homomorphic encryption system [1] [2] has been proposed and implemented. These designs have evolved into intriguing attempts at developing an implementable partial homomorphic encryption (PHE) method that does not require a computationally demanding bootstrapping phase. The techniques allow for unlimited number of addition operations while keeping the ciphertext size constant. However, using the existing schemes, multiplicative homomorphism is not instantly malleable. The current study is an effort to provide a system for designing an fully homomorphic encryption (FHE) utilizing any error correcting code based on coding theory. The development of a code-based homomorphic encryption scheme with homomorphic addition operations is a straightforward approach, however homomorphic multiplication is not possible with existing developments. The current work tries to show that a Reed-Muller (RM) error correcting code may be utilized to successfully develop multiplication operations, therefore transforming it fully homomorphic. While keeping the benefit of computational cost of ECC, the code-based homomorphic encryption method is effectively turned into the RM code -based FHE scheme (RMFHE). The RMFHE structure has been theoretically proven, and extensive experiments at various security levels have been conducted [14]. In this study, the hardness of RMFHE scheme to an attacker is reduced to the intractable decisional synchronized codeword problem (DCSP).