Paper 2021/1431

Secure and Efficient Multi-Key FHE Scheme Supporting Multi-bit Messages from LWE Preserving Non-Interactive Decryption

Chinmoy Biswas and Ratna Dutta


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 by Lopez-Alt, Tromer and Vaikuntanathan in 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. Keywords: lattice based cryptosystem, multi-key fully homomorphic encryption, learning with errors, multi-bit messages

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
lattice techniquespublic-key cryptography
Contact author(s)
chinmoy88biswas @ gmail com
2021-10-26: received
Short URL
Creative Commons Attribution


      author = {Chinmoy Biswas and Ratna Dutta},
      title = {Secure and Efficient Multi-Key {FHE} Scheme Supporting Multi-bit Messages from {LWE} Preserving Non-Interactive Decryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1431},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.