In this paper, we propose L0 norm optimization in a scrambled sparse representation domain and its application to an Encryption-then-Compression (EtC) system. We design a random unitary transform that conserves L0 norm isometry. The resulting encryption method provides a practical orthogonal matching pursuit (OMP) algorithm that allows computation in the encrypted domain. We prove that the proposed method theoretically has exactly the same estimation performance as the nonencrypted variant of the OMP algorithm. In addition, we demonstrate the security strength of the proposed secure sparse representation when applied to the EtC system. Even if the dictionary information is leaked, the proposed scheme protects the privacy information of observed signals.

In this paper, we propose a secure computation of sparse coding and its application to Encryption-then-Compression (EtC) systems. The proposed scheme introduces secure sparse coding that allows computation of an Orthogonal Matching Pursuit (OMP) algorithm in an encrypted domain. We prove theoretically that the proposed method estimates exactly the same sparse representations that the OMP algorithm for non-encrypted computation does. This means that there is no degradation of the sparse representation performance. Furthermore, the proposed method can control the sparsity without decoding the encrypted signals. Next, we propose an EtC system based on the secure sparse coding. The proposed secure EtC system can protect the private information of the original image contents while performing image compression. It provides the same rate-distortion performance as that of sparse coding without encryption, as demonstrated on both synthetic data and natural images.