Abstract: A novel reversible data hiding in encrypted domain is proposed based on block sorting and histogram modification. The first work divides image into blocks and blocks sorting, and each block is permuted by scrambling encryption. Then, the histogram of each block is modified to vacate room for secret data. Finally, the receiver can decrypt firstly and then extract data, the inverse process is also viable. Experiments show that the operator of data extraction and image decryption is completely separable in the proposed method, and compared with the existing methods, the proposed method has improved embedding capacity while maintaining zero error rate, and has better image quality while under-capacity.