This paper addresses the problem of lossy outsourcing, i.e., clients outsource computation needs to the cloud side through lossy channels, which is very common in practice. We focus on the case that the clients transmit 2D sparse signals to the semi-trusted clouds over packet-loss networks, and the clouds provide sparse robustness decoding service (SRDS) for the users. In order to achieve high level of efficiency and security, we propose to jointly exploit parallel compressive sensing for robust signal encoding and employ multiple cloud servers for SRDS. Specifically, prior to encoding, a signal is encrypted by only altering the indices and amplitudes of its non-zero entries. The encrypted signal is sensed using a Gaussian measurement matrix and the generated compressive measurements are then sent to multi-clouds for SRDS, along with the occurrence of packet loss. Each column in compressive measurements can be regarded as a packet and each description consists of a certain number of packets. Each description together with a small portion of support set is distributed to a cloud. When receiving the request from a user, each cloud performs SRDS using the acquired description, where the reconstructed signal is still in encrypted form so that the signal privacy is well preserved. After receiving the reconstructed signal, the user accomplishes the decryption operation. Experimental results show that the encryption algorithm improves compressibility and reconstruction performance compared with the case of no encryption, and the proposed privacy-assured outsourcing of SRDS is highly robust and efficient