In recent years, cloud computing has become the most popular and promising service platform. A cloud user can outsource its heavy computation overhead to a cloud service provider (CSP) and let the CSP make the computation instead. In order to guarantee the correctness of the outsourced processing (e.g., machine learning and data mining), a proof should be provided by the CSP in order to make sure that the processing is carried out properly. On the other hand, from the security and privacy points of view, users will always encrypt their sensitive data first before they are outsourced to the CSP rather than sending the raw data directly. However, processing and verifying of encrypted data computation has always been a challenging problem. Homomorphic Encryption (HE) has been proposed to tackle this task on computations over encrypted data and ensure the confidentiality of the data. However, original HE cannot provide an efficient approach to verify the correctness of computation over encrypted data that is processed by CSP. In this paper, we propose a verifiable outsourced computation scheme over encrypted data with the help of fully homomorphic encryption and polynomial factorization algorithm. Our scheme protects user data security in outsourced processing and allows public verification on the computation result processed by CSP with zero knowledge. We then prove the security of our scheme and analyze its performance by comparing it with some latest related works. Performances analysis shows that our scheme reduces the overload of both the cloud users and the verifier.