Perfect secrecy via compressed sensing

2013 Iran Workshop on Communication and Information Theory (IWCIT) 1

Perfect Secrecy via Compressed Sensing Mahmoud Ramezani Mayiami, Babak Seyfe, Senior Member, IEEE, Hamid G. Bafghi, Department of Electrical Engineering, Shahed University, Tehran, Iran. Emails: {ma.ramezani, seyfe, ghanizade}@shahed.ac.ir

1

Abstract—In this paper we consider the compressive sensing based encryption and proposed the conditions in which the perfect secrecy is achievable. We prove that when the measurement matrix holds the Restricted Isometry Property (RIP) and the number of measurements is more than two times of the sparsity level, i.e., M ≥ 2k, the Shannon perfect secrecy condition is achievable either i) the cardinality of the message set tends to infinity or ii) the message set does not include the zero message. As an implicit assumption, we suppose that the eavesdropper has not access to the secret key during the transmission. Index Terms—compressed sensing, perfect secrecy, compressed sensing-based encryption.

I. I NTRODUCTION The framework of Compressed Sensing (CS) or Compressive Sampling, proposed by Candes et al. [1] and Donoho [2], has recently become a widely investigated research area and has been served in some applications such as image processing [3], radar systems [4], signal detection [5] and other applications [6]. Secure communication from an information theoretic perspective first studied by Shannon in his famous paper [7] is an interesting problem considered in various approaches. Some researchers approach to the secure communication problem through encryption methods. Some of the others treat this problem with the information theoretic measurements. They try to minimize the leakage information to the unintended receiver, i.e., the eavesdropper by using the coding scheme named Random Coding [8]. Information-theoretic secrecy intends to ensure that an eavesdropper who listens to the transmitted message, can only collect an arbitrary small number of information bits about this message. The perfect secrecy condition in which the listening to the channel cannot increase the probability of decryption of the sent message for 1 This

work was supported by Iran National Science Foundation (INSF), under Grant number 91/s/26278.

978-1-4673-5023-5/13/$31.00 © 2013 IEEE

the eavesdropper was first proposed in Shannon’s landmark paper [7]. The secure communication using the CS methods is a new interesting subject attracted the attentions, recently [9], [10]. The aim of this approach is to compose the encryption and compression of the message by using a measurement matrix. In other words, the measurement matrix generated for compressive sampling purpose is used as a key to encrypt the sparse messages. Rachlin and Baron in [9] argued whether the measurements of compressed sensing can prepare an approach to obtain perfect secrecy simultaneously. They investigated the achievability of the perfect secrecy by using the measurement matrix of compressive sampling as a key and proved that compressed sensing-based encryption cannot generally achieve perfect secrecy. In this paper, we consider the encryption system in which the encoder with a sparse message uses the compressed sensing measurement matrix to encrypt and compress its message. The unintended receiver who accesses to the ciphertext, without any knowledge about the key generation, tries to decode the ciphertext (see Figure 1). Here, we prove the practical conditions in which the Shannon’s perfect secrecy condition is established. The organization of this paper is given in the following. In section II, we review the literature of the compressed sensing and the perfect secrecy. The main results of the paper as perfect secrecy through compressed sensing are proposed in section III. We will conclude this paper in section IV.

II. T HE BACKGROUNDS Since the contribution of this paper is based on Compressed Sensing and Perfect Secrecy, some preliminaries about these topics are presented in this section.

Basis Pursuit (BP) [14] is one of the approaches to solve (3). Definition 1 [13]: A satisfies the RIP of order k when for all k-sparse vector α with appropriately chosen constant 0 < εk < 1, ∥Aα∥2 satisfies constraints given by Fig. 1. The compressed sensing-based encryption system with an external eavesdropper.

(1 − εk )∥α∥22 ≤ ∥Aα∥22 ≤ (1 + εk )∥α∥22 .

However an important question is: what measurement matrices, with respect to the specific dictionary Ψ, leads A to satisfy RIP? Although there is a broad set of random matrices satisfying RIP, the most important one is investigated in [15]. The authors in [15] proved that if the elements of Φ are selected from independent and identically distributed (i.i.d) random variables from a Gaussian probability density 1 , Φ will be function (pdf) with mean zero and variance M incoherent with any basis Ψ. Thus A satisfies RIP with overwhelming probability when M ≥ ck log( Nk ), for some constants c [1], [2], and [16].

A. Compressed Sensing By CS approach, we can sense the signal in compressed form. In other words, the important information of the signal is sensed and the remainder that could not be useful is ignored [2]. Suppose x is a N × 1 signal vector that we want to find its elements. It is shown that x can be interpreted as x = Ψα, where Ψ is a N × N dictionary that its columns are orthonormal and span x domain and α is the coefficient vector of x in the basis Ψ. The vector α is said to be ksparse whenever k non-zero elements exist in α for k ≪ N . Here, we count non-zero elements with l0 -norm notation i.e., ∥α∥0 = k, where √∑ ∥α∥p indicates lp -norm which is N defined as ∥α∥p = p i=1 | αi |p and αi for 1 < i < N are the elements of the vector α. In the compressed sensing, instead of sensing the signal directly, we observe M measurements of signal vector (k < M < N ) and these measurements are shown by y as following y = Φx = ΦΨα = Aα

B. Perfect Secrecy Cryptographic encryption which is the base of the conventional techniques for achieving confidentiality is a basic field in communication systems [17], [18]. In an encryption system, the sender uses a key to encrypt the source information, i.e., plaintext and converts it into the ciphertext. The legitimate receiver decrypts the ciphertext to the original message using the corresponding key. In these systems, it is assumed that the unintended receiver, i.e., eavesdropper, has access to the ciphertext without any information about the key. As an application, the eavesdropper has limited time or limited computational resources to test all possible keys (see [19] and the references therein). Encryption includes two principle types of algorithm: secret-key encryption algorithm in which the transmitter and the receiver share a common secret key, and public-key encryption algorithm in which the transmitter and the receiver have different keys for encryption and decryption, respectively [19]. In this case, the plaintext would be encrypted by a public key which is known for all receivers including eavesdroppers. The intended receiver, firstly, extracts the private key corresponding to the public key and decrypts the ciphertext with this key. So, in practice, the eavesdropper

(1)

where, Φ is a M × N measurement matrix and A is holographic dictionary [2]. Since M < N , (1) is underdetermined system of linear equations having many solutions. If we choose a constraint on sparsity of α, we can be assure of finding the solution via the general following method. min ∥α∥ α

subject to

y = Aα.

(2)

There are some approaches for implementing (2) such as Orthogonal Matching Pursuit (OMP) algorithm [11]- [12]. Since OMP is not a convex relaxed approach, it is common to use other methods which is implemented by linear programming. For example, if A has Restricted Isometery Property (RIP), which will be defined latter, we can recover α as [13] min ∥α∥1 α

subject to

y = Aα.

(4)

(3) 2

sparsity level of the messages, i.e., M ≥ 2k, and the number of source messages goes to infinity, i.e., T1 → ∞. Proof: To compute the mutual information between y = Φx and x, we have

cannot obtain any information about the private key and the plaintext. Perfect secrecy introduced by Shannon in his fundamental paper [7] is based on the statistical properties of a system, and provides protection even in the face of a computationally unbounded adversary. In the Shannon’s model, a source message X is encrypted to a ciphertext Y by a key Φ that is shared between the transmitter and the intended receiver. An eavesdropper may intercept the ciphertext Y. The system is considered to be perfectly secure if a posteriori probabilities of X for all Y be equal to a priori probabilities independent of the values of Y, i.e., PX|Y = PX . Alternatively, this condition can be given by I(X; Y) = 0, which means that the eavesdropper cannot extract any information about the plaintext from the received ciphertext [7].

I(X; Y) = H(Y) − H(Y|X) ∑ = H(Y) − x∈X H(Y|X = x)PX (X = x) = H(Y) − H(Y|X = 0)PX (X = 0) ∑ − x∈X ,x̸=0 H(Y|X = x)PX (X = x) ∑ =(a) H(Y) − x∈X ,x̸=0 H(Y|X = x)PX (X = x)

(5)

Note M ≥ 2k guaranties that there is one projection y for each x [22]. Then, (a) is because of the fact that for any measurement matrix Φ, y = 0 iff x = 0 then, H(Y|X = 0) = 0. For uniformly distributed variable X we have PX (X = x) = T11 . Furthermore, whereas the message X is uniformly distributed over X , and Φ is a linear projection, then Y has uniform distribution over alphabet Y with cardinality T1 . So, for the right hand side of (5) we have 1 ∑ H(Y|X = x). (6) I(X; Y) = log T1 − T1

III. S ECRECY VIA C OMPRESSED S ENSING Suppose X and Y are discrete random variables with alphabet X and Y which contain source messages and encoded messages, respectively and each of the source messages x ∈ X is sparse in the basis Ψ. For simplicity and without loss of generality, suppose that Ψ is an identity matrix [9]. Also, we assume that the channel is not noisy and the transmitted signal is not interfered. The compressed sensingbased encryption expresses that we can transmit cryptogram y = Φx instead of x and the legitimate receiver can decrypt it by knowing Φ. In this paper we assume the secret-key, i.e., the measurement matrix Φ, shared between the sender and the legitimate receiver while this key is not known at the eavesdropper. This assumption is common in the literature of information theoretic secrecy [19]. Each random measurement matrix Φ is generated with a seed which is exchanged through a secure way between the sender and the legitimate receiver [20], [21]. In the following, we show that the CS based-encryption satisfies Shannon’s definition of perfect secrecy if some constraints are held. Theorem 1: Let X uniformly distributed over X with cardinality T1 , i.e., |X | = T1 . The encoder uses the CS measurement matrix Φ which satisfies RIP, to map X to Y. This CS measurement matrix is known at the encoder and the legitimate decoder but not at the eavesdropper. The CS based encryption achieves perfect secrecy if the number of measurements M is equal or greater than two times of the

x∈X ,x̸=0

Note that if the legitimate receiver accesses to the CS measurement matrix Φ, it can decode the received sequence y by using the conventional approaches explained in section I, like OMP. Since Φ satisfies the RIP and M ≥ 2k, the encrypted transmitted message x has a unique projection [22]. Therefore, the legitimate receiver who has the CS measurement Φ can decrypt the ciphertext. Hence, in (6), H(Y|X = x) = 0 and the reliability for this coding scheme is achievable at the legitimate receiver. Because the eavesdropper has no access to the CS measurement matrix Φ, it tries to decode the received sequence y to extract x without the knowledge of CS measurement matrix Φ. Because of the fact that we use a unique coding scheme to encode the message x as stated in the above, H(Y|X = x) = H(Y) and we can rewrite (6) as I(X; Y) = logT1 −

T1 − 1 log(T1 − 1). T1

(7)

Note that the cardinality of Y − {0} is equal to T1 − 1. Now, according to (7), when the number of source messages goes to infinity, i.e., T1 → ∞, we have I(X; Y) = 0 and it means that the coding scheme with CS measurement matrix 3

does not increase a priori probability of decoding of the X at the eavesdropper, i.e., PX|Y = PX . Hence, the perfect secrecy is achievable at the eavesdropper.

log T2 and for (8) we can write

Corollary 1: This theorem explains that the coding scheme based on CS measurement matrix can satisfy the Shannon’s perfect secrecy condition if the eavesdropper has no access to the measurement matrix Φ and the number of source messages goes to infinity. This coding scheme can be used in some applications, e.g., spread spectrum communications, mobile communications, and wireless sensors networks.

and therefore the perfect secrecy is achievable. Corollary 2: This theorem remarks that there exists a finite code based on the CS approach, which achieves perfect secrecy. Remark 1: Here, we compare our results in these theorems with the proposed results in [9] which expressed generally that the CS based encryption can not satisfy the Shannon’s perfect secrecy condition. The authors in [9] mentioned that x = 0 leads to y = 0 and then PY|X (Y = 0|X = 0) = 1. Therefore for arbitrary PY (Y = 0) < 1 we have PY|X (Y = 0|X = 0) ̸= PY (Y = 0) or equivalently I(X; Y) > 0. This means that the perfect secrecy is not achievable. Our first theorem mentions that the perfect secrecy is achievable if the eavesdropper has no access to the measurement matrix Φ, and the number of the message tends to infinity. Also, in the second theorem we have shown that when the eavesdropper has no access to the measurement matrix Φ, and the null message is eliminated from the alphabet X , the perfect secrecy is achievable. Therefore, our results has no conflict with the one in [9, Theorem 1].

I(X; Y) = log T2 −

The next theorem mentions that the CS based coding scheme can meet the Shannon’s perfect secrecy condition with another constraint too. In this case, it is necessary to remove the null message from the alphabet X , then it achieves the Shannon’s perfect secrecy condition for the finite input alphabet of X. Theorem 2: Let X uniformly distributed over alphabet X with cardinality equal to T2 and there is not any null message in the set of source messages, i.e., ∀x ∈ X , x ̸= 0. If the encoder uses the CS measurement matrix Φ which satisfies RIP, to map X to Y and this CS measurement matrix is known at the encoder and the legitimate decoder but not at the eavesdropper. Then, perfect secrecy via compressed sensing is achievable. Proof: Since Φ satisfies RIP and M ≥ 2k, every message X has a unique projection [22]. Hence, Y has a uniform distribution over Y. On the other hand, because there is not any null message in the set of source messages, having unique projection guaranties that there is not any null message in the set of Y, i.e., ∀y ∈ Y, y ̸= 0. Therefore, PY (Y = 0) = 0 and we have

(9)

IV. C ONCLUSIONS In this paper, the perfect secrecy using compressed sensing measurements was studied. It is shown that for the sparse message and the CS measurement matrix in which RIP condition is held, and the number of measurements M is equal or greater than two times of the sparsity level of the messages, i.e., M ≥ 2k, the CS based encryption achieves the Shannon’s perfect secrecy condition either i) the cardinality of the message set tends to infinity, or ii) there is no null message in the set of source messages.

I(X; Y) = H(X) − H(X|Y) ∑ = H(X) − y∈Y H(X|Y = y)PY (Y = y) = H(X) − H(X|Y = 0)PY (Y = 0) ∑ − y∈Y,Y̸=0 H(X|Y = y)PY (Y = y) ∑ = H(X) − y∈Y,y̸=0 H(X|Y = x)PY (Y = y) ∑ = log T2 − T12 y∈Y,y̸=0 H(X|Y = y)

1 .T2 log T2 = 0 T2

R EFERENCES [1] E. J. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inform. Theory, vol. 52, no. 2, pp. 489– 509, Feb. 2006. [2] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, vol. 52, no. 4, pp. 1289– 1306, Apr. 2006.

(8)

Then, for the case in which the eavesdropper has no access to the CS measurement matrix Φ, H(X|Y = y) = H(X) = 4

sensing,” in Forty-Fifth Annual Allerton Conference, Allerton House, UIUC, IL, USA, Sept. 2007.

[3] J. Romberg, “Imaging via compressive sampling [introduction to compressive sampling and recovery via convex programming],” IEEE Signal Process. Mag., vol. 25, no. 2, pp. 14 – 20, Mar. 2008. [4] R. Baraniuk and P. Steeghs, “Compressive radar imaging,” IEEE Radar Conference, Waltham, MA,, April 2007. [5] Marco F. Duarte, Mark A. Davenport, Michael B. Wakin, and Richard G. Baraniuk, “sparse signal detection from incoherent projections,” in in Proc. of International Conference on Acoustics, Speech and Signal Processing ( ICASSP), 2006, vol. 3, pp. 305– 308. [6] A. M. Bruckstein, D. L. Donoho, and M. Elad, “From sparse solutions of systems of equations to sparse modeling of signals and images,” SIAM Rev., vol. 51, no. 1, pp. 34– 81, Feb. 2009. [7] C.E. Shannon, “Communication theory of secrecy systems,” The Bell System Technical Journal, vol. 28, pp. 656–715, October 1949. [8] A. Wyner, “The wire-tap channel,” Bell. Syst. Tech. J., vol. 54, no. 8, pp. 1355–1387, Jan. 1975. [9] Y. Rachlin and D. Baron, “The secrecy of compressed sensing measurements,” in Communication, Control, and Computing, 2008 46th Annual Allerton Conference on, sept. 2008, pp. 813 –817. [10] A. Orsdemir, H.O. Altun, G. Sharma, and M.F. Bocko, “On the security and robustness of encryption via compressed sensing,” in Military Communications Conference, 2008. MILCOM 2008. IEEE, nov. 2008, pp. 1 –7. [11] Y.C. Pati, R. Rezaiifar, and P.S. Krishnaprasad, “Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition,” in Signals, Systems and Computers, 1993. 1993 Conference Record of The Twenty-Seventh Asilomar Conference on, nov 1993, pp. 40 –44 vol.1. [12] S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification,” International Journal of Control, vol. 50, no. 5, pp. 1873–96, 1989. [13] E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215, 2005. [14] S.S. Chen, D.L. Donoho, and M.A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 33–61, 1998. [15] E. Candes and T. Tao, “Near optimal signal recovery from random projections: Universal encoding strategies,” IEEE Trans. Inf. Theory, vol. 52, no. 12, pp. 5406–5425, 2006. [16] R.G. Baraniuk, M. Davenport, R. DeVore, and M.B. Wakin, “A simple proof of the restricted isometry principle for random matrices,” Constructive Approximation, vol. 28, no. 3, pp. 253– 263, 2008. [17] Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996. [18] William Stallings, Cryptography and Network Security: Principles and Practice, Pearson Education, 2002. [19] Yingbin Liang, H. Vincent poor, and Shlomo Shamai, Information Theoretic Security, Now publishers Inc., 2008. [20] W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Inform. Theory, vol. IT-22, no. 6, pp. 644–654, 1976. [21] U. Maurer and S. Wolf, “Information-theoretic key agreement: From weak to strong secrecy for free,” in Advances in Cryptology- EUROCRYPT, Lecture Notes in Computer Science, 2000. [22] Y. Weiss, H. S. Chang, and W. T. Freeman, “Learning compressed

5