This work proposes a novel scalable image compression method for stream cipher encrypted images. The bit stream in the base layer is produced by coding a series of non-overlapping patches of the uniformly down-sampled version of the encrypted image. An off-line learning approach can be exploited to model the reconstruction error of original image patch based on the intrinsic relationship between the local complexity and the length of the compressed bit stream. This error model leads to a greedy strategy of adaptively selecting pixels to be coded in the enhancement layer. At the decoder side, an iterative, multi-scale technique is developed to reconstruct the image from available pixel samples. Experimental results demonstrate that the proposed scheme outperforms the state-of-the-art in terms of rate-distortion (RD) performance at low and medium rate regions.