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).