Recently, compressed sensing (CS) cryptosystem has received a lot of interest. However, this cryptosystem is vulnerable to chosen-plaintext attack (CPA) because the CS sampling process is a linearity process. To solve this problem, we propose a novel CS-based cryptosystem by using negative-positive transformation (NPT) in this paper, which embeds a NPT operation in the CS sampling process. First, the image is pre-processed by using NPT operation. Then, the cipher image is re-encrypted by using CS. Last, the compressed ciphertext is quantized into bits. Since the introduction of NPT operation destroys the linearity of sampling process, our method can resist CPA. Compared with previous CS-based cryptosystems, the proposed cryptosystem has two advantages: 1) It achieves effective privacy protection against CPA; 2) It has better compression performance.
Compressed sensing (CS) has received a lot of attention recently [1], [2], which is capable of efficiently capturing and recovering a signal through a few of linear measurements. When CS was applied in secure applications, a secure CS (SCS) framework is proposed, where the measurement matrix is used as a key since the unauthorized user cannot recover the signal without the knowledge of the measurement matrix. However, when the entire measurement matrix is considered as a secret key, the storage space and transmission overhead for the key are too large. To overcome this difficulty, some pioneers proposed that we can generate the measurement matrix by chaotic functions [3-5], such as Logistic map [3], Skew tent map [4] and Logistic-Tent map [5]. The initial value which is utilized to generate the chaotic measurement matrix can be used as the key. This strategy saves the storage space and transmission overhead for the key significantly, which makes CS theory more attractive for secure applications.
In [6], the authors proved that SCS can guarantee the computation secrecy, since the adversary cannot figure out the right key by exhaustive searching in its key space. However, this cryptosystem fails to satisfy Shannon’s perfect secrecy [7]. In this context, an achievable security metric for CSbased cryptosystem called asymptotic spherical security is defined in [8]. In [9], the authors demonstrated that only the energy information of the signal is obtained by the adversary who gets the CS samples. Therefore, it is recommended that the CS measurement vector is needed to be normalized before sending it into the channel.
In [10], the authors show that CS-based cryptosystem is vulnerable to known-plaintext attack (KPA). In [11], a quantitative analysis for the CS-based cryptosystem against KPA is performed, which shows that this cryptosystem can resist KPA if the adversary only collects one pair of the plaintext and the corresponding ciphertext. On this basis, some pioneers suggested that the CS-based cryptosystem should update the measurement matrix [12-14] for every signal.
In order to use CS in multi-time-sampling (MTS) scenario, a novel CS-based cryptosystem by using negative-positive transformation (NPT) is proposed in this paper, which embeds a NPT operation [15] in the CS sampling process to achieve effective privacy protection against CPA. First, the image is preprocessed by using NPT operation. Then, the cipher image is re-encrypted by using CS. Last, the final compressed ciphertext is quantized into bits. Since the introduction of NPT operation destroys the linearity of sampling process, the proposed method can provide effective privacy protection against CPA. The proposed cryptosystem has two advantages. First, it achieves effective privacy protection against CPA. Second, it has better compression performance. The contribution of this paper is that a CS-based cryptosystem with embedding NPT operation is proposed, which can achieve effective privacy protection against CPA.
Consider a signal x RN , which can be represented as where φ RNN is a basis matrix and θ RN is a coefficient vector.
The sampling process of CS is a linear projection, i.e., x = φθ , y = Φx , where Φ RM（NM N）is a measurement matrix and y RM is the measurement vector of x . The signal recovery can be achieved from the measurement vector y by solving xˆ = arg min φT x 1 s.t. y=Φx .
x 2.2.
When CS is used in simultaneous compression-encryption applications, the measurement matrix can be generated by chaotic functions [3-5]. For example, Frunzete et al. [4] proposed to construct the measurement matrix Φ by Skew tent map system:
zk ， 0<zk <
zk+1 = T[zk ; ]=
1-zk (1- ), zk <1
zM
zM +1
zMN −M
zMN −M +1 ,
zMN −1
X（i, j）, R(i, j)=0
Z（i, j）=
255-X（i, j）, R(i, j)=1
where the control parameter (
To construct the measurement matrix, iterate Skew tent map system governed by (
where the scalar 2 M is used for normalization. 2.3.
NPT operation is a lightweight image encryption method which can be expressed by where X RNN , Z RNN and R RNN are the original image, the cipher image and the random binary matrix, respectively. X（i, j）, Z（i, j）and R（i, j）are the entries of X , Z and R located in（i, j）, respectively.
We can construct a random binary matrix by using Skew tent map system with two steps:
(
1, A(i, j) median(vec(A))
R（i, j）= 0，A(i, j) median(vec(A)), where vec() reshapes a matrix into a vector and median() calculates the median. 2.4.
It has been proved that CS-based cryptosystem is vulnerable to CPA due to the linearity of the CS sampling process [10]. By making full use of the linearity of the CS sampling process, the adversary can easily obtain the secret measurement matrix. For example, if the adversary uses an artificial chosen plaintext x = 1 0 0T as the input of the CS-based cryptosystem, then the first column of measurement matrix is revealed. Therefore, we can conclude that the CS-based cryptosystem cannot provide effective privacy protection against CPA. The reason why this cryptosystem is vulnerable to CPA is due to the linearity of sampling process.
In order to resist CPA, a novel CS-based cryptosystem by using NPT is proposed. The overall architecture of the proposed scheme is shown in Figure 1. 3.1.
According to the discussion above, the CS-based crypto-system is vulnerable to CPA due to the linearity of the CS sampling process. To solve this problem, we embed a non-linear operation called NPT in the CS sampling process, which breaks its linearity. The main encoding steps include three steps.
Step 1: Use NPT operation to preprocess the 2D image before CS encoding
Z = E（X）,
yi = Φzi ,
Y = ΦZ ,
(
Specially, in this paper, we use NPT operation to realize the above encryption function. The
NPTbased image encryption can be achieved by using (
In order to simplify the encoder, we use parallel CS (PCS) to sample the cipher image. It contains two sub-steps.
(
(
For the whole intermediate ciphertext, the above sample process can be expressed by where Y = y1, y2,..., yN RMN is the final compressed ciphertext.
Step 3: Y is quantized into bits by using scalar quantization (SQ).
When the recipient receives the keys (e. g., K1 and K2 ), the random binary matrix R and the chaotic measurement matrix Φ will be exactly generated. Now we will study CS reconstruction problem in this subsection.
By taking the NPT-based image encryption into consideration, we can recover image by solving Xˆ = arg min ΨXΨ T 1 s.t.Y = Φ E( X ) ,
X (11) where Ψ RNN is a wavelet basis matrix.
The above problem can be solved by using projected Landweber with embedding decryption (PLED) algorithm [14]. The detailed steps are summarized below.
Input: Φ RMN , Y RM N , Ψ RNN , R+ , Cmax Z + , and is a factor which controls the convergence speed.
Initialization: n = 0 ; Zˆ（0）= ΦT (ΦΦT )−1Y , where Zˆ（0） is the initial estimation of Z ; Xˆ（0）= E-（1Zˆ（0））, where E-（1）is the decryption function and Xˆ（0） is the initial estimation of X .
Stop condition 1 Xˆ（n）− Xˆ（n−1） F or n Cmax .
N Iteration While the stop condition is not satisfied.
Step 1: Bivariate shrinkage [16]. It includes three sub-steps.
(
D(n) = ΨXˆ (n)Ψ T .
ˆ
D(n) = Th(Dˆ(n), ) , where Th( ) is a denotes a bivariate shrinkage operation and is a control factor. The bivariate shrinkage operation can set the coefficients with small absolute value to zero. Therefore, after bivariate shrinkage, we can obtain a sparse solution. The reader can refer to [16] for more details about bivariate shrinkage function.
(
Step 2: Update the iterative guess by projection operation.
(
Step 3: Update the index: n = n + 1 .
End while.
Output: the recovered image Xˆ = Xˆ（n）. 3.3.
In this part, we will verify that the proposed CS-based cryptosystem can achieve effective privacy protection against CPA. Combine (8) and (10), we can see that the sampling process for X can be expressed by
y = Φ E（X）, (12)
According to (12), we can see that the CS sampling process for X can be regarded as a non-linear operation. Since the linearity of the CS encoding process is destroyed, our method can resist CPA. To demonstrate this, let us consider an example.
Example 1: Suppose the size of the image is 4×4, the sampling ratio is set to be 0.5, and the secret matrix Φ can be expressed by Φ = Φ ：,1 Assume that the random binary matrix is Φ ：,2 Φ ：,3 Φ ：,4 , where Φ ：,i R21 is the i -th column of Φ .
Now, we demonstrate that the adversary cannot reveal the secret measurement matrix when NPT operation is embedded in the CS encoding process. In order to reveal the first column of the measurement matrix, the adversary use the cryptosystem to encrypt an artificial chosen plaintext 1 0 0 0 X = 00 00 00 00 . (14) 0 0 0 0
Obviously, for traditional CS-based cryptosystems, if this artificial chosen plaintext is used, the first column of the measurement matrix is revealed. However, in the proposed method, we embed a NPT operation in the CS sampling process. Before sampling the artificial chosen plaintext, the plaintext is encrypted by using NPT operation. After NPT-based encryption, we can obtain the intermediate ciphertext (13) (15)
Then, the intermediate ciphertext is sampled by using PCS. The first column of the final ciphertext can be expressed by
y1 = 254Φ ：,1 + 255Φ ：,2 + 255Φ ：,4 . (16)
According to (16), we can see that the first column of final ciphertext is still a combination of columns. Since the adversary does not know which columns are involved in computing, he cannot figure out the secret measurement matrix. In conclusion, since the linearity of the CS encoding process is destroyed by embedding NPT operation, our proposed method can achieve effective privacy protection against CPA.
First, the encryption performance is evaluated by subjective evaluation. Lena image (512×512) is used in the experiment. The bit size for each CS measurement is 8. The cipher image and the final compressed ciphertext are presented in Figure 2. It can be seen that the cipher image leaks some outline information of the original image. The main reason is that NPT operation is a lightweight encryption method, which cannot protect image privacy perfectly when it is used separately. To enhance the security performance, CS is used to re-encrypt the intermediate cipher image. After CSbased encryption, the final cipher image masks the content of the image perfectly, which means that our method can provide visual privacy protection for 2D images. Furthermore, the size of the compressed ciphertext is far less than that of the plaintext, which means the image is encrypted and compressed by using the proposed method at the same time.
Now, the security performance is evaluated by key space analysis. According to [18], the key space for a good encryption scheme is suggested to be larger than 2100 to achieve effective privacy protection against brute-force attack. In the proposed method, the separate keys are K1 and K2 . Based on the floating-point standard [19], the precision of double-precision number is about 10-15, so the key space of our method is which is larger enough to resist the brute-force searching. 4.2.
Compression performance 40 35 30 ) dBN (R25 S P20 15 100 0.1 0.2 Compres0s.3ionratio 0.4
(a) 35 30 ) 25 dBNR ( S P20 15 0.6 100 0.1 0.2 Compressionratio 0.4 0.3 (b)
PCS-CME PCS-RP Ourmethod 0.5
0.6 PCS-CME PCS-RP Ourmethod 0.5
0.6 PCS-CME PCS-RP Ourmethod 0.5 PCS-CME PCS-RP Ourmethod 0.5 40 35 30 ) dBN (R25 S P20 15 30 25 ) 20 dBRN ( S P15 10 0.6 50 0.1 0.2 Compressionratio 0.4
0.3 (c) (d)
In this section, we evaluate the compression performance of the proposed method and compare it with two schemes, including PCS with counter mode encryption (PCS-CME) proposed in [5] and PCS with random permutation (PCS-RP) proposed in [13]. Four gray images (512×512) is used in this test. Each CS measurement is quantized into 8 bits. For all schemes, we do not add entropy coder after the quantization with the purpose of simplifying the encoder. For PCS-RP scheme, orthogonal matching pursuit (OMP) [20] algorithm is applied to reconstruct the image. For PCS-CME scheme, we use smoothed projected Landweber (SPL) [21] algorithm to reconstruct the original image. The PSNR (in dB) versus compression ratio for different methods is showed in Figure 3. It can be seen from the figure that our method can obtain remarkable gain in comparison with the other two schemes. For instance, when compression ratio equals to 0.1, for Lena image, the gain of our method is more than 12 dB. The reconstructed images are displayed in Figure 4. It can be seen that our method has better visual quality than the other two schemes.
In this paper, a novel CS-based cryptosystem by using NPT operation is proposed, which embeds a NPT operation in the sampling process to achieve effective privacy protection against CPA. Compared with previous CS-based cryptosystems, the proposed cryptosystem has two advantages: 1) It achieves effective privacy protection against CPA; 2) It has better compression performance.
This work was supported by the Project Supported by Graduate Student Research and Innovation Foundation of Chongqing, China (Grant No. CYB22063). Zhixiang Zheng (sime0821@163.com) is the corresponding author of this paper.
[8] V. Cambareri, M. Mangia, F. Pareschi, R. Rovatti, and G. Setti, “Lowcomplexity multiclass encryption by compressed sensing,” IEEE Trans. on Signal Processing, vol. 63, no. 9, pp. 21832195, 2015. [9] T. Bianchi, V. Bioglio, and E. Magli, “Analysis of one-time random projections for privacy preserving compressed sensing,” IEEE Trans. On Information Forensics and Security, vol. 11, no. 2, pp. 313-327, 2016. [10] L. Y. Zhang, K. W. Wong, Y. Zhang, et al., Bi-level protected compressive sampling, IEEE
Trans. on Multimedia, vol. 18, no. 9, pp. 1720-1732 , 2016. [11] V. Cambareri, M. Mangia, F. Pareschi, et al., “On known-plaintext attacks to a compressed sensing-based encryption: Aquantitative analysis,” IEEE Trans. on Inf. Forensics Security, vol. 10, no. 10, pp. 2182-2195, 2015. [12] R. Fay, “Introducing the counter mode of operation to compressed sensing based encryption,”
Information Processing Letters, vol. 116, no. 4, pp. 279-283, 2016. [13] Y. S. Zhang, J. Zhou, F. Chen, “Embedding cryptographic features in compressive sensing,”
Neurocomputing, vol. 205, pp. 472-480, 2016. [14] B. Zhang, D. Xiao, M. D. Wang, and J. Liang, “Privacy-preserving compressed sensing for image simultaneous compression-encryption ap-plications,” in Proc. of 2021 IEEE Data Compression Conference, 2021, pp. 283-292. [15] B. Zhang, D. Xiao, and Y. Xiang, “Robust coding of encrypted images via 2D compressed sensing,” IEEE Trans. on Multimedia, vol. 23, pp. 2656-2671, 2021. [16] L.S. Endur, I. W. Selesnick, “Bivariate shrinkage functions for wavelet-based denoising exploiting interscale dependency,” IEEE Trans. on Signal Processing, vol. 50, no. 11, pp. 27442756, 2002. [17] J. Yang, Y. Wang, W. Xu ,et al., “Image coding using dual-tree discrete wavelet transform,”
IEEE Trans. on Image Processing, vol. 17, no. 9, pp. 1555-1569, 2008. [18] G. Alvarez, and S. Li, “Some basic cryptographic requirements for chaos-based cryptosystems,”
International Journal of Bifurcation and Chaos, vol. 16, no. 8, pp. 2129-2151, 2006. [19] IEEE Standard for Binary Floating-Point Arithmetic, IEEE Standard 754, 1985. [20] S. Mun and J. E. Fowler, “Block compressed sensing of images using directional transforms,” in
Proc. of IEEE Conference on Image Processing (ICIP), pp. 3021-3024, 2009. [21] J. Tropp, and A. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit,” IEEE Trans. on Information Theory, vol. 53, no. 12, pp. 4655-4666, 2007.