Cryptanalysis of Polynomial based Homomorphic Encryption
Alina Trepacheva · 2014
This paper analyses some security issues of symmetric homomorphic cryptosystems based on polynomial ring homomorphisms R[x] ↠ R[x]. The work especially concentrates on the case when ciphertexts are produced via polynomial composition c(x) = r(k(x)), where k(x) is a key, and plaintext space is a finite field Fq. We consider and compare to each other two approaches to carry out a ciphertext only attack on cryptosystem. The first one uses existing algorithms to decompose univariate polynomials. Its complexity depends polynomially on degree of polynomials representing ciphertexts and q. And the second approach is based on computation of polynomial greatest common divisors and polynomial factorization. Its running time depends polynomially on ciphertexts degrees and logarithmically on q.