Abstract: Reversible data hiding in encrypted images (RDHEI) is an effective technology that can embed additional data after image encryption, extract data error-free and recover images losslessly. It can not only achieve information transmission, but also ensure the security of the transmission carrier. Therefore, with the development of cloud computing and the growing demand for privacy protection, RDHEI has been widely concerned in recent years. In this paper, a RDHEI algorithm based on pixel prediction and block labeling is proposed. The proposed algorithm focuses on how to achieve high embedding capacity and complete reversibility while ensuring security. In the preprocessing step, the median edge predictor is used to calculate the prediction error. Different from the previous algorithms, the proposed algorithm uses the most significant bit to represent the sign of the prediction errors, and the rest of bit planes represent the absolute values of the prediction errors. The prediction error bit planes are divided into several non-overlapping blocks and these blocks are labeled adaptively. The label map with sparse feature can be compressed effectively via arithmetic coding. In the encryption step, the encryption key is used to generate a pseudo-random matrix to encrypt the original image. In the data hiding step, different methods are used to embed additional data for different types of blocks. Finally, according to the corresponding key, the additional data can be extracted error-free and the original image can be recovered losslessly. Experimental results show that, the proposed algorithm can not only ensure the security and reversibility, but also improve the embedding capacity significantly compared with the state-of-art RDHEI algorithms.