This paper proposes a novel scheme of reversible steganography in encrypted domain based on Learning With Errors (LWE). The original data is encrypted by the cryptographic algorithms with LWE. Then additional data could be embedded into the cipher text. With embedded cipher text, the additional data can be extracted by using data-hiding key, and the original data can be recovered by using encryption key, and the processes of extraction and decryption are separable. By deducing the error probability of the scheme, the standard deviation of noise sequence which directly related to the scheme’s correctness is mainly discussed, and reasonable range of the standard deviation is obtained by experiments. The probability distribution function of the embedded cipher text is deduced, that proves the embedded cipher text is not detective. The proposed scheme based on encrypted domain can apply to different kinds of media vehicle such as text, image or audio. Experimental results demonstrate that the proposed scheme can not only achieve statistical security without degrading the quality of encryption or data embedding, but realize that 1 bit original data can maximally load 1 bit additional data in encrypted domain.