Compressed sensing has considerable potential for utilization in various fields owing to its efficient sampling process, but its reconstruction complexity is extremely high. For resource-constrained users, performing the compressed sensing reconstruction (CSR)task is impractical. In particular, the emergence of big data makes this task increasingly time-consuming. Cloud computing resources are abundant and can be employed to solve this task. However, owing to the lack of trust in the cloud, it is necessary to outsource the CSR task without privacy leakages. In this study, we design an efficient secure outsourcing protocol for the CSR task. In the basic outsourcing service model, a client samples a signal via a secure measurement matrix and then sends the acquired measurements to the cloud for CSR outsourcing. The reconstructed signal can not only be utilized by the client, but also by other users. The proposed outsourcing scheme is highly efficient and privacy-preserving, based on three aspects. First, the sensing matrix employed for reconstruction is assumed to be public, because it has a significantly larger size than the signal and consumes considerable resources if encrypted and transmitted. Second, a secret orthogonal sparsifying basis is contained only in the measurement matrix, rather than the sensing matrix. Third, a user can verify the reconstructed signal by leveraging the keys, which are the unique information shared between the client and user. We also demonstrate the privacy and analyze the efficiency of the proposed CSR outsourcing protocol, both theoretically and experimentally.