Abstract
We consider multi-key fully homomorphic encryption (multi-key FHE) which is the richest variant of fully homomorphic encryption (FHE) that allows complex computation on encrypted data under different keys. Since its introduction López-Alt et al. (On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp 1219–1234. ACM, 2012), numerous proposals have been presented yielding various improvements in security and efficiency. However, most of these multi-key FHE schemes encrypt a single-bit message. Constructing a multi-key FHE scheme encrypting multi-bit messages have been notoriously difficult without loosing efficiency for homomorphic evaluation and ciphertext extension under additional keys. In this work, we study multi-key FHE that can encrypt multi-bit messages. Motivated by the goals of improving the efficiency, we propose a new construction with non-interactive decryption and security against chosen-plaintext attack (IND-CPA) from the standard learning with errors (LWE) assumption. We consider a binary matrix as plaintext instead of a single-bit. Our approach supports efficient homomorphic matrix addition and multiplication. Another interesting feature is that our technique of extending a ciphertext under additional keys yields significant reduction in the computational overhead. More interestingly, when contrasted with the previous multi-key FHE schemes for multi-bit messages, our candidates exhibits favorable results in the length of the secret key, public key and ciphertext preserving non-interactive decryption.
