Homomorphic encryption technique can be used for protection of data privacy, and some algebraic operations can be implemented on the ciphertext data. This is very useful in the field of cloud computing security, such as analyzing and processing the encrypted data in cloud without exposing the content of data. Addressing privacy protection and data security problems in cloud computing, this paper proposes a robust and reversible image watermarking algorithm in homomorphic encrypted domain. The algorithm includes five aspects:(1) The original image is divided into a number of non-overlapping blocks and each pixel in a block is encrypted with Paillier cryptosystem to obtain the encrypted image; (2) The statistical values of the encrypted blocks can be retrieved in encrypted domain by employing modular multiplicative inverse (MMI) method and looking for a mapping table. After that, watermark information can be reversibly embedded into encrypted image by shifting the histogram of the statistical values with the homomorphic property of Paillier cryptosystem; (3) On the receiver side, the marked histogram of the watermarked and encrypted image can be obtained for extraction of the watermark from the marked histogram. The encrypted image can be restored by inverse operations of histogram shifting in the embedding phase; (4) The marked histogram can be obtained from the directly decrypted image. This is followed by the watermark extraction and restoration of original image; (5) The watermark can still be extracted correctly under some attacks (such as JPEG/JPEG2000 compression and additive Gaussian noise) to some extent on the watermarked and decrypted image. The proposed method achieves embedding information bits directly into the encrypted image without preprocessing operations on the original image, and can extract the watermark and restore the encrypted image in encrypted domain or the original image in plaintext domain after decryption. Besides, the watermark is robust to those common image processing operations. The experimental results have shown the validity of the proposed scheme.