Abstract To enhance the confidentiality and the robustness of double image encryption algorithms, a novel double-image compression-encryption algorithm is proposed by combining co-sparse representation with random pixel exchanging. Firstly, two scrambled plaintext images are expressed by the co-sparse analysis model with different row-scrambled basis matrices while the co-sparse representations could be regarded as the intermediate ciphertext. Subsequently, the co-sparse representations are compressed and encrypted concurrently by compressive sensing. Furthermore, the corresponding measurements obtained are processed by the random pixel exchanging operator and the Arnold transform. Finally, the corresponding results are combined into an enlarged image and then the resulting image is re-encrypted by the discrete fractional angular transform to improve the security of the whole algorithm. A series of numerical simulations are carried out to show the security performance of the proposed double-image compression and encryption algorithm.