Privacy protection of surveillance videos is an important issue because of the pervasiveness of surveillance cameras. Region of interest (RoI) privacy protection prefers encrypting limited privacy-sensitive areas to encrypting the entire video because of the resource-tightened Internet of Things devices. However, many cryptographic technologies now applied in privacy protection, e.g., AES and RSA, are not efficient to meet the real-time requirement for surveillance videos. A lightweight encryption approach is then devised based on layered cellular automata (LCA). Using our approach, the extracted RoIs are fed into the initial state of an 8-layer cellular automata, which is driven by the randomly selected rules for the LCA’s state transitions. As a result, all RoIs are encrypted independently and synchronously. The encrypted RoIs are stored at the camera side and can be used by authenticated users through an on-demand manner. The surveillance video without RoIs can be watched in real-time by any user online. Theoretical analyses and experimental results show that our approach is both efficient and effective.