Fully Homomorphic Encryption Based on Approximate Matrix GCD
The authors first introduce Approximate Matrix GCD problem (AMGCD), and construct public key encryption schemes based on AMGCD. Then, they define a variant of AMGCD and design a new Fully Homomorphic Encryption scheme (FHE) based on the variant AMGCD, whose security depends on the hardness assumption of the variant AMGCD problem. They construct a new fully homomorphic encryption schemes, which are based on the trapdoor function of an approximate matrix GCD over the integers. Their first contribution is to design new trapdoor function based on (approximate) Matrix GCD problem (MGCD).