  Compressed sensing (CS), breaking the constriction of Shannon-Nyquist
sampling theorem, is a very promising data acquisition technique in the era of
multimedia big data. However, the high complexity of CS reconstruction
algorithm is a big trouble for endusers who are hardly provided with great
computing power. The combination of CS and cloud has the potential of freeing
endusers from the resource constraint by cleverly transforming computational
workload from the local cilent to the cloud platform. As a result, the
low-complexity encoding virtue of CS is fully leveraged in the
resource-constrained sensing devices but its highcomplexity decoding problem is
effectively addressed in cloud. It seems to be perfect but privacy and security
concerns are ignored. In this paper, a secure outsourcing scheme for CS
reconstruction service is proposed. Experimental results and security analyses
demonstrate that the proposed scheme can restrict malicious access, verify the
integrity of the recovered data, and resist brute-force attack, ciphertext-only
attack, and plaintext attack.
