The remote sensing images have the multi-temporal, multi-semantics and multi-spectral characteristics. In view of the sensitive remote sensing images involving state secret information with low searching efficiency, it is a general trend to conduct a secure outsourcing search for remote sensing images based on a cloud platform. Thus, a scheme of secure outsourcing search for encrypted remote sensing images is proposed. The remote sensing image stored on the cloud platform is first encrypted by the scan mode, and then a double ciphertext is obtained through the exclusive or operation and the Johnson-Lindenstrauss (JL) transformation. The JL-transformed remote sensing images are used to search on the cloud platform, while the exclusive or encrypted remote sensing images are used to decrypt image. The experimental results show that this scheme can effectively guarantee the security of remote sensing images on the cloud platform. Meanwhile, the search accuracy of encrypted images is high and the search efficiency is 98.37% higher than that by homomorphic encryption. Moreover, the computational complexity and communication cost are low, and it is suitable for the deployment on the cloud computing platforms.