Aiming at the problems that the security of traditional data hiding algorithms is difficult to be guaranteed and the existing algorithms’ embedded volume is restricted under quantum operation attacks, a reversible data hiding algorithm in encrypted images based on Classic McEliece cryptosystem is proposed. The image pixels are first decomposed into bit planes to generate a data stream, and then encrypted in groups using the Classic McEliece cipher algorithm. In the encryption process, the fault tolerance mechanism in its encryption algorithm is utilized to select the appropriate modulation noise composition and the mapping relationship between the secret data, and the error pattern is modulated into noise to interfere with the encryption process, so as to realize the embedding of the secret data. Finally, the marked encrypted image is obtained by using the exclusive-or encryption and scrambling encryption processes. The experimental results show that the algorithm has the reversibility of carrier recovery. Compared with the existing algorithms, this algorithm’s embedded volume is advantageous, and its highest embedding rate is 4.43548 bpp, which realizes large-capacity data hiding while improving security.