The polynomial approximate common divisor problem and its application to the fully homomorphic encryption

We propose and examine the approximate polynomial common divisor problem, which can be viewed as a polynomial analogue to the approximate integer common divisor problem. Since our problem is rather new, we perform extensive cryptanalysis, applying various known attacks against the structurally similar problems. Moreover, we propose a small root finding algorithm for multivariate modular equation system, and apply it to the proposed problem. Those analyses confirm that the proposed problem is difficult with appropriate parameters.Additionally, we construct a simple somewhat homomorphic encryption scheme, which can efficiently accommodate large message spaces. When the evaluation of a low degree polynomial of very large integers is required, our scheme is more efficient than the recent RLWE-based scheme, YASHE, by Bos et al. (2013). In particular, multiplication is ten times faster when evaluating degree-10 polynomial of 1638-bit integers. We convert this scheme to a leveled fully homomorphic encryption scheme by applying Brakerski’s scale invariant technique, and the resulting scheme has features similar to the variant of van Dijk et al.’s scheme by Coron et al. (2014). Our scheme, however, does not use the subset sum, which makes its design much simpler.