On one hand, homomorphic encryption allows a cloud server to perform computation on outsourced encrypted data but provides no verifiability that the computation is correct. On the other hand, homomorphic authenticator, such as homomorphic signature with public verifiability and homomorphic MAC with private verifiability, guarantees authenticity of computation over outsourced data but does not provide data confidentiality. Since cloud servers are usually operated by third-party providers which are almost certain to be outside the trust domain of cloud users, neither homomorphic encryption nor homomorphic authenticator suffices for verifiable computation on outsourced encrypted data in the cloud. In this paper, we propose verifiable homomorphic encryption (VHE), which enables verifiable computation on outsourced encrypted data. We first introduce a new cryptographic primitive called homomorphic encrypted authenticator (HEA), which may be of independent interest. Informally, HEA can be viewed as a homomorphic authenticator in which the authenticator itself does not leak any information about the message it authenticates. Next, we show that the fully homomorphic MAC scheme, proposed by Gennaro and Wichs recently, is a fully HEA with weak unforgeability in the sense that an adversary is not allowed to make verification queries. We then propose a linearly HEA which can tolerate any number of malicious verification queries, i.e., it achieves (strong) unforgeability. Finally, we define VHE formally, and give a generic construction of VHE based on homomorphic encryption and HEA. Instantiating the generic construction, we derive a fully VHE with weak verifiability as well as a linearly VHE with (strong) verifiability.