Cryptology ePrint Archive: Report 2020/565

Homomorphic Computation in Reed-Muller Codes

Jinkyu Cho and Young-Sik Kim and Jong-Seon No

Abstract: With the ongoing developments in artificial intelligence (AI), big data, and cloud services, fully homomorphic encryption (FHE) is being considered as a solution for preserving the privacy and security in machine learning systems. Currently, the existing FHE schemes are constructed using lattice-based cryptography. In state-of-the-art algorithms, a huge amount of computational resources are required for homomorphic multiplications and the corresponding bootstrapping that is necessary to refresh the ciphertext for a larger number of operations. Therefore, it is necessary to discover a new innovative approach for FHE that can reduce the computational complexity for practical applications. In this paper, we propose a code-based homomorphic operation scheme. Linear codes are closed under the addition, however, achieving multiplicative homomorphic operations with linear codes has been impossible until now. We strive to solve this problem by proposing a fully homomorphic code scheme that can support both addition and multiplication simultaneously using the Reed-Muller (RM) codes. This can be considered as a preceding step for constructing code-based FHE schemes. As the order of RM codes increases after multiplication, a bootstrapping technique is required to reduce the order of intermediate RM codes to accomplish a large number of operations. We propose a bootstrapping technique to preserve the order of RM codes after the addition or multiplication by proposing three consecutive transformations that create a one-to-one relationship between computations on messages and that on the corresponding codewords in RM codes.

Category / Keywords: public-key cryptography / Error-correcting codes, fully homomorphic encryption, homomorphic computation, post-quantum cryptography, Reed-Muller (RM) codes.

Date: received 15 May 2020, last revised 15 May 2020

Contact author: mypurist at gmail com

Available format(s): PDF | BibTeX Citation

Note: We propose a fully homomorphic code scheme that can support both addition and multiplication simultaneously using the Reed-Muller (RM) codes which can be applicable for coded computations in distributed systems or stabilizer codes in quantum computing and can be a preceding step for constructing code-based FHE schemes. As the order of RM codes increases after multiplication, we also propose a bootstrapping technique to preserve the order of RM codes after the addition or multiplication by proposing three consecutive transformations that create a one-to-one relationship between computations on messages and that on the corresponding codewords in RM codes.

Version: 20200516:021233 (All versions of this report)

Short URL: ia.cr/2020/565


[ Cryptology ePrint archive ]