Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition

This paper is about the improved multiplcation method of multi-key homomophic encryption scheme. (O(n^2) to O(n) where n is the number of the key.) To achieve performance improvement, we define a new notion ‘homomorphic gadget decomposition’ and apply it into the multiplication algorithm.