---
abstract: |
    Some pioneering works have investigated embedding cryptographic properties in compressive sampling (CS) in a way similar to one-time pad symmetric cipher. This paper tackles the problem of constructing a CS-based symmetric cipher under the key reuse circumstance, i.e., the cipher is resistant to common attacks even a fixed measurement matrix is used [multiple]{} times. To this end, we suggest a bi-level protected CS (BLP-CS) model [which makes use of]{} the advantage of the [non-RIP measurement matrix construction]{}. Specifically, two kinds of artificial basis mismatch techniques are investigated to construct key-related sparsifying bases. It is demonstrated that the encoding process of BLP-CS is simply a random linear projection, which is the same as the basic CS model. However, decoding the linear measurements requires knowledge of both the key-dependent sensing matrix and its sparsifying basis. [The proposed model]{} is exemplified by sampling images [as a joint data acquisition and protection layer for resource-limited wireless sensors. Simulation results and numerical analyses have justified that the new model can be applied in circumstances where the measurement matrix can be re-used.]{}

    compressive sampling, restricted isometry property, encryption, known/chosen-plaintext attack, random projection.
author:
- |
    Leo Yu Zhang, , Kwok-Wo Wong, ,\
    Yushu Zhang, [Jiantao Zhou, ,]{} [^1] [^2] [^3]
title: '[[Bi-level Protected Compressive Sampling]{}]{} [^4] '
---

Introduction {#sec:intro}
============

Compressive sampling (CS) has received extensive research attention in the last decade [@Donoho:CSIntro:TIT06; @Candes:IntroCS:SPM08; @Richard:CSIntro:SPM07]. By utilizing the fact that natural signals are either sparse or compressible, the CS theory demonstrates that such signals can be faithfully recovered from a small set of linear, nonadaptive measurements, allowing sampling at a rate lower than that required by the Nyquist-Shannon sampling theorem.

The use of CS for security purposes was first outlined in one of the foundation papers [@Candes:CS:TIT06], in which Candes and Tao suggested that the measurement vector obtained from random [subspace]{} linear projection can be treated as ciphertext since the [unauthorized user]{} would not be able to decode it unless he knows in which random subspace the coefficients are expressed. In this way, the entire CS scheme can be considered as a variant of symmetric cipher, [where the signal to be sampled, the measurement vector and the measurement matrix are treated as the plaintext, the ciphertext and the secret key, respectively]{}. [It is a favorable characteristic that certain kind of data protection mechanism can be embedded into the data acquisition stage. Such a property of CS is of particular importance for data acquisition systems in sensor networks, where each sensor is usually resource-limited and a separate cryptographic layer is too expensive for secure data transmission. Example applications work under this circumstance include visual sensor networks [@winkler2014security], video surveillance networks [@dufaux2008scrambling] and etc. Meanwhile, CS paradigm also found to be useful for medical systems, especially in the case that sampling speed [@lustig2007sparse] and privacy [@barrows1996privacy] are two major concerns.]{} [There are a]{} number of studies exploring the security that [a CS-based symmetric cipher]{} can provide from the computation point of view. For example, it was shown in [@Rachlin:secrecy:08] that the measurement matrix leads to computational secrecy under some attack scenarios, such as brute-force attack and ciphertext only attack (COA). Based on this result, there were many attempts in establishing secure measurement matrices. In [@dautov:establishing:2013], constructing the measurement matrix using physical layer properties and linear feedback shift register (LFSR) with the corresponding $m$-sequence was proposed. [In [@tong2011compressive], Tong *et al.* suggested constructing CS measurement matrix by chaotic sequence for privacy protection in video sequence. In [@Cambareri:TwoClassCS:2013], Cambareri *et al.* employed CS to provide two access levels by artificially carrying out sign flips to a subset of the measurement matrix. In this way, the first-class decoder, who can access full knowledge of the measurement matrix, can retrieve the signal faithfully while the second-class decoder, who can only access partial knowledge of the measurement matrix, subjects to a quality degradation during reconstruction. The work was later extended to multi-class low-complexity CS-based encryption [@cambareri2015low].]{}

[Another research area of the secrecy of CS lies in the information theory frame. It is shown in [@yangsecurity] that CS-based cryptosystems fail to satisfy both Shannon’s and Wyner’s perfect Secrecy. In this context, Cambareri *et al.* [@cambareri2015low] defined an achievable security metric, i.e., asymptotic spherical security, for CS-based cipher. Basically, it states that the statistical properties of the random measurements only leak information about the plaintexts’ energy. Based on this observation, Bianchi *et al.* [@Bianchi:SecRLM:ICASSP14] suggested that re-normalizing every measurement vector and treating the normalized measurements as the ciphertext will lead to a perfect “securized" CS-based cipher with the help of an auxiliary secure channel to transmit the energy of the real measurement vector.]{}

[ It should be noted that all the above security features of CS-based ciphers are obtained under limited attack models, i.e., the adversary is permitted to work out the secret key or plaintext from ciphertext only or to search the entire key space. Under more threatening scenarios, such as known-plaintext attack (KPA) and chosen-plaintext attack (CPA), the adversary can easily reveal the measurement matrix (secret key in a CS-based cipher) if he is able to collect sufficient amount of independent plaintexts. As such, to maintain their respective security features, all the results mentioned above must work in a one-time-sampling (OTS) manner, i.e., the measurement matrix is never re-used. ]{}

[ Assume that a $K\times M$ measurement matrix is produced by using a secure deterministic random number generator (SDRNG) from a secret key shared between the encoder and decoder. We note that this is exactly the case of the traditional one-time-pad (OTP) cipher [@shannon1949communication]. If a sparse signal belongs to $\{0, 1\}^{M}$, it requires exactly $M$ bits to perfectly protect this signal when OTP cipher is applied. For the case of OTS, it requires at least $K\times M$ bits (if the Bernoulli matrix is used) to sample (encrypt) the signal. From this sense, the OTS CS-based cipher indeed reduces the service life of the SDRNG. Meanwhile, generating a different measurement matrix for every signal could be energy-consuming. Additionally, for engineering practice, using the same measurement matrix for multiple signals or signal segments flavors the subsequent source coding stage of multimedia data sensing, as discussed in [@mun2012dpcm; @liu2014joint]. Based on these observations, it is concluded that investigating the behavior of CS-based cipher under the multi-time-sampling (MTS) scenario is both important from the cryptographic and engineering point of view. ]{}

[ The work presented in [@cambareriknown] offers an intimate view for MTS CS-based cipher, where a second-class user in the two-class CS encryption [@cambareri2015low] tries to upgrade the recovery quality by studying only one pair of known-plaintext and ciphertext. Restricting the measurement matrix to the form of Bernoulli matrix, it is shown in [@cambareriknown] that the number of candidate measurement matrices matching a single pair of known plaintext and ciphertext is too huge for the adversary to search for the true one. Still, the result only holds for a single plaintext-ciphertext pair while in typical KPA the adversary can access a large amount of plaintexts and the corresponding ciphertexts. Thus, the true measurement matrix may be determined uniquely. The same argument also applies to the case of CPA. ]{}

[ A straight forward solution to support the usage of CS in MTS scenario is to encrypt the entire or only the significant part of the quantized measurement vector using some conventional cryptographic method, such as AES or RSA. However, as we mentioned earlier, a standalone encryption layer can be too costly for a CS sensor and this approach does not take advantage of the confidentiality provided by CS itself. ]{}

[ Another approach to achieve this goal is to embed other efficient cryptographic primitives in the the CS encoding process. This is exactly the idea of product cipher introduced by Shannon [@shannon1949communication], who suggested combining two or more cryptographic primitives together such that the product is more secure than individual component against cryptanalysis.]{}

[ In [@zeng2012scrambling], Zeng *et al.* proposed a speech encryption algorithm by scrambling the CS measurements. A similar idea was later applied for secure remote image sensing [@huang2015compression]. For the purpose of image acquisition and confidentiality, Zhang *et al.* [@yushu:SCS:14arxiv] suggested scrambling the frequency coefficients before the CS encoding instead of scrambling the CS samples. Note that scrambling the frequency coefficients is a mature technique for multimedia confidentiality in traditional coding system [@Wenjun:FrequencyScrambling:TM03], the main advantage of employing this technique in the CS paradigm is that a so-called “acceptable" permutation can make the column (or row) sparsity level of $2$D signals uniform [@Fang:permutation:TSP13], thus relaxing the restricted isometry property (RIP) of the measurement matrix and flavoring a parallel CS (PCS) reconstruction model. The same technique is also used for privacy protection in cloud-assisted image service [@wu2014low]. Another popular approach to form product cipher for MTS usage of compressive imaging is to employ an optical encryption primitive, i.e., double-random phase encoding (DRPE) technique, such as those proposed in [@deepan2014multiple; @rawat2015compressive; @li2015compressive]. There is also work that try to embed low-complexity nonlinear diffusion into the measurements quantization stage to enhance security of CS-based cipher [@leozhang2015joint]. ]{}

[ Although the above mentioned product ciphers are efficient, generally they cannot resist CPA in MTS scenario (this issue will be discussed in detail in Sec. \[subsec:B\] and \[subsec:C\]). The reason for the difficulty in applying CS-based cipher for MTS usage is due to the characteristic of CS itself: 1) the signal to be sensed must be sparse; 2) the encoding process is linear. For this reason, embedding some high-security primitives before CS encoding will probably make the signal noise-like and not sparse anymore. On the other hand, the introduction of any non-linear cryptographic primitive in CS paradigm will break the linearity of the sampling process and make the recovery infeasible. ]{}

[ Our work moves one step further for the usage of CS-based cipher under MTS scenario. Start with a RIPless reconstruction observation, we study how to embed security features in sparsifying bases under the sparse constraint. In more detail, we suggest a bi-level protected CS (BLP-CS) framework, which can be viewed as a product cipher of the basic CS model and transform-domain encryption technique under the sparse constraint. In particular, we propose several techniques to construct secret key-related sparsifying basis and incorporate them into our BLP-CS model. At the encoding stage, this model can be viewed as a new design of the measurement matrix, thus the encoding is the same as that of the original CS model. However, a successful decoding requires knowledge of the key-dependent sensing matrix and key-related sparsifying basis. In this way, the new product cipher can resist CPA. ]{}

[ This paper makes two contributions in the area of embedding secrecy in CS. On the one hand, we propose a CPA-resistant product cipher by utilizing the confidentiality provided by CS. To the best of our knowledge, this is the first reprot that the CS-based (product) cipher can resist CPA. On the other hand, we incorporate a cryptographic permutation to the CS encoding stage, thus relaxing the RIP of the measurement matrix and flavoring a PCS reconstruction for $2$D sparse signals. In this sense, our work can be considered as an extension of the work presented in [@Fang:permutation:TSP13]. ]{}

The rest of this paper is organized as follows. In Sec. \[sec:II\], we first review the CS framework and present [the CPA on CS-based product ciphers]{}. In Sec. \[sec:secIII\], two techniques for constructing secret key-related sparsifying basis are proposed to establish the bi-level protection model. [Sec. \[sec:discussion\] presents comparisons of the OTS CS-based cipher and our BLP-CS model from complexity and security point of view. ]{} As an application example, the new model is used to sample digital images in Sec. \[sec:Sec4\]. The superiority of the new CS-based image cipher is justified by both theoretical analyses and simulation results. Our work is concluded in Sec. \[sec:conclusion\].

[Security Defects of Existing CS-based Ciphers in MTS Scenario]{} {#sec:II}
=================================================================

[ As we mentioned earlier, there exists some effort to support CS-based cipher for MTS usage [@zeng2012scrambling; @huang2015compression; @yushu:SCS:14arxiv; @wu2014low; @deepan2014multiple; @rawat2015compressive; @li2015compressive]. In this section, we report the fact that all of them fail to resist CPA. To begin with, we briefly review the theory of compressive sampling. ]{}

CS Preliminaries
----------------

We denote a $1$D discrete signal to be sampled as a column vector $\mathbf{x} = (x_1, x_2, \cdots, x_M)^T $. [$2$D signals of size $M = n \times n$, $\mathbf{X} = \left[\mathbf{X}_{i,j}\right]_{i=1, j=1}^{n, n}$, can be vectorized to $1$D format as $\mathbf{x}$ by stacking the columns of $\mathbf{X}$, i.e., $\mathbf{x} = \operatorname{vec}(\mathbf{X})$. ]{} $\mathbf{x}$ is said to be $k$-sparse under $\mathbf{\Psi}$ if there exists a certain sparsifying basis $\mathbf{\Psi} =\{\psi_{i,j}\}_{i=1,j=1}^{M,M}$ such that $\mathbf{x} = \mathbf{\Psi}\mathbf{s}$ and $\|\mathbf{s}\|_0=\# \{\operatorname{supp}{\mathbf{s}}\}=\#\{i:s_i \neq 0\} =k<<M$. [ Here, we emphasize that in almost all of the works about the secrecy of CS, such as [@Rachlin:secrecy:08; @cambareri2015low; @Bianchi:SecRLM:ICASSP14; @cambareriknown; @zeng2012scrambling; @li2015compressive], the role of the basis is ignored or simply treated as an orthnormal matrix. We relax the requirement of the basis to an invertible matrix in this work. The encoding process during CS is a linear projection, i.e.,]{} $$\mathbf{y} = \mathbf{\Phi}\mathbf{x} = \mathbf{\Phi}\mathbf{\Psi} \mathbf{s} =\mathbf{A}\mathbf{s},
\label{eq:samplingspace}$$ [if the sampling is perform in the space/time domain, or equivalently $$\mathbf{y} = \mathbf{\Phi}\mathbf{s} = \mathbf{\Phi}\mathbf{\Psi}^{-1} \mathbf{x} =\mathbf{A}\mathbf{s},
\label{eq:samplingfrequency}$$ if the sampling is performed in the frequency domain.]{}

[The revolutionary finding of CS is that the $K$ dimensional measurement vector $\mathbf{y}$ reserves all the information required for unique and stable recovery of $\mathbf{x}$ even if $k<K \ll M$ provided that the measurement matrix $\mathbf{A}$ obeys some information-preserving guarantees [@Candes:CS:TIT06; @Richard:ProveRIP:2008; @candes2011probabilistic; @kueng2014ripless]. Since the linear systems (\[eq:samplingspace\]) and (\[eq:samplingfrequency\]) are undetermined, both of them have infinite solutions. Considering the signal is sparse, the]{} intuitive way to restore $\mathbf{x}$ is to solve the $l_0$ optimization problem $$\label{eq:l0hard}
  \min \|\mathbf{{s}}\|_0~~\text{subject to }\mathbf{y}=\mathbf{A}  \mathbf{{s}},$$ to obtain $\mathbf{{s}}$ and then recover $\mathbf{x}$ by $\mathbf{x} = \mathbf{\Psi} \mathbf{{s}}$. As stated in [@Tao:BPunderRIP:TIT05], solving this problem is NP-hard because it requires an exhaustive search over all subsets of columns of $\mathbf{A}$.

The convex relaxed form of problem (\[eq:l0hard\]) can be expressed as $$\label{eq:l1opt}
  \min \|\mathbf{{s}}\|_1~~\text{subject to }\mathbf{y} =  \mathbf{A}  \mathbf{{s}}.$$ As proved in [@Candes:CS:TIT06], the solution of the $l_1$ problem (\[eq:l1opt\]) is identical to that of (\[eq:l0hard\]) with overwhelming probability provided that $\mathbf{A}$ satisfies RIP. [Examples of widely accepted matrices satisfying RIP including Gaussian ensemble and Bernoulli ensemble with $K = O(k \log M)$ rows. Up to a logarithmic factor, the number of measurements is optimal [@Candes:CS:TIT06]. Here we note that all the previously mentioned approaches of embedding secrecy into CS-based (product) ciphers work with RIP.]{}

[@Richard:ProveRIP:2008] \[def:RIP\] A matrix $\mathbf{A}$ of size $K \times M$ is said to satisfy the restricted isometry property of order $k$ if there exists a constant $\delta_k \in (0,1)$ such that $$(1- \delta_k) \|\mathbf{x}^{(T)}\|_2^2 \leq \|\mathbf{A}^{(T)} \mathbf{x}^{(T)}\|_2^2 \leq (1+ \delta_k) \|\mathbf{x}^{(T)}\|_2^2$$ holds for all column indices sets $T$ with $\#{T}<k$, where $\mathbf{A}^{(T)}$ is a $K \times \#{T}$ matrix composed of the columns indexed by $T$, $\mathbf{x}^{(T)}$ is a vector obtained by retaining only the entries indexed by $T$ and $\|\cdot\|_2$ denotes the $l_2$ norm of a vector.

[More generally, let the $K$ rows of $\mathbf{A}$, i.e., $\mathbf{a}_1^T, \cdots, \mathbf{a}_K^T$, be i.i.d. random vectors drawn from a distribution, say $F$. The recently developed RIPless CS theory states that the solution of problem (\[eq:l1opt\]) is unique and equal to that of problem (\[eq:l0hard\]) if the number of measurements grows proportionally to the product of coherence parameter and the condtion number of the covariance matrix [@candes2011probabilistic; @kueng2014ripless], as given by Theorem \[theorem:RIPless\]. ]{}

[@kueng2014ripless] \[theorem:RIPless\] Let $\mathbf{s}$ be a $k$-sparse vector and $\omega \geq 1$. The solution of problem (\[eq:l1opt\]) is unique and equal to that of problem (\[eq:l0hard\]) with probability at least $1-e^{-\omega}$ if the number of measurements fulfills $$K = O(\mu(F)  \theta \cdot \omega^2 k \log M),$$ where $\mu$, the coherence parameter, is the smallest number that $$\max_{1\leq i \leq M } |<\mathbf{a}^T, \mathbf{e}_i>| \leq \mu(F)$$ and $\theta$ is the condition number of the covariance matrix $\Sigma= \mathbb{E}[\mathbf{a}\mathbf{a}^T]^{1/2}$ with $\mathbf{a}^T$ being a generic row random vector draw from $F$ and $\mathbf{e}_i$ being the canonical basis vector of dimension $M$.

[ What concerns us about the RIP CS and RIPless CS is that the quantity $\mu(F) \theta$ that governs the number of required measurements for successful $l_1$ reconstruction is different. For Gaussian, Bernoulli and partial Fourier matrices, it is shown that $\mu(F) \theta = O(1)$ in [@candes2011probabilistic]. Moreover, it is easy to find out that $\theta =1$ for unitary matrix and $\theta >1$ for generic matrix[^5]. Moreover, the larger the value of $\mu(F)\theta$, the more the samples we need for exact reconstruction in the RIPless setting. We make us of this fact to design the measurement matrix for security purpose.]{}

[ In the subsequent sections, we will show that almost all the CS-based product ciphers mentioned above, i.e., those proposed in [@zeng2012scrambling; @huang2015compression; @yushu:SCS:14arxiv; @wu2014low; @deepan2014multiple; @rawat2015compressive; @li2015compressive], fail to resist the CPA under MTS scenario due to the fact that these product ciphers work only under the RIP framework. ]{}

[Scrambling in the Measurements Domain or the Frequency Domain]{} {#subsec:B}
-----------------------------------------------------------------

[As described in the previous sections, it is more practical if the same measurement matrix can be re-used multiple times. To this end, there are some attempts trying to incorporate other low-complexity cryptographic primitives to fix the intrinsic security defect of CS in a manner of constructing product ciphers [@zeng2012scrambling; @huang2015compression; @yushu:SCS:14arxiv; @wu2014low]. A common cryptographic technique suitable for this purpose is scrambling (also known as random permutation), which has been widely used in the field of multimedia security [@dufaux2008scrambling; @Wenjun:FrequencyScrambling:TM03]. It should be noted that the works mentioned here and Sec. \[subsec:C\] are based on the RIP theory. Here, we treat the measurement matrix as Gaussian matrix for simplicity[^6].]{}

Roughly speaking, existing works utilizing scrambling for MTS usage of CS can be divided into two classes[^7]:

I.  Scrambling is performed on the measurements, such as [@zeng2012scrambling; @huang2015compression];

II. Scrambling is done in the frequency domain, such as [@yushu:SCS:14arxiv; @wu2014low].

The scrambling process can be characterized by a permutation matrix, which is a square binary matrix that has exactly one non-zero element with value $1$ in each row and each column and $0$s elsewhere.

According to Eq. (\[eq:samplingspace\]), class I CS-based product cipher can be expressed as

[rCl]{} \[eq:encryptionBI\] = \_[K]{} = \_[K]{}\_[K]{} = \_[K]{}\_[K]{} ,

where $\mathbf{x}$ is a $k$-sparse signal with dimension $M$ to be sampled (encrypted), $\mathbf{\Psi}$ is a orthnormal sparsifying basis, $\mathbf{P}_{K}$ is a $K \times K$ permutation matrix, $\mathbf{\Phi}_{K}$ is the Gaussian ensemble and $\mathbf{\hat{y}}$ is the ciphertext to be transmitted or store. A difference between this class of product cipher and the basic CS-based ciphers is that the (equivalent) secret key for the product cipher is the permutation matrix $\mathbf{P}_{K}$ and the measurement matrix $\mathbf{\Phi}_{K}$ while only measurement matrix can be utilized as the key in basic CS-based ciphers. Ideally (from the designer’s point of view), the decoding (decryption) is composed of a two-step reconstruction, i.e.,

[rCl]{} &=& \_[K]{} ,\
\_1   &=& \_[K]{} .

However, since both $\mathbf{P}_{K}$ and $\mathbf{\Psi}$ are orthonormal, $\mathbf{P}_{K}\mathbf{\Phi}_{K} \mathbf{\Psi}$, which is a rotation of $\mathbf{\Phi}_{K}$, possess the distribution of a Gaussian ensemble. Governed by the RIP theory, we can simplify the decoding as a single-step optimization

[rCl]{} \_1   &=& \_[K]{}\_[K]{} = \_[K]{}\_[K]{}.

An unauthorized decoder, who can collect ciphertext for any plaintext in CPA scenario, submits a series of artificial signals $\{\mathbf{x}_j \}_{j=1}^{M} = \{(0, \cdots, 0, 1_j, 0, \cdots, 0)^T\}_{j=1}^M$ to the encryption oracle and concludes $\mathbf{P}_{K}\mathbf{\Phi}_{K} = \left[\mathbf{\hat{y}}_1, \cdots, \mathbf{\hat{y}}_M \right]$ using Eq. (\[eq:encryptionBI\]). It is clear that any further using of the same measurement and permutation matrices for security purpose is doomed to fail.

[ For the class II CS-based product ciphers, the same treatment can be applied. According to model (\[eq:samplingfrequency\]), we can rewrite the encoding (encryption) process as $$\mathbf{\hat{y}} = \mathbf{\Phi}_{K} \mathbf{P}_{K} \mathbf{s} = \mathbf{\Phi}_{K} \mathbf{P}_{K} \mathbf{\Psi}^{-1}\mathbf{x}. \nonumber$$ Once again, $\mathbf{\Phi}_{K} \mathbf{P}_{K}$ can jointly working as the measurement matrix and it can be revealed by $M$ independent chosen plaintexts and their corresponding ciphertexts. ]{}

In the following discussion, we will explain how scrambling (known as “acceptable¡± permutation in [@Fang:permutation:TSP13]) relaxes the RIP requirement of the measurement matrix for $2$D sparse signals. Without loss of generality, let $\mathbf{X} = \left[\mathbf{X}_{i,j}\right]_{i=1, j=1}^{n, n}$ be a $2$D signal sparse in the canonic sparsifying basis and $\mathbf{k} = (k_1, k_2, \cdots, k_n)$ be a row vector whose entry denotes the number of nonzero elements of the columns of $\mathbf{X}$. A column by column sampling process of $\mathbf{X}$ can be summarized as $$\mathbf{Y} = \left[\mathbf{y}_1, \mathbf{y}_2, \cdots, \mathbf{y}_n \right]= \mathbf{\Phi} \mathbf{X} = \mathbf{\Phi} \left[\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_n \right], \nonumber$$ or equivalently

[rCl]{} () = \^T= () = \^T,

where

[rCl]{} = .

The corresponding parallel (column by column) reconstruction is given by

[rCl]{} \[eq:PCSreconstruction\] \_j\_1  \_j &=& \_j,

where $j\in \{1, 2, \cdots, n\}$ and $\mathbf{\Phi}$ being a typical RIP measurement matrix with $O(\|\mathbf{k}\|_{\infty} \cdot \log n )$ rows. As we can see, the accurate reconstruction is proportional to $\|\mathbf{k}\|_{\infty}$ [@Fang:permutation:TSP13]. The smaller $\|\mathbf{k}\|_{\infty}$ is, the fewer rows $\mathbf{\Phi}$ require for correct recovery or the worse RIP constant $\mathbf{\Phi}$ can stand.

The remaining work is to demonstrate that $\|\mathbf{k}\|_{\infty}$ of $\mathbf{X}$ will decrease with large probability if $\mathbf{X}$ is randomly scrambled. Let $\operatorname{vec}(\mathbf{\bar{X}}) = P\cdot \operatorname{vec}(\mathbf{X})$ and $\mathbf{\bar{k}}=(\bar{k}_1, \cdots, \bar{k}_n)$ be the sparsity vector of $\mathbf{\bar{X}}$, we define an acceptable permutation as follows:

A $n^2 \times n^2$ permutation $P$ is said to be acceptable if the following two rules are satisfied:

1.  the expectations of the column sparsity of $\mathbf{\bar{X}}$ are the same, i.e., each column expects the same sparsity level;

2.  the probability that $\|\mathbf{\bar{k}}\|_{\infty}$ deviates from the expected sparsity level observe a power law decay.

The following property demonstrates the role of (secret) random scrambling for $2$D signals which is sparse in space. By swapping time and frequency, reconstruction model (\[eq:PCSreconstruction\]) can be applied to natural $2$D signals, such as images. The examples demonstrating this phenomenon will be provided in Sec. \[sec:Sec4\].

\[pro:permutation\] Uniform random permutation is an *acceptable* permutation for any $n\times n$ $2$D sparse signal $\mathbf{X}$.

[ To prove this, we recall that uniform random permutation refers to choosing a permutation from all the $(n^2)!$ candidates with equal probability. In other words, each non-zero entry of $\mathbf{X}$ will appear at any location of $\mathbf{\bar{X}}$ with probability $1/n^2$ when $\mathbf{X}$ is processed by uniform random permutation.]{}

[ Since there are $\|\mathbf{k}\|_1$ non-zero entries of $\mathbf{X}$ in total, each entry of its permutated version is nonzero with probability $\|\mathbf{k}\|_1/n^2$. Apparently, the expected sparsity level of $\mathbf{\bar{x}}_j$ is $n\times \frac{\|\mathbf{k}\|_1}{n^2}= \|\mathbf{k}\|_1/n$, which meets the requirements of rule 1).]{}

Treat each column of $\mathbf{\bar{X}}$ as realization of $n$ independent, identically distributed random variables, the probability that $\|\mathbf{\bar{k}}\|_{\infty}$ deviates from the expectation $\|\mathbf{k}\|_1/n$ by $t$ can be characterized by

[rCl]{}\
&= & Prob( (\_j (|[k]{}\_j) -\_1/n ) t)\
&& Prob( ( |[k]{}\_j - \_1/n) t)\
&& e\^[-[2nt\^2]{}]{},

where the last inequality is obtained by applying Hoeffding inequality. Hence finishes the proof.

[Concatenation of CS and DRPE]{} {#subsec:C}
--------------------------------

[ As one of the optical information processing technique, image encryption using DRPE has received a lot of research attention since its first appearance in [@Refregier:DRPE:OL95; @javidi1999method]. This cipher was found insecure against various plaintext attacks [@carnicer2005vulnerability; @frauel2007resistance]. In a different context, CS offers a new approach for hologram compression and sensing in the optical domain [@clemente2013compressive; @rivenson2010compressive]. On the one hand, the concatenation of CS and DRPE enjoys a all-optical implementation and substantially data volume reduction. On the other hand, the secrecy provided by CS may enhance the security level of DRPE, and vice visa. These reasons making cascading CS and DRPE a noticeable alternative to support the MTS usage of CS. In the following discussion, we will point out that the later argument is questionable in MTS scenario since the CPA complexity of this model is exactly the same as that of the basic CS model. ]{}

Considering a discrete and bounded[^8] $2$D data $\mathbf{I}=[\mathbf{I}_{i,j}]$, the DRPE encryption can be formulated as

[rCl]{} \_[i,j]{} &=& ( ( \_[i,j]{} (j2p\_[i,j]{}) ) (j2q\_[u,v]{}) ),

where the random spatial phase mask $\mathbf{P}=[\exp(j2\pi p_{i,j})]$ and the random frequency phase mask $\mathbf{Q}=[\exp(j2\pi q_{u,v})]$ are the secret keys, and $\mathcal{FT}(\mathbf{X}) =\mathbf{F}\mathbf{X} \mathbf{F}^*$ with $\mathbf{\cdot}^*$ being the conjugate transpose and $\mathcal{IF}$ being the inverse Fourier transform. The DRPE decryption is omitted here since it is similar to the encryption process. With these notations, we can also divide the encryption schemes based on concatenation of CS and DRPE into two classes:

I.  CS encryption followed by DRPE [@deepan2014multiple];

II. DRPE followed by CS encryption [@rawat2015compressive; @li2015compressive].

Considering a $2$D image $\mathbf{X}$ with $M = n\times n $ pixels is sensed by CS with $K=m \times m$ measurements, the algorithms of class I can be modeled as a separate two-step process, i.e.,

[rCl]{} () = (),\
= ( ( \_[i,j]{} (j2p\_[i,j]{}) ) (j2q\_[u,v]{}) ) , \[eq:DRPE\]

where $\mathbf{\Phi}_{m^2 \times n^2}$, $\mathbf{P}_{m \times m}=[\exp(j2\pi p_{i,j})]$ and $\mathbf{Q}_{m \times m}=[\exp(j2\pi q_{u,v})]$ serve as the (equivalent) secret key in the whole process and $\mathbf{C}$ is the ciphertext to deliver or display. As claimed in [@deepan2014multiple], decoding $\mathbf{C}$ should observe a separate DRPE decryption and CS reconstruction, or by a reversed order in algorithms belonging to class II [@rawat2015compressive; @li2015compressive]. As such, it is demonstrated that an unauthorized user who cannot access full knowledge of $\mathbf{\Phi}$, $\mathbf{P}$ and $\mathbf{Q}$ is not able decrypt $\mathbf{X}$ [@deepan2014multiple; @rawat2015compressive; @li2015compressive].

We investigate the real strength against CPA for the approaches mentioned above by first rewriting Eq. (\[eq:DRPE\]) as a matrix form [@frauel2007resistance], i.e.,

[rCl]{} () & = & (),\
& = & \^\* (),

where $\mathbf{\bar{F}}_{m^2\times m^2}$ is the Kronecker product of the Fourier matrices $\mathbf{F}^*$ and $\mathbf{F}$, $\mathbf{\bar{P}}_{m^2\times m^2} ={\mathop{\mathrm{diag}}}(\operatorname{vec}(\mathbf{P}))$ and $\mathbf{\bar{Q}}_{m^2\times m^2} ={\mathop{\mathrm{diag}}}(\operatorname{vec}(\mathbf{Q}))$ are the DRPE secret key. By construction, $\mathbf{\bar{P}}$ and $\mathbf{\bar{Q}}$ are unitary matrices. So, it is concluded $\mathbf{T}$ is also a unitary matrices. In this concern, $\mathbf{T}\mathbf{\Phi}$ must be a RIP matrix and thus a single-step optimization can be formulated as[^9]

[rCl]{} \^[-1]{}()\_1   () &=& () .

Once again, the attacker who works under CPA assumption can retrieve $\mathbf{T}\mathbf{\Phi}$ faithfully from $M$ independent plaintexts and the corresponding ciphertexts. Moreover, he can use this information to decode (decrypt) any subsequent ciphertexts. Similarly, we can apply the analyses to class II algorithms and obtain the same conclusion.

The Proposed Scheme {#sec:secIII}
===================

[ As reviewed in the previous section, existing proposals [@zeng2012scrambling; @huang2015compression; @yushu:SCS:14arxiv; @wu2014low; @deepan2014multiple; @rawat2015compressive; @li2015compressive] targeting the MTS usage of CS as joint sampling and data protection mechanism fail to resist plaintext attacks. Similarly, it can be concludes that cascading CS, scrambling and DRPE also suffer from the same defect, such as the one suggested in [@liu2013optical]. The underlying reason is that all these three cryptographic primitives are linear and we can always translate the encoding components to a (equivalent) RIP-based measurement matrix. Therefore, the key question is whether it is possible to construct a more secure CS-based product cipher without introducing any computing-intensive cryptographic primitives. We will give a positive solution to this problem by switching from the RIP measurement matrix construction to the RIPless matrix construction. We start with the following example.]{}

Consider a column vector $\mathbf{x}$ of length $M=500$ taking values from $\{0, 1\}$ has a sparsity level $k=10$. Let $F$ denote an independent multivariate antipodal distribution, which is given by $F = \{\pm d_1\} \times \{\pm d_2\} \times \cdots \times \{\pm d_M\}$ with $Prob(d_j)=Prob(-d_j)=1/2$ and $\{d_j\}_{j=1}^{M}$ be positive integers. We take $60$ sensing vectors[^10] from this distribution and get a measurement matrix $\mathbf{\Phi}$ which is further used to sample $\mathbf{x}$. By Definition 1, $\mathbf{\Phi}$ cannot guarantee energy-preserving property thus it is a non-RIP matrix. By construction, we have $\theta = O(\max_j(d_j)/\min_j(d_j))$ and

[rCl]{} (F) && \_[1i M ]{} |&lt;\^T, \_i&gt;|\
&=& max\_j(d\_j) .

In summary, $\mu(F) \theta=O(\max_j(d^2_j)/\min_j(d_j))$ is a non-negligible term and the following straightforward recovery dominated by RIPless theory (see Theorem 1 for detail) $$\min \|\mathbf{\bar{x}}\|_1~~\text{subject to }  \mathbf{y}=\mathbf{\Phi}  \mathbf{\bar{x}} \nonumber$$ returns a solution $\mathbf{\bar{x}}\neq \mathbf{x}$. Set $\mathbf{A} = \mathbf{\Phi}\mathbf{D} = \mathbf{\Phi}\cdot {\mathop{\mathrm{diag}}}(1/d_1,\cdots, 1/d_M)$, the reconstruction can also transformed to a two-step reconstruction compliance with RIP theory after realizing that $\mathbf{A}$ is a Bernoulli matrix, i.e.,

[rCl]{} \_1   &=& (\^[-1]{}) = ,\
&=& .

We compare the recovery techniques described above. Figure \[fig1:RIPandRIPless\] depicts a typical reconstruction result with $d_j \in [1, 60]$, from which we can see that the recovery in the RIP case is exact but the RIPless case is not due to a lack of sufficient measurements.

![ Example of RIPless reconstruction and RIP reconstructions.[]{data-label="fig1:RIPandRIPless"}](RIPless){width="\figwidthb"}

![ Example of RIPless reconstruction and RIP reconstructions.[]{data-label="fig1:RIPandRIPless"}](RIP){width="\figwidthb"}

[ The above example provides a preparatory understanding of how a RIPless matrix construction can be transformed to a RIP one. Still, it cannot be considered as a good CS-based cipher since an attacker can reveal $\mathbf{D}$ from $\mathbf{\Phi}$ by $d_j = |\mathbf{\Phi}_{i,j}|$. Moreover, this technique only works for vector who is sparse in the canonical basis, which is not practical for real signals. In this concern, we apply this finding to the CS model (\[eq:samplingfrequency\]) and devise a so called bi-level protected CS model in a way that the measurement matrix is non-RIP and the reconstruction works under RIP theory. ]{}

[The BLP-CS model will be described in]{} Sec. \[subsec:newmodel\], which can be viewed as product of the CS-based cipher and a transform encryption. Then we propose two methods for key-related sparsifying transformation design, namely, *Type I Secret Basis* and *Type II Secret Basis*.

Bi-level Protection Model {#subsec:newmodel}
-------------------------

[The]{} block diagram of this model is shown in Fig. \[fig:newmodel\], where we suggest using key-dependent sensing matrix, $\mathbf{A}_K$, and secret-related sparsifying basis, $\mathbf{\Psi}_K$, to determine the measurement matrix $\mathbf{\Phi}= \mathbf{A}_K\mathbf{\Psi}^{-1}_K$. [Recalling the above example]{}, we are interested in [the phenomenon that the measurement matrix $\mathbf{\Phi}$ does not satisfy the RIP requirement, while the key-dependent sensing matrix $\mathbf{A}_K$ itself is a RIP matrix.]{} [Referring to Eq. (\[eq:samplingfrequency\])]{}, the sampling procedure can be expressed as $$\mathbf{y} = \mathbf{\Phi}\mathbf{x}
=  \mathbf{A}_K\mathbf{\Psi}^{-1}_K (\mathbf{\Psi}_K\mathbf{s}) = \mathbf{A}_K \mathbf{s}.$$ [It should be noted that the number of measurements (sampling rate) is on the order of $(k \log M)$ even though $\mathbf{\Phi}$ is a non-RIP measurement matrix. This number of measurements fails to meet the minimum requirement defined in Theorem \[theorem:RIPless\], thus makes the correct decoding from $\mathbf{\Phi}$ an impossible task. ]{}

![Block diagram of BLP-CS.[]{data-label="fig:newmodel"}](Newmodel){width="\imagewidtha"}

[To correctly decode (decrypt) $\mathbf{y}$,]{} a legitimate user should first derive $\mathbf{A}_K$ and $\mathbf{\Psi}_K$ from the key scheduling process and then [refer to the following two-step reconstruction]{}

[rCl]{} \_1   &=& =\_K ,\
&=& \_K .

or equivalently

[rCl]{} \_K\^[-1]{}\_1   &=& ,

To fulfill the security requirement, the remaining task is to design two matrices $\mathbf{A}_K$ and $\mathbf{\Psi}_K$ satisfying:

1.  $\mathbf{A}_K$ is a key-related matrix satisfy RIP;

2.  $\mathbf{\Psi}_K$ is a key-related sparsifying basis;

3.  $\mathbf{A}_K\mathbf{\Psi}^{-1}_K$ is a structural non-RIP matrix.

The work of designing a RIP matrix is trivial since it is already clear that Guussian/Bernoulli [@Candes:CS:TIT06] and structurally random matrices [@Do:TSP:SRM12] are competent for this task with overwhelming probability. Therefor, we focus our attention on the designing of $\mathbf{\Psi}_K$ in the following discussions. [It is worth mentioning that the work of designing $\mathbf{\Psi}_K$ satisfying RULE b (also known as transform encryption) is very popular in the filed of multimedia encryption, examples can be found in [@zeng2014perceptual; @pande2012secure; @pande2013securing]. However, the work of designing $\mathbf{A}_K$ and $\mathbf{\Psi}_K$ satisfying RULE c is totally new.]{}

Type I Secret Basis {#sec:TypeI}
-------------------

[ The first type of [secret]{} basis that drawn our attention is the parameterized construction of some familiar transform, such as parameterized discrete wavelet transform (DWT) [@engel2005parameterized; @pande2012secure] and directional discrete cosine transfrom (DCT) [@yeung2012new; @zeng2014perceptual]. Here, we present a parameterized transform based on Fractional Fourier Transform (FrFT) as an example. ]{}

The use of FrFT for security purpose can be dated back to year $2000$, when Unnikrishnan *et al.* [@Joseph:Frft:OL00] suggested to use FrFT for DRPE instead of the ordinary Fourier transform [@Refregier:DRPE:OL95], in order to benefit from its extra degrees of freedom provided by the fractional orders. Generally speaking, performing an order $\alpha$ FrFT on a signal can be viewed as a rotation operation on the time-frequency or space-frequency distribution at an angle $\alpha$. Though FrFT is very popular in optics for its easy implementation, it is not preferred in digital world since complex numbers always cause extra computational load.

To this end, Venturini *et al.* proposed a method to construct Reality-Preserving FrFT of arbitrary order [@Venturini:RealFrct:04]. Here, we deduce the Reality-Preserving Fractional Cosine Transform (RPFrCT) by the virtue of their method. Denote the discrete cosine transform [@Gianfranco:Ftct:TSP02] of size $n\times n$ by $$\mathbf{C} =\left( \frac{1}{\sqrt{n}} \epsilon_l \cos(2 \pi \frac{(2i+1)l}{4n})\right),$$ where $i = 0\sim n-1$, $l= 0\sim n-1$, $\epsilon_0 =1$ and $\epsilon_l= \sqrt{2}$ for $l>0$. The unitary property of $\mathbf{C}$ assures that it can be diagonalized as $$\label{eq:Dct}
\mathbf{C} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^*,$$ where $\mathbf{U} = \{\mathbf{u}_i\}_{i=1}^n$ is composed of $n$ orthonormal eigenvectors, i.e., $\mathbf{u}^*_m \mathbf{u}_i = \delta_{mi}$ and $\mathbf{\Lambda} = {\mathop{\mathrm{diag}}}(\lambda_1, \cdots, \lambda_i,\cdots , \lambda_n)$ with $\lambda_i = \exp(j \varphi_i)$. Replace $\lambda_i$ with its $\alpha$-th power $\lambda_i^\alpha$ in Eq. (\[eq:Dct\]), we can express the Discrete Fractional Cosine Transform (DFrCT) matrix $\mathbf{C}_\alpha$ of order $\alpha$ in the compact form $$\mathbf{C}_\alpha =\mathbf{U} \mathbf{\Lambda}^\alpha \mathbf{U}^*.$$ Having defined $\mathbf{C}_\alpha$, we can derive the RPFrCT matrix $\mathbf{R}_\alpha$ as follows:

-   For any real signal $\mathbf{x}=\{x_l\}_{l=1}^{M}$ of length $M$ ($M$ is even), construct a complex signal of length $M/2$ by $$\mathbf{\widetilde{x}} = \{x_1+ jx_{M/2+1}, x_2+ jx_{M/2+2}, \cdots, x_{M/2}+ jx_{M} \}.$$

-   Compute $\mathbf{\widetilde{y}} = \mathbf{B}_\alpha \mathbf{\widetilde{x}}$, where $\mathbf{B}_\alpha$ is a DFrCT matrix of size $(M/2\times M/2)$, namely, $\mathbf{B}_\alpha =  \mathbf{C}_{\alpha, M/2}$.

-   Determine the RPFrCT matrix $\mathbf{R}_\alpha$ by $$\begin{aligned}
        \mathbf{y} & = & (\operatorname{Re}(\mathbf{\widetilde{y}}), \operatorname{Im}(\mathbf{\widetilde{y}}) )^T \nonumber\\
                   & = & \left(
                        \begin{array}{c}
                            \operatorname{Re}(\mathbf{B}_\alpha) \operatorname{Re}(\mathbf{\widetilde{x}}) - \operatorname{Im}(\mathbf{B}_\alpha) \operatorname{Im}(\mathbf{\widetilde{x}})  \nonumber\\
                            \operatorname{Im}(\mathbf{B}_\alpha) \operatorname{Re}(\mathbf{\widetilde{x}}) + \operatorname{Re}(\mathbf{B}_\alpha) \operatorname{Im}(\mathbf{\widetilde{x}})   \nonumber\\
                            \end{array}
                       \right)\\
                    & = & \left(
                        \begin{array}{cc}
                            \operatorname{Re}(\mathbf{B}_\alpha) & -\operatorname{Im}(\mathbf{B}_\alpha)  \nonumber\\
                            \operatorname{Im}(\mathbf{B}_\alpha) & \operatorname{Re}(\mathbf{B}_\alpha)  \nonumber\\
                            \end{array}
                       \right) \cdot
                       \left(
                       \begin{array}{c}
                             \operatorname{Re}(\mathbf{\widetilde{x}}) \nonumber\\
                             \operatorname{Im}(\mathbf{\widetilde{x}}) \nonumber\\
                            \end{array}
                       \right)  \\
                    & = &    \mathbf{R}_\alpha \mathbf{x} \nonumber.
        \end{aligned}$$

From the construction process listed above, we can conclude that $\mathbf{R}_\alpha$ is orthogonal, reality preserving and periodic. Then, the Reality-Preserving Fractional Cosine Transform of a digital image $\mathbf{X}$ is given by

[rCl]{} \[eq:2dbasis\] = \_ \^[T]{}\_,

where [$(\cdot)^T$ represents the transpose operator, ]{} $\alpha$ and $\beta$ are the orders of the Fractional Cosine Transform along $x$ and $y$ directions, respectively.

Equivalently, we can express this formula as

[rCl]{} () = \^[-1]{} (),

where $\mathbf{\Psi}^{-1} = \mathbf{\Psi}^{T}=(\mathbf{R}_\beta \otimes \mathbf{R}_\alpha)$. To study the sparsifying capability of the proposed parameterized basis,

we carried out experiments [on digital images]{} at different fractional orders $\alpha$ and $\beta$ by using the best $s$-term approximation, i.e., keep the $s$ largest coefficients and set the remaining ones to zero. The recovered result of RPFrCT is compared with that of DCT$2$ using the ratio between their peak signal-to-noise ratios (PSNRs). As expected, the sparsifying capability of RPFrCT raises when $\alpha$ or $\beta$ increases, as shown in Fig \[fig:FrCTDCT\]. When $\alpha, \beta \in (0.9, 1]$, the sparsifying capability of RPFrCT is comparable to that of DCT2. [It is worth mentioning that a similar sparsifying capability was also observed when this transform is applied to $1$D signals [@Venturini:RealFrct:04].]{}

![Comparison between the recovery result of RPFrCT and DCT2 using the best $s$-term approximation at different fractional orders.[]{data-label="fig:FrCTDCT"}](ratio){width="\imagewidth"}

Type II Secret Basis {#sec:TypeII}
--------------------

[ We have demonstrated a technique for parameterized sparsifying basis construction, where the free parameter can be used as the secret key in the BLP-CS model. In this way, the resultant basis satisfies RULE b. However, it still suffers from the same CPA shown in Sec. \[sec:II\] since it fails to meet RULE c. In the subsequent discussions, we propose three kind of operations on an existing basis to make it fulfill RULE c. ]{} We start the deviation by defining equivalent sparsifying bases.

Two basis matrices, $\mathbf{\Psi}$ and $\mathbf{\Psi}'$ are equivalent sparsifying bases if $\mathbf{x} = \mathbf{\Psi}\mathbf{s} = \mathbf{\Psi}'\mathbf{s}'$, $\|\mathbf{s}\|_0 = \|\mathbf{s}'\|_0=k$ holds for any signal $\mathbf{x}$.

\[pro:basischange1\] $\mathbf{\Psi}'$ and $\mathbf{\Psi}$ are equivalent sparsifying bases if

[rCl]{} ’ & = & \_1()\
& = &(d\_1\_1, d\_2\_2, , d\_j\_j, , d\_M\_M),

where $\{d_j\}_{j=1}^M$ are non-zero constants and $\psi_j$ is the $j$-th column of $\mathbf{\Psi}$.

Set $s'_j = \frac{1}{d_j} s_j$ and we have $\|\mathbf{s}\|_0 = \|\mathbf{s}'\|_0$.

We demonstrate that we are able to construct a non-RIP measurement matrix satisfying RULE c. Assume $\mathbf{\Psi}$ is an orthonormal basis and set

[rCl]{} ’ = ,

where $\mathbf{D}={\mathop{\mathrm{diag}}}(1/d_1, 1/d_2, \cdots, 1/d_M)$ and $\{d_j\}_{j=1}^{M}$ are positive integers drawn from certain distribution independently. Let $\mathbf{A}$ denote a Gaussian matrix with i.i.d. entries and calculate $\mathbf{\Phi}$ as

[rCl]{} &=& ()\^[-1]{} ,\
&=& \^[-1]{} \^[T]{}.

Once again, the effect of $\mathbf{\Psi}^{T}$ can be viewed as a rotation of $\mathbf{A} \mathbf{D}^{-1}$ in a $M$ dimensional space, which is energy preserving. By construction, $\mathbf{\Phi}$ is a non-RIP matrix.

\[pro:basischange2\] $\mathbf{\Psi}'$ and $\mathbf{\Psi}$ are equivalent sparsifying bases if $$\mathbf{\Psi}' = \mathbb{F}_2(\mathbf{\Psi}) =  \mathbf{\Psi} \mathbf{P},$$ where $\mathbf{P}$ is a random permutation matrix.

Since $\mathbf{\Psi}\mathbf{s} = \mathbf{\Psi}(\mathbf{P}\mathbf{P}^T)\mathbf{s} = \mathbf{\Psi}' (\mathbf{P}^T\mathbf{s}) =\mathbf{\Psi}'\mathbf{s}'$ , $\|\mathbf{s}'\|_0 = \|\mathbf{P}^T\mathbf{s}\|_0=\| \mathbf{s}\|_0$.

[In the $1$D case, this property implies that random scrambling does not cause any loss of the sparsity level of any given signal. In the $2$D case, as we have shown in Sec. \[subsec:B\], it helps to uniform the column (or row) sparsity level and thus flavors a parallel CS reconstruction technique, which will be exemplified in Sec \[sec:Sec4\].]{}

In addition, if we know or partially know that $\operatorname{supp}(\mathbf{s})$ is localized in a certain $k$-dimensional subspacerather than uniformly distributed in $\mathbb{R}^N$, we can embed more secrets into the sparsifying basis, as stated in Property \[pro:basischange3\]. Here we assume that $\mathbf{\Psi}$ is an orthonormal sparsifying basis for simplicity.

\[pro:basischange3\] $\mathbf{\Psi}'$ and $\mathbf{\Psi}$ are equivalent sparsifying bases if

[rCl]{} ’ & = & \_3()\
& = & (\_1, , \_[j-1]{}, a\_j+b\_k,\_[j+1]{}, , \_M),

where $a,b$ are non-zero constants and $j, k \in \operatorname{supp}(\mathbf{s})$ or $j, k \notin \operatorname{supp}(\mathbf{s})$.

Since $\mathbf{\Psi}$ is orthonormal, $s_j = (\mathbf{\psi}_j, \mathbf{x}) =\mathbf{\psi}_j^T \mathbf{x}$ and we know $s_j = 0$ when $j \notin \operatorname{supp}(\mathbf{s})$. Then the proof for $j, k \notin \operatorname{supp}(\mathbf{s})$ is trivial. For $j, k \in \operatorname{supp}(\mathbf{s})$, set $\mathbf{s}' =  (s'_1, s'_2, \cdots,s'_j, \cdots, s'_k, \cdots, s'_M)^T  \nonumber $ with $$\label{eq:suppunchanged}
s'_i = \left\{
\begin{array}{rl}
s_i/a & \text{if } i = j,  \\
s_i - s_j{b}/{a} & \text{if } i = k, \\
s_i & \text{otherwise}.
\end{array} \right.$$ Then we have

[rCl]{} & = &\
& = & \_ \^[N]{} s\_i\_i + s\_j \_j +s\_k \_k\
& = & \_ \^[N]{} s\_i\_i + (a \_j+b\_k) + (s\_k - )\_k\
& = & ’’

By Eq. (\[eq:suppunchanged\]), we conclude that $\| \mathbf{s}'\|_0 = \|\mathbf{s}\|_0$, hence completes the proof.

Obviously, the operator $\mathbb{F}_3(\cdot)$ can be applied to three or more columns as long as all of the chosen columns are either in $\operatorname{supp}(\mathbf{s})$ or not. Finally, we provide an example to further illustrate Property \[pro:basischange3\]. The grayscale image “Lena" with size $512 \times 512$, as shown in Fig \[fig3:DCT2Energy\]a), is transformed using RPFrCT with orders $\alpha = 0.99$ and $\beta= 0.95$. Figure \[fig3:DCT2Energy\]b) shows the absolute value of the RPFrCT coefficients under the logarithm base. It is clear that the energy of the RPFrCT coefficients matrix is localized, specifically, they are concentrated at the upper-left corner of the four sub-blocks. Thus, we can apply Property \[pro:basischange3\] to the RPFrCT basis $\mathbf{\Psi} = (\mathbf{R}_{\beta} \otimes \mathbf{R}_{\alpha})^T$ accordingly. [A similar effect can be observed in the parameterized DWT and DCT settings.]{}

![a) Original image “Lena"; b) Energy distribution of RPFrCT coefficients of “Lena" using logarithm base.[]{data-label="fig3:DCT2Energy"}](lenna512 "fig:"){width="\figwidth"} a)

\

![a) Original image “Lena"; b) Energy distribution of RPFrCT coefficients of “Lena" using logarithm base.[]{data-label="fig3:DCT2Energy"}](FrCTenergy "fig:"){width="\figwidtha"} b)

[Discussions and Security Analysis]{} {#sec:discussion}
=====================================

[ We have demonstrated the possibility of using BLP-CS as a joint data acquisition and protection model for MTS purpose. This section aims to compare the basic OTS CS cipher and BLP-CS cipher from the viewpoints of complexity and security.]{}

Complexity {#subsec:complexity}
----------

Suppose we have constructed a RPFrCT matrix $\mathbf{R}_{\alpha}$ with appropriate fractional order $\alpha$, a $M\times 1$ signal $\mathbf{x}$ can be sparsified by $\mathbf{R}_{\alpha}\mathbf{x} =  \mathbf{s}$. All the techniques on manipulating the sparsifying basis $\mathbf{R}_{\alpha}^T$ introduced in Sec. \[sec:TypeII\] can be unified to the following matrix notation[^11], i.e.,

[rCl]{} \_[K]{} & = & \_\^T ,

where $\mathbf{D}$, $\mathbf{P}$ and $\mathbf{Q}$ are matrices determined by operators $\mathbb{F}_1$, $\mathbb{F}_2$ and $\mathbb{F}_3$, respectively. It worth mentioning that $\mathbf{x}=\mathbf{\Psi}_{K} \mathbf{s'} = \mathbf{R}_{\alpha}^T \mathbf{s}$ with $\|\mathbf{s'}\|_0 = \|\mathbf{s}\|_0$. Recall from Sec. \[subsec:newmodel\], the encoding of BLP-CS is governed by

[rCl]{} \[eq:blpsampling\] = &=& \_K \_[K]{}\^[-1]{} ,

and the decoding should follow a two-step reconstruction, i.e.,

[rCl]{} \_1   &=& =\_K ,\
&=& \_K . \[eq:blpdecoding\]

Once a well-designed key schedule is given[^12], a trusted third party can produce $\mathbf{\Phi}$, $\mathbf{A}_K$ and $\mathbf{\Psi}_K$ faithfully and transmit them to the encoder and decoder. An alternative option is that the encoder and decoder produce their own matrix key on the air using the agreed key schedule from the same root key. We assume the OTS CS model also adopts the same matrix key generation process for a fair comparison.

[ We first take a look at the encoder side. For the former situation, where the matrix key is produced by the trusted party and then delivered to both the CS encoder and decoder, the encoding complexity of the BLP-CS model outperforms that of the OTS CS model since it does not bring extra communication cost once the key is set. For the later situation, the encoding complexity of the OTS CS model is lower than that of the BLP-CS model at the first glimpse due to the reason that the encoding process of the second model involves a matrix multiplication, i.e., $\mathbf{A}_K \mathbf{\Psi}_{K}^{-1}$, in the key generation process. Nevertheless, since the OTS CS system requires updating the measurement matrix in every sampling, the BLP-CS model outperforms OTS CS after sampling $(2f'+f)/f'$ times. Here, $f$ and $f'$ refer to the complexity of the matrix multiplication and the matrix key generation, respectively. ]{}

[ At the decoder side, the Moore-Penrose pseudoinverse of the sensing matrix $\mathbf{A}_K$ need to be calculated in every iteration of some $l_1$ optimization algorithms [@Boyd:Convex:08], for example, orthogonal matching pursuit [@tropp2007signal]. The complexity of this operation dominates the overall complexity in CS reconstruction. As such, if some off-line techniques can be employed to calculate the pseudoinverse of $\mathbf{A}_K$, the complexity of the reconstruction can be largely reduced. For the OTS CS system, this is impossible since the measurement matrix is never re-used. ]{}

Security
--------

I.  [*Brute-force and Ciphertext-only Attacks*]{}\
    We employ the existing results presented in [@Rachlin:secrecy:08; @cambareri2015low] to show that the BLP-CS preserves most secrecy features of the OTS CS-based cipher under these two attacks.

    [@Rachlin:secrecy:08 Theorem 1 and Corollary 1] \[theorem:wrongrec\] Let $\mathbf{A}$ and $\mathbf{A}'$ be $K\times M$ Gaussian matrices. Let $\mathbf{x}$ be $k$-sparse with respect to the canonic basis and $\mathbf{y}=\mathbf{A}\mathbf{x}$. If $K>k$, then $l_0$ problem (\[eq:l0hard\]) and $l_1$ problem (\[eq:l1opt\]) will yield an $K$-sparse solution $\mathbf{x}'$ with probability one such that $\mathbf{y}=\mathbf{A}'\mathbf{x}'$.

    We first examine the case of brute-force attack, i.e., the attacker try to guess possible measurement matrices and use them for decoding. Referring to Theorem \[theorem:wrongrec\], the $l_0$ or $l_1$ recovery governed by a wrong sensing matrix $\mathbf{A}_K$ will lead to an incorrect reconstruction with probability one. Thus the OTS CS-based cipher can guarantee computational secrecy if the key space is large enough to make systematic search of all the keys (sensing matrices) impossible. This result can be directly applied to our BLP-CS model. According Eqs. (\[eq:blpsampling\]) and (\[eq:blpdecoding\]), we can conclude that BLP-CS is computationally strong even if the attacker can successfully retrieved the secret sparsifying basis $\mathbf{\Psi}_K$. In this concern, the transform encryption approach enhances the security level of the basic CS paradigm.\
    An interesting security feature of the OTS CS cryptosystem under ciphertext-only attack is the asymptotic spherical secrecy [@cambareri2015low]. This type of secrecy states that any two different plaintexts (sparse signals to be sampled in this context) with equal power remain approximately indistinguishable from their measurement vectors when CS operates under the RIP framework. Alternatively, we can intercept this property as only the energy of the measurements carries information about the signal. A bird’s-eye view of why this asymptotic spherical secrecy holds for the OTS CS cipher may refer to the definition of RIP, which states that the CS encoding should obey an energy-preserving guarantee. A theoretical proof about this property can be found in [@cambareri2015low].\
    As we demonstrated in Eqs. (\[eq:blpsampling\]) and (\[eq:blpdecoding\]), the proposed BLP-CS model works under the seemingly RIPless theory if one cannot determine $\mathbf{A}_K$ and $\mathbf{\Psi}_K$. Therefore, the energy-preserving constraint introduced by RIP is unapplicable to this setting. As such, we can conclude that the measurements (ciphertext) carries no information about the signal (plaintext) when a single ciphertext is observed. The BLP-CS and the OTS CS ciphers have the following major difference: when multiple ciphertexts are observed by the attacker, he is aware of the fact that two plaintexts must be similar if their corresponding ciphertexts are close to each other in the Euclidean space. This is caused by the multi-time usage of the same measurement matrix and the linear encoder. Surely the OTS CS cipher is more secure then the BLP-CS cipher from this point of view. Nevertheless, as mentioned in Sec. \[sec:intro\], this is a favorable property that promotes the source coding gain from a system point-of-view [@mun2012dpcm]. This property also finds its way in privacy-preserving video surveillance systems [@tong2011compressive]: assume the attacker happens to know some pairs of plaintext and ciphertext, such as static video scenes and their corresponding measurement vectors, and he want to retrieve privacy-sensitive data from a new intercepted ciphertext. After studying the Euclidean distance of the new ciphertext, he comes to realize that plaintext corresponding to the new ciphertext contains privacy-sensitive data. However, the decryption of this ciphertext requires full knowledge of the matrix key $\mathbf{A}_K$ and $\mathbf{\Phi}_K$. This leads to our discussion of resistance of the BLP-CS cipher with respect to plaintext attacks.

II. [*Plaintext Attacks*]{}\
    As discussed in Sec. \[sec:II\], the data complexity of retrieving a general measurement matrix (the secret key) is $M$ independent plaintexts and their corresponding ciphertexts in any basic CS-based cipher. If the used measurement matrix is Bernoulli, a single plaintext in the form $\mathbf{x}=(2^0, 2^1, \cdots, 2^M)^T$ and the corresponding ciphertext can be utilized to recover the Bernoulli measurement matrix completely[^13]. Based on these knowledge, investigating the resistance of the OTS CS cryptosystem is a trivial work. We hereby focus on the BLP-CS cipher. Referring to Eq. (\[eq:blpsampling\]), the attacker can retrieve $\mathbf{\Phi}$ from $M$ independent plaintext-ciphertext pairs. By construction, $\mathbf{\Phi}$ is a non-RIP matrix. Thus the conclusion drawn from Theorem \[theorem:RIPless\] assures that a straightforward use $\mathbf{\Phi}$ in the $l_1$ optimization problem (\[eq:l1opt\]) is not applicable. Considering that the $l_0$ optimization problem (\[eq:l0hard\]) is NP-hard [@Tao:BPunderRIP:TIT05], the attacker tries to decompose $\mathbf{\Phi}$ with the form $\mathbf{\Phi} = \mathbf{E}\mathbf{F}$, with the constraint that entries of $\mathbf{E}$ should observe certain kind of distribution (Gaussian or Bernoulli). In particular, $\mathbf{F}$ is the product of an elementary matrix and an orthonormal matrix.\
    If the decomposition is unique or the possible number of decompositions is very limited, i.e., polynomial function of $M$, the attacker can determine the matrix key $\mathbf{A}_K$ and $\mathbf{\Psi}_{K}^{-1}$ and the BLP-CS cryptosystem is regarded as fail to resist plaintext attacks. To summarize, we conclude that the number of decompositions should be at least $O(M!)$, thus making the search for the true one inconclusive[^14]. The conclusion is based on the simple fact $\mathbf{E}\mathbf{F} = (\mathbf{E}\mathbf{P})(\mathbf{P}^T\mathbf{F})$, where $\mathbf{P}$ is a $M \times M$ random permutation matrix. As we can see, distribution of all the entries of $(\mathbf{E}\mathbf{P})$ is exactly the same as that of $\mathbf{E}$ and $\mathbf{P}^T$ represents elementary row operation on $\mathbf{F}$. As such, the attacker cannot distinguish the decomposition result $\mathbf{E}$ and $\mathbf{F}$ from $(\mathbf{E}\mathbf{P})$ and $(\mathbf{P}^T\mathbf{F})$.

BLP-CS for Digital Images {#sec:Sec4}
=========================

In this section, the proposed [BLP-CS model is applied as a joint data acquisition and protection layer for digital images. The aim is to provide an intuitive interpretation of how a cryptographic random scrambling can relax RIP of the measurement matrix and substantially reduce the decoding complexity, i.e., parallel reconstruction. Moreover, some other features owned by a basic CS paradigm, such as robust to packet loss and noise, are also observed.]{}

We now consider a $2$D image $\mathbf{X}$ with $M= n\times n$ pixels. If the chosen parameterized transform is RPFrCT, the basis for $\mathbf{X}$ is $(\mathbf{R}_{\beta}^T\otimes \mathbf{R}_{\alpha}^T)$ according to Eq. (\[eq:2dbasis\]). Following the same approach adopted in [@duarte2008single], the encoding stage can be written as

[rCl]{} () = \[\_1, \_2, , \_n\]\^T= (),

where $\mathbf{\Phi}$ is the product of the $K\times M$ key-dependent sensing matrix $\mathbf{A}_K$ and the $M\times M$ key-dependent basis $\mathbf{\Psi}^{-1}_{K}$ having the form

[rCl]{} \^[-1]{}\_[K]{} = \^[-1]{}\^[T]{}(\_\^T\_\^T),

and

[rCl]{} \_K =

with $\mathbf{A}_j =  \mathbf{A}$ for $j \in \{1, \cdots n\}$ being Gaussian matrices. As we discussed in Sec. \[subsec:complexity\], repeatedly using the same sensing matrix for different signal segments can speed up the reconstruction if some off-line mechanism is allowed to calculate the pseudoinverse of $\mathbf{A}$ in advance.

According to Secs. \[sec:TypeI\] and \[sec:TypeII\], $\operatorname{vec}(\mathbf{S}) = [\mathbf{s}_1, \mathbf{s}_2, \cdots, \mathbf{s}_n]^T = \mathbf{\Psi}^{-1}_{K}\operatorname{vec}(\mathbf{X})$ is sparse in the canonical basis. Referring to property \[pro:permutation\] and Eq (\[eq:PCSreconstruction\]), a parallel construction is applied as

[rCl]{} \[eq:pcsrec\] \_j\_1  \_j &=& \_j.

for all $j\in \{1, 2,\cdots, n\}$. Finally, the recovered image is given by $\operatorname{vec}(\mathbf{\bar{X}})=\mathbf{\Psi}_{K} \operatorname{vec}(\mathbf{S})$.

A block diagram of the whole system is depicted in Fig. \[fig:PCSRecons\]. [In summary, this system is a instance of the simplified BLP-CS model.]{}

![Block diagram of BLP-CS for digital images.[]{data-label="fig:PCSRecons"}](ParaRec){width="\imagewidthb"}

To further illustrate how the random scrambling $\mathbf{P}$ relaxes the RIP requirement of the sensing matrix $\mathbf{A}$, we consider another sampling configuration

[rCl]{} () = (),

where $\mathbf{\Phi} =\mathbf{A}_K  \mathbf{\hat{\Psi}}^{-1}_{K}$ with $\mathbf{A}_K$ is the same as defined above and $\mathbf{\hat{\Psi}}^{-1}_{K}= \mathbf{D}^{-1}(\mathbf{R}_{\beta}^T\otimes \mathbf{R}_{\alpha}^T)$. Here, we note that the only difference of $\mathbf{{\Psi}}^{-1}_{K}$ and $\mathbf{\hat{\Psi}}^{-1}_{K}$ is the permutation matrix $\mathbf{P}$. The reconstruction is exactly the same as that of Eq. (\[eq:pcsrec\]). By construction, this is a special form of block-based compressive sampling (BCS) [@Gan:BCS:07], where each block is a column of the frequency coefficients, together with block independent recovery. We call this model BCS-In. We also note that using the smoothed projected Landweber operator can largely improve the BCS reconstrution quality at relatively low extra computation overhead [@fowler2011multiscale]. However, the study of embedding the smoothed projected Landweber operator in the BLP-CS reconstruction is out of the scope of this paper.

[ Four representative images, “Lena", “Peppers", “Cameraman" and “Baboon" of size $512\times 512$ are used as our test images. The tests are carried out under different sampling rate SR $= \frac{K}{M}\times 100\%$. The reconstruction quality is evaluated in terms of average[^15] peak signal-to-noise ratio, APSNR (dB) $=10 \cdot \log_{10}\mathbb{E} \left( \frac{M255^2}{\|\operatorname{vec}(\mathbf{X})- \operatorname{vec}(\mathbf{\bar{X}})\|_2^2}\right)$. The results are listed in Table \[table:PSNRcomparision\] and they support the conclusion of property \[pro:permutation\], i.e., a cryptographic random scrambling helps make the column sparsity level of $\mathbf{S}$ uniform. The last point worth mentioning is that random scrambling is suitable for all kind of $2$D sparse data (all kind of sparsifying coefficients under parameterized orthonormal transform), which extends the result that zig-zag scrambling works for DCT$2$ coefficients [@Fang:permutation:TSP13]. ]{}

  ----------------- ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
       [SR]{}                                                                                                  
                     [BLP-CS]{}   [BCS-In]{}   [BLP-CS]{}   [BCS-In]{}   [BLP-CS]{}   [BCS-In]{}   [BLP-CS]{}   [BCS-In]{}
     [“Lena"]{}        $21.6$       $15.5$       $27.5$       $23.3$       $31.4$       $27.3$       $35.7$       $32.1$
    [“Peppers"]{}      $20.9$       $14.4$       $27.2$       $22.6$       $30.9$       $27.9$       $34.7$       $32.5$
   [“Cameraman"]{}     $19.2$       $13.0$       $24.8$       $21.5$       $28.6$       $27.4$       $32.9$       $32.8$
    [“Baboon"]{}       $17.8$       $9.7$        $20.2$       $17.6$       $22.6$       $21.3$       $25.8$       $25.2$
  ----------------- ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

\[table:PSNRcomparision\]

[The basic CS paradigm that works under RIP theory is known to be robust]{} with respect to transmission imperfections such as noise or packet loss [@dimakis2009lp; @laska2011democracy]. [ Since the new proposal works under the RIPless theory at only the encoder but RIP theory at the decoder, we expect the same property in our approach.]{} To quantitatively study this, we evaluate the robustness of the proposed framework with respect to additive white Gaussian noise (AWGN) and various packet loss rates (PLRs). In the former case, we artificially add a zero-mean normal distribution random sequence with variance $1$ to the measurements while in the latter we randomly discard certain number of measurements governed by PLR. Then we [perform reconstruction on]{} the corrupted measurements. In real applications, PLR can be up to $30\%$ [@Zhao:PacketLoss:03ACM] and we measure the quality of the reconstruction in terms of APSNR at $10\%$, $20\%$ and $30\%$ PLR, respectively. These tests were carried out using the “Lena" image, but similar results were obtained using other images. As observed from Table \[table:NoisePsnr\], our scheme is almost immune to AWGN when we compare the APSNR of the ideal [case]{} and the one with AWGN. In addition, comparing the APSNRs at different levels of PLR, we found that the reduction rate of APSNR is linear to the increasing rate of PLR, which implies that all measurements are of the same importance [@laska2011democracy].

  ------------------------ --------- --------- --------- ---------
           [SR]{}           [0.1]{}   [0.3]{}   [0.5]{}   [0.7]{}
                             21.6      27.5      31.4      35.7
      [BLP-CS AWGN]{}        21.8      27.4      31.3      34.9
   [BLP-CS $10\%$ PLR ]{}    21.7      26.8      30.5      34.1
   [BLP-CS $20\%$ PLR ]{}    20.9      26.2      29.5      32.7
   [BLP-CS $30\%$ PLR ]{}    19.9      25.5      28.5      31.3
  ------------------------ --------- --------- --------- ---------

  : APSNR of the reconstructions under AWGN and various PLRs.

\[table:NoisePsnr\]

Conclusion {#sec:conclusion}
==========

[ To realize the MTS usage of CS cryptosystem, some approaches have already been proposed. Typical examples include scrambling in different domains [@zeng2012scrambling; @huang2015compression; @yushu:SCS:14arxiv; @wu2014low] and cascading the DRPE technique [@deepan2014multiple; @rawat2015compressive; @li2015compressive]. However, we have shown that they fail to satisfy the security requirement. In this concern, we suggest a BLP-CS model by making use of the non-RIP measurement matrix construction. Our approach differs from existing ones in two aspects: 1) the RIPless CS theory is firstly applied for providing the security features of a CS-based cipher; 2) the role of the sparsifying basis for the secrecy of CS is revealed. ]{}

[The security of the BLP-CS model is discussed from various aspects, such as brute-force attack, ciphertext-only attack and plaintext attacks. Special attention has been paid to the plaintext attacks since it is widely accepted that basic CS model is immune to brute-force attack and ciphertext-only attack [@Rachlin:secrecy:08; @cambareri2015low]. Under plaintext attacks, we have demonstrated that the number of candidate sensing matrices and sparsifying basis matrices that match the information inferred by the attacker is huge. Therefore, the searching of the true sensing matrix and sparsifying basis matrix is impossible. ]{}

[ Finally, we apply the proposed model for the purpose of secure compressive image sampling. Both theoretical analyses and experimental results support our expectation, i.e., random scrambling plays a critical role in relaxing the RIP requirement of the measurement matrix and flavoring a PCS reconstruction for $2$D sparse signals. Other features of a basic CS system, such as robust to packet loss and noise, are also observed. ]{}

[^1]: Leo Yu Zhang and Kwok-wo Wong are with Department of Electronic Engineering, City University of Hong Kong, Hong Kong (e-mail: leocityu@gmail.com; itkwwong@cityu.edu.hk)

[^2]: Yushu Zhang is with the School of Electronics and Information Engineering, Southwest University, Chongqing 400715, China (e-mail: yushuboshi@163.com)

[^3]: [Jiantao Zhou is with Department of Computer and Information Science, Faculty of Science and Technology, University of Macau, Macau (e-mail: jtzhou@umac.mo)]{}

[^4]: 

[^5]: Recall that condition number is the absolute value of the ratio between the largest and smallest singular values.

[^6]: This simplification will not affect the security level of the discussed product cipher.

[^7]: Note that embedding scrambling in the time domain actually brings no benefit to security enhancement, but it helps the construction of a structural sampling ensemble [@Do:TSP:SRM12].

[^8]: This always holds true given that continuous data can be adequately sampled.

[^9]: We note that the multiple measurement vector CS model [@duarte2005distributed] should be adopted since $\mathbf{T}$ is a complex matrix.

[^10]: Here, we take $K=60$ because $K>4k$ is an empirical threshold for exact CS recovery in the RIP theory [@Candes:IntroCS:SPM08].

[^11]: We are aware of the fact that any parameterized orthonormal transform with good sparsifying capability can play the role of $\mathbf{R}_{\alpha}^T$.

[^12]: The design of an effective key scheduling process is not considered in this paper since our concern is only the secrecy of CS paradigm. We also note that this is a common treatment for all the state-of-the-art works on this topic.

[^13]: One can imagine the role of a $\{+1, -1\}$ matrix as that of a $\{0, 1\}$ matrix, the proof can be found in [@cambareriknown]. A vector composed by $\{0, 1\}$ can be recovered from the inner product of this vector and $\mathbf{x}$.

[^14]: This is even worse than directly solving the NP-hard $l_0$ problem (\[eq:l0hard\]), who has a complexity $M \choose k$.

[^15]: $\mathbb{E}$ denotes calculate average over $100$ tests.
