Image adaptive selective encryption of vector quantization index compression

IMAGE ADAPTIVE SELECTIVE ENCRYPTION OF VECTOR QUANTIZATION INDEX COMPRESSION 1

Yassin M. Y. Hasan1,2, 2

Mohammed F. A. Ahmed1,3, and Tarik K. Abdelhamid1

EE Dept., Assiut University, ARE CSI Dept., Taibah University, KSA 3ECE Dept., University of Alberta, Canada 1 [email protected], [email protected] ABSTRACT

The foremost issues with most of the existing selective encryption (SE) schemes of images are vulnerability to cryptographic and application specific attacks, reduction in the compression performance, insubstantial computational savings relative to full encryption, and lack of bit stream compliance. This paper is the first one that proposes effective schemes for joint vector quantization (VQ) based image compression and SE. We introduce an image adaptive VQ index compression algorithm suitable for SE, effectively combining remapping of indices, entropy, predictive, differential, and search order coding. We then present SE through codebook pseudorandom shuffling and block ciphering of the VQ index image bit-planes, index usage map, prediction information tables and full indices. Experimentally, the results demonstrate the improved performance and effectiveness of the proposed schemes.

Index Terms— Selective encryption, vector quantization. 1. INTRODUCTION Secure storage and transmission of the various forms of multimedia data have recently become more crucial [1]. Encryption can protect such data. But encryption of the typically huge raw multimedia data is computationally intensive [2],[3]. Such uncompressed data is also very redundant, hence an attacker can take advantage of the redundancy in a source multimedia signal (plaintext) to cryptanalyze its encrypted form (ciphertext). It is also clear that compression after encryption with inherently entropy-raising pseudorandomness gives inefficient compression. In practice, even after lossless/lossy compression [4], multimedia data files may still be too massive to be fully encrypted (decrypted) using inexpensive resources with low power consumption, particularly for real-time processing and mobile applications. Selective, also called partial, lightweight and soft, encryption (SE) schemes [5]-[7] cipher small parts of the compressed/uncompressed source signal representation, mostly corresponding to the most significant or critical information, to make the information recovered from the rest of the bit stream useless for the intended application. Therefore, SE offers significant savings in computations, power consumption, cost, and/or time. In addition, from the security point of view, since cryptanalysis generally benefits from having more available plaintext-ciphertext samples for the same key, SE is useful in reducing such information. It also introduces new functionalities [6]-[8]. As overviewed in Section 2, many SE techniques of compressed/uncompressed images/video have been presented [9] This paper is the first one that addresses joint vector quantization (VQ)-based image coding and SE.

2. EXISTING SE SCHEMES OF IMAGES One straightforward SE scheme is to cipher some bits of the raw image representation. In [9], it is experimentally shown that fully encrypting 2 to 4 image most significant bit-planes may result in

978-1-4244-5654-3/09/$26.00 ©2009 IEEE

1277

visually acceptable results and high confidentiality. In [10], SE based on decoding processes de-synchronization is achieved through ciphering the initial model of an adaptive entropy coder. However, the scheme is insecure since it is vulnerable to chosenplaintext attacks [11]. In [12], an adaptive arithmetic coding-based technique is presented that obscures the initial model/parameters and secretly alters the interval per symbol. But it nearly doubles the overall computations and increases the data size. In [13], an image ciphering technique based on hierarchical scan patterns followed by additive noise substitution is introduced. But, brute force attacks can break its security since the number of scan patterns is not large ( ~236 for 512u512 images). Also, one chosen plaintext can resolve the substitution and decomposition. In [14], SE is applied to lossless quadtree (QT) compressed images. But the technique is vulnerable to histogram and known/chosen-plaintext attacks. In [15], only the QT structure is encrypted. In [16], a more secure technique is presented that ciphers ~13%-27% of the compressed bit stream. SE of images/video in transform domains such as the DCT domain has also been studied [17-21]. Encryption of the DC coefficients of the block-wise DCT reduces the PSNR of the image to ~9dB and mostly results in a perceptually unintelligible image. But replacing all the encrypted DC coefficients with a constant level, makes all the edges be clear enough to resolve the image content. In [17], a pseudorandom permutation list replaces the zigzag order in mapping the 8u8 DCT block to a 1u64 vector, with and without mixing the DC and AC coefficients together. The employed shuffling degrades the compressibility. In [18], a video encryption algorithm uses a secret key to pseudorandomly change the sign bits of the DCT coefficients of MPEG video. In [19], three improved versions of an earlier work are introduced that ciphers the data associated with every nth I-frame macroblock, the headers of all predicted macroblocks or both of them. In [20], a scheme for encrypting the motion vectors in multimedia streaming is presented. In [21], the introduced MPEG video security scheme including DC encryption and "Event Shuffle" without bit overhead. Also, wavelets based SE schemes have been presented [16],[22],[23]. In [18], SE (~2%) of the bit stream of embedded Set Partitioning in Hierarchical Trees (SPIHT) [4] coded images, is presented that ciphers only the significance information of pixels or sets in the two highest pyramid levels and the parameter used as the initial threshold. In [22], the encoder chooses different decomposition schemes with respect to the wavelet packet subband structure for each image and the tree is encrypted. In [23], in order to preserve the compressibility of the JPEG 2000 coder, SE is performed in its entropy-coding stage, ciphering the selected DWT code-blocks. To further speed up the SE processes, other fast transform and compressed domain shuffling-based SE techniques have been introduced [24],[25]. However, in [26], effective schemes for general cryptanalysis of shuffling-only multimedia encryption algorithms have been proposed. In [27], a computationally efficient encryption scheme is presented based on pseudorandom bit stream partitioning and rotations. But it does not provide sufficient change diffusion characteristics to be secure enough.

ICIP 2009

3. VECTOR QUANTIZATION Conventional VQ [28] is among the extensively studied nonstandard asymmetric lossy image compression techniques with slow and computationally intensive encoding but fast simple table lookup based decoding processes. In general, the M-dimensional, Ncodeword vector quantizer is defined as a mapping process Q(.) from an M-dimensional Euclidean space RM into a certain finite ordered set, called codebook, C={C1, C2, …, CN} of N Mdimensional codewords, Ci = (ci1, ci2, …., ciM) based on a specific distance measure. Hence, VQ is an indexing procedure in which each input vector is mapped into an index. The codebook can be designed using forms of the LBG or clustering algorithms [28],[29]. Recent publications has applied VQ to full-image encryption [33]-[35]. In [33], a virtual image cryptosystem based on VQ uses a ciphered common codebook. In [34], relying on the basic ideas of secret sharing and the virtual image cryptosystem, a virtual image sharing method (VISM) is presented that divides a secret image into a large number of different shadows. However, the encryption burden slows down the already slow VQ encoder [33],[34]. Also, in [35], it is shown that if many images are ciphered with the same ciphered common codebook, the cryptosystem becomes vulnerable to ciphertext-only and chosen plaintext attacks. So, new effective VQ-based encryption/SE schemes are needed.

representing the subset of the codewords used, is sent to the decoder in conjunction with the compressed codes of the new index image, after remapping, with short re-mapped indices for the new codebook that has fewer renumbered codewords. Instead of sending an N-bit IUM vector for each sub-image, we send fewer overhead bits corresponding only to the minimum used index Imin, the maximum used index Imax, and the Imax-Imin+1-bit IUM between them. If we choose to use remapping, the sizes of the sub-images and their IUM's are appended to the header.

4.2. Proposed SE Schemes of VQ Image Compression We present various VQ-based encryption schemes, starting with simple ones and gradually giving more effective ones suitable for the proposed compression algorithm. A simple encryption algorithm is to pseudorandomly shuffle the indices of the codebook before performing VQ. Alternatively, similar degree of security is gained if the IUM is ciphered. In Fig. 1, an airplanes image and its encrypted version using codebook pseudorandom shuffling are shown. This scheme reduces the adjacent indices correlation and so reduces their compressibility. It is also not secure since it does not change the indices histogram and does not provide change diffusion. So known/chosen plain-image attacks can break its security despite of its possibility of providing visually acceptable cipher-image.

4. PROPOSED VQ SE SCHEME 4.1 Proposed VQ-based Image Compression: Since, the residual redundancy after VQ leads to repeated patterns of indices in index images, the main idea of the proposed lossless VQ index compression algorithm is to exploit the correlation between the VQ indices through effectively combining look-up table based, entropy, predictive-differential [28],[30],[31], and search order coding (SOC) [32] as follows: 1- Raster-scan the index image and record the pairs repetitions of the present index with its upper (U) and left (L) neighboring indices. Then, construct two Nu1-index vectors called U and L tables, together called NEXT table that sequentially records, for each index, the most probable neighboring indices (with the highest repetition) in the respective directions. 2- Check the present index if it matches the corresponding value in the U or L tables and code it as A or B codes, respectively. Go to 5. 3- If no matching is found, run a simple SOC that searches (in a predefined path) within its 4 direct previously encoded indices for a matched index to the current index. If a match is found, send the search order headed by a code S and go to Step 5. 4- Compute the signed difference between the present index and its corresponding values in the U and L tables. If the absolute value of a difference is less than a specified threshold, binary-encode it headed by a code AD or BD, respectively, otherwise, fully binary-encode this current index headed by a code FI. 5- If the end of the index image is not reached, advance to the next index in the scanning order and Go to Step 2. 6- Find a Huffman table for the prefixes A, B, AD, BD, S, and FI based on their histogram, encode and properly insert them in the bit stream.. Also the fully encoded indices and search orders can optionally be Huffman coded and inserted in the bit stream. 7- Append a header to the bit stream including the following: image size, the NEXT table (i.e., the U/L prediction tables), and the lengths of all the symbols' Huffman tables entries. The adaptability of an image coder to match the image characteristics typically results in better performance. So, we construct the NEXT table per image and sent it within the bit stream. Also, a large universal codebook is generated once and used for coding. In this case, only a binary indices-usage-map (IUM),

1278

Fig.1 The original airplanes image and its encrypted version using codebook pseudorandom shuffling. Another straightforward SE scheme is to cipher some most significant bit-planes of the index image using block ciphers with the cipher-block-chaining mode [3]. If partial reconstruction is not required, it gives visually unsatisfying results leaking information about the image content as shown in Fig. 2. Moreover, bit-plane encryptions are vulnerable to replacement attacks, where the encrypted bit-plane may be replaced by an estimated value. Although applying this attack to the indices followed by table lookup image reconstruction is less efficient than the case of unquantized (original) images but it still works. Because the index image resembles the original image, the index image itself after a replacement attack gives much information about the original image. In addition, the least percentage of SE is only 12.5% (i.e., a full bit-plane) of the index image which is not small enough. Also, this scheme badly affects the compressibility of the index image.

Fig.2 SE with encrypting the most significant bitplane only of the index image. Repeated adjacencies lossless index compression algorithms without SOC and Section 4.1 can be used for SE of images. Decoding the compressed bit stream to retrieve the VQ image indices essentially requires the NEXT table. Since the rest of the indices decoding processes progressively depend on the previously

decoded indices, we propose encrypting the NEXT table to disguises many parts of the image in the reconstruction process. However the full indices do not depend on the NEXT table and as a consequence they can exactly be recovered independent of the ability of recovering their preceding (relatively coded) indices as shown in Fig. 3 (without SOC). For small codebook sizes, the percentage of full indices is low, while the it increases with increasing the codebook size. This is because the smaller codebook sizes result in more correlated indices, so it is more probable to find a matched index in the nearby area. High detailed images (like the baboon) have less percentage than low detailed images.

the airplanes image of Fig. 1 encoded using the proposed algorithm with SOC (when ciphering both the NEXT table and all full indices) and the correctly recovered areas without deciphering with the correct private key. It is clear that such SE flexibly allows quality scalable partial image reconstruction through controlling the percentages of the prediction tables and full indices to be encrypted.

Fig.6 SE of the airplanes image of Fig. 1 encoded using the proposed algorithm with SOC when ciphering both the NEXT table and all full indices (left) and the correctly recovered areas

(right, with darkened background). Fig.3 SE of the airplanes image of Fig. 1 using Next table encryption (left) and the correctly recovered areas corresponding to the fully encoded indices. Since the indices coded using the NEXT table recursively depend on previously coded full indices somehow, ciphering the full indices only is more effective than ciphering the NEXT table only but the percentage of full indices load relative to the compressed bit stream is ~5 more than that of the NEXT table. So, to solve the full indices recovery problem without affecting the bit rate and computational savings, we propose the SE scheme of Fig. 4 that ciphers some of (or all) the NEXT table and full indices. Without the SOC procedure, Fig.5 illustrates the results of SE of the airplanes image of Fig. 1 (ciphering both the NEXT table and all the full indices) and the correctly recovered areas without deciphering with the correct key. It is clear that the correctly recovered areas are reduced significantly. The locations/sizes of these parts are key dependent.

Fig.4 General block diagram of the proposed SE scheme.

Fig.5 SE of the airplanes image of Fig. 1 using both NEXT table and all full indices encryption (left) and the correctly recovered areas (right, with darkened background). As given in the index compression algorithms, the percentage of the full indices can be reduced by the SOC step, since it codes the indices depending on their (mostly ciphered) neighboring indices. So we apply the proposed joint VQ-based compression and encryption scheme as follows: The scheme first applies both the NEXT table and SOC-based index encoder, and then encrypts the NEXT table and the full indices. Fig. 6 gives the results of SE of

1279

The following should be noticed concerning reducing the percentage of full indices: (1) Since the full indices are not equally probable, variable length codes (VLC) can be assigned to them to reduce the total bit rate followed by encryption. (2) Using IUM and remapping of indices on sub-image basis further reduces the percentage of the encountered full indices. (3) The merits of reducing the percentage of the full indices are: Less percentage of the bit stream to be ciphered, less original-to-SE images correlation, and more uniform SE image histogram.

5. EXPERIMENTAL RESULTS AND DISCUSSION The performance of the proposed VQ-based joint compressionencryption algorithm is evaluated from the SE processing load and reliability points of view. We implemented the proposed algorithms through constructing a Matlab-based toolbox. We used the 256-gray level 512u512-pixel images of the SIPI-USC miscellaneous imageset [36], 20% to generate a 256-codeword codebook used in the simulation and other 15% for testing, in addition to non-standard images. Each image is divided into 4u4-pixel blocks (represented as 1u16 vectors). The splitting method is used to obtain the initial codebook, and the LBG is used to enhance it [29]. The full search algorithm is used to find the best matched codeword with the minimum Euclidean distance. The repeated adjacencies scheme uses index difference threshold of 16, the SOC algorithm uses 2 bits to code the search order and 4 bits are used to code the differences. There is no one standard measure for the encryption quality despite of some indicative measures [4]. Acceptable encryption schemes should not preserve the original image histogram and be as much uniform as possible. The histograms modifications due to encryption in the index domain and in the pixel domain are shown in Fig.7. The histograms before SE are bell-shaped and after SE are almost uniform. The similarity between the encrypted image and the original one can be evaluated using the correlation factor. The encryption computational burden can be assessed by the percentage of the ciphered portion of the overall bit stream. Table 1 summarizes the results for 4 randomly chosen test images giving the bit-rate (BR) in bit/pixel with/without the SOC procedure, the percentage of full indices (FI%) and the percentage of encrypted bit stream (E%) representing the computational savings gained with SE compared to full encryption of the bit stream, as well as the correlation factor (CF) between the plain and ciphered images as indication of the pseudorandomness of the encrypted images (without leaking information about the original images). If indices remapping is used the obtained average bit rate drops from ~0.35 to ~0.3 bit/pixel. The average correlation factor

between the plain and ciphered images is ~0.05. Incorporating SOC leads to ~45% less full indices and hence less encryption burden.

Fig.7 Histograms of the original and encrypted airplanes images and VQ indices. Table 1. Results of SE: bitrate (BR), percentage of encrypted bit stream (E%), correlation factor between the plain and ciphered images (CF), and percentage of full indices (FI%). airplanes

tank

airfield

harbor

B R

NEXT

0.322

0.390

0.410

0.321

0.36

NEXTSOC

0.320

0.385

0.402

0.319

0.35

E %

NEXT

16.46

15.86

25.26

22.32

19.97

NEXTSOC

11.35

8.98

17.06

15.02

13.10

C F

NEXT NEXTSOC

-0.023 0.027

0.081 0.078

0.021 0.004

0.104 0.094

0.057 0.051

F I %

NEXT

9.03

10.77

18.96

12.74

12.9

NEXTSOC

5.73

5.35

12.18

8.04

7.8

Mean

6. CONCLUSION Joint vector quantization-based image adaptive index compression and selective encryption (SE) schemes are proposed. A novel better SE scheme selectively encrypts ~8% to ~13% of the compressed bit stream if all full indices only or both full indices and prediction tables are encrypted, respectively. Exhibiting sufficient uniform pseudo-randomness, the output does not reveal information about the original image. Gradual partial reconstruction is also flexibly available with very low quality images if less bit percentage of the full indices and prediction tables are encrypted. The output is generally bit stream format-compliant and length preserving.

REFERENCES [1] A. M. Askicioglu and J. Delp, "An overview of multimedia content protection in consumer electronics devices," Signal Processing: Image Communication, vol.16, no.7, pp.681-699, 2001. [2] Xiliang Lu and Ahmet M. Eskicioglu. Selective encryption of multimedia content in distribution networks: Challenges and new directions. In Proc. IASTED CIIT03, AZ, USA, Nov. 2003. [3] W. Stallings, Cryptography and Network Security, Prentice Hall, 2006. [4] A. Said and W. A. Pearlman, "A new fast and efficient image codec based on set partitioning in hierarchical trees," IEEE Trans. on CAS for Video Technology, vol.6, no.3, pp.243-250, Jun. 1996. [5] A. Said, "Measuring the strength of partial encryption schemes," in Proc. IEEE ICIP'05, vol.II, pp.1126-1129, 2005. [6] T. D. Lookabaugh and D. C. Sicker, "Selective encryption for consumer applications," IEEE Comm. Mag., vol.42, no.5, 2004. [7] C. J. Skrepth and A. Uhl, Selective encryption of visual data: classification of application scenarios and comparison of techniques for lossless environment," In Proc. of the IFIP Conf. on Comm. and Multimedia Security (CMS'02), Protoroz, Slovenia, 2002.

[8] D. Engel, T. Stuetz, and A. Uhl, "Efficient Transparent JPEG2000 Encryption With Format-Compliant Header Protection," in Proc. of the IEEE ICSPC'07, Dubi, UAE, 24-27 Nov., 2007. [9] R. Norcen, M. Podesser, A. Pommer, H.-P. Schmidt, and A. Uhl, "Confidential storage and transmission of medical image data," Computers in Biology and Medicine, vol.33, no.3, pp.277–292, 2003. [10] D. Jones, "Data compression and encryption algorithms," Available: www.cs.uiowa.edu/~jones/compress [11] D. Jones, "Applications of splay trees to data compression," Communication of ACM, pp.996-1007, Aug. 1988. [12] X. Liu, P. G. Farrell, and C. A. Boyd, "Resisting the Beregn-Hogan attack on adaptive arithmetic coding," In Proc. of the 6th IAM Int. Conf. on Cryptography and Coding, pp. 199-208, 1997. [13] N. Bourbakis and C. Alexopoulos, "Picture data encryption using scan patterns," Pattern Recognition, vol.25, no.6, pp.567-581, 1992. [14] H. K. C. Chang and J. L. Liu, "A linear quadtree compression scheme for image encryption," Signal Processing: Image Communication, vol.10, no.4, pp.279-290, Sept. 1997. [15] F. Li, Z. Wang, P. Luo, and X. Li, "On the Effectiveness of Partial Encryption for Image Sets Organized with a Tree Data Structure," in Proc. of the World Congress in Computer Science, LDCOMP'07IPCV'07, Las Vegas, USA, June 25-28, 2007. [16] H. Cheng and X. Li, "Partial encryption of compressed images and videos," IEEE Trans. on Image Processing, vol.48, no.8, 2000. [17] L. Tang, "Methods for encrypting and decrypting MPEG video data efficiently," in Proc. of the ACM Multimedia'96, pp.219–229, 1996. [18] C. Shi and B. Bhargava, "A fast MPEG video encryption algorithm," in Proc. of the ACM Multimedia'98, pp.81–88, 1998. [19] A. M. Alattar, G. I. Al-Regib, and S.A. Al-Semari, "Improved selective encryption techniques for secure transmission of MPEG video bitstreams," in Proc. of the IEEE ICIP’99, pp.256–260, 1999. [20] Z. Liu and X. Li, "Motion vector encryption in multimedia streaming," in Proc. IEEE 10th Multimedia Modeling Conf., pp.64–71, Jan. 2004. [21] G. Liu, T. Ikenaga, S. Goto, and T. Baba, "A Selective Video Encryption Scheme for MPEG Compression Standard," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E89-A, no.1, pp.194-202, 2006. [22] A. Pommer and A. Uhl, "Selective encryption of wavelet-packet encoded image data — efficiency and security," ACM Multimedia Systems, vol.9, no.3, pp.279–287, 2003. [23] J. Liu, "Efficient selective encryp. for JPEG2000 images using private initial table," Pattern Recognition, vol.39, pp.1509-1517, Aug. 2006. [24] W. Zeng and S. Lei, "Efficient frequency domain video scrambling of digital video," IEEE Trans. Multimedia, vol.5, pp.118-130, 2003. [25] R. Noreen and A. Uhl, "Encryption of wavelet-coded imagery using random permutations," in Proc ICIP'04, vol.5, pp.3431-3434, 2004. [26] S. Li, C. Li, G. Chen, D. Zhang, and N. Bourbakis, "A general cryptanalysis of permutation-only multimedia encryptions," 2005 [27] D. Xie and C. J. Kuo, "Multimedia data encryption via random rotation in partitioned bit streams," in Proc. of IEEE ISCAS 2005, vol.6, pp.5533-5536, 23-26 May 2005, [28] A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Norwell, MA, USA, Kluwer, 1992. [29] G. Campobello, M. Mantineo, G. Patane, and M. Russo, "LBGS: a smart approach for very large data sets vector quantization," Signal Processing: Image Communication, vol.20, pp.91-114, 2005. [30] L. George and B. Al-abudi, "Fast multi-level image vector quantization," in Proc. of IEEE ICSPC, Dubi, UAE, 2007. [31] M. F. Abdel-Latif, T. K. Abdel-hamid, M. M. Doss, and H. Selim, "Utilizing repeated adjacencies of vector quantization indices in image compression," in Proc. IEEE ISSPIT, Rome, Italy, 2004. [32] C. Hsieh and J. Tsai, :Lossless compression of VQ index with search order coding," IEEE Trans. on IP, vol.5, pp.1579-1582, 1996. [33] T. S. Chen, C. C. Chang, and M. S. Hwang, "A virtual image cryptosystem based upon vector quantization," IEEE Trans. on IP, vol.7, no.10, Oct. 1998, pp.1485-1488. [34] W. B. Lee, T. H. Chen, and C. C. Lee, "Security of new encryption algorithm for image cryptosystems," Imaging Science Journal, vol.54, no.3, pp.178-187, 2006. [35] T. S. Chen and C. C. Chang, "New method of secret image sharing based upon vector quantization," SPIE Journal of Electronic Imaging, vol.10, no.4, Oct. 2001, pp. 988-997. [36] SIPI-USC Database, available at http://sipi.usc.edu/database .

1280

View publication stats