Multi-Key Fully Homomorphic Encryption Scheme Over the Integers

Fully Homomorphic Encryption (FHE) schemes enable computations on data encrypted with a single key. Since Gentry’s groundbreaking result, numerous variants of FHE schemes have been proposed, leveraging challenging mathematical problems such as Approximate Greatest Common Divisor (AGCD) problem and Learning with Errors (LWE). López-Alt et al. introduced Multi-Key Fully Homomorphic Encryption (MKFHE), enabling homomorphic computation on encrypted input data using different keys. Subsequent advancements in MKFHE have been proposed, all based on LWE or its ring variant. In this paper, we present a novel MKFHE scheme based on the AGCD problem, which, as per our knowledge, is the first of its kind. Our proposed scheme demonstrates a gradual and additive growth of noise term in ciphertext following each homomorphic addition or multiplication operation.