Secure and efficient multi-key FHE scheme supporting multi-bit messages from LWE preserving non-interactive decryption

• Published in: Journal of ambient intelligence and humanized computing 2023-12, Vol.14 (12), p.16451-16464
• Main Authors: Biswas, Chinmoy, Dutta, Ratna
• Format: Article
• Language: English
• Subjects: Algorithms; Artificial Intelligence; Cloud computing; Computational Intelligence; Cryptography; Cybersecurity; Data encryption; Efficiency; Encryption; Engineering; Messages; Multiplication; Original Research; Protocol; Robotics and Automation; User Interfaces and Human Computer Interaction
• ISSN: 1868-5137; 1868-5145
• DOI: 10.1007/s12652-022-03864-3

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.