In this paper, we propose a novel framework to encrypt surveillance videos. Although a few encryption schemes have been proposed in the literature, they are not sufficiently efficient due to the lack of full consideration of the characteristics of surveillance videos, i.e., intensive global redundancy. By taking advantage of such redundancy, we design a novel method for encrypting such videos. We first train a background dictionary based on several frame observations. Then every single frame is parsed into the background and foreground components. Separation is the key to improve the efficiency of the proposed technique, since encryption is only carried out in the foreground,while the background is skillfully recorded by corresponding background recovery coefficients. Experimental results demonstrate that, compared to the state of the art, the proposed method is robust to known cryptanalytic attacks, and enhances the overall security due to the foreground and background separation. Additionally, our encryption method is faster than competing methods, which do not conduct foreground extraction.