59.xps Middle-East Journal of Scientific Research 12 (12): 1873-1880, 2012 ISSN 1990-9233 © IDOSI Publications, 2012 DOI: 10.5829/idosi.mejsr.2012.12.12.1236 Corresponding Author: T.V.U. Kiran Kumar, Department of ECE, Bharath University, Chennai-73. 1873 Visual Secret Sharing Scheme for JPEG Compressed Images T.V.U. Kiran Kumar, B. Karthik and E. Bharath Kumaran Department of ECE, Bharath University, Chennai-73, India Abstract: Existing schemes modify either the pixel values or change the Color Index Table (CIT) values. Almost all the existing techniques are applicable to primarily non-compressed images in either monochrome or color domains. However, most imaging applications including digital photography, archiving and internet communications nowadays use images in the JPEG compressed format. Application of the existing Visual Secret Sharing schemes for these images requires conversion back into spatial domain. In this paper we propose a shared key algorithm that works directly in the JPEG domain, thus enabling shared key image encryption for a variety of applications. The scheme directly works on the quantized DCT coefficients and the resulting noise- like shares are also stored in the JPEG format. The decryption process is lossless preserving the original JPEG data. Key words: Pixel values Color Index Table Compressed format Shared key Visual Secret sharing Image encryption. INTRODUCTION applications in the Internet world. The computer-based A secret sharing encryption scheme creates several shared image encryption systems. This has also lead to (n) shares of the original information and distributes to n development of methods that apply to color images. In participants. The decryption is carried out by using a addition, the methods described, this also address prescribed number (k, k = n) of subset shares. Fewer than computational complexity issues by designing schemes k shares are insufficient to reconstruct the original data. that require simpler bit-level arithmetic operations during The ‘k’ keys are generated in such a way that the share decryption. This method similar in spirit to these schemes images are “random" looking with no semblance to the but addressing a larger domain of images stored in original image. It is a highly secure mechanism since the compressed digital formats. Large number of imaging decryption is being performed by the human visual applications including digital photography, archiving and system when both shares are brought together. Here first internet communications primarily use images stored in we will see 2-out-of-2 or {2, 2} secret sharing method. the JPEG format. Most of the digital cameras in the market Next we will see an extension to k out of n {n,k} secret use JPEG. Application of the existing shared key sharing where k stacked images are needed to reconstruct cryptographic schemes for these images requires the clear image. conversion back into spatial domain. When transmission All the existing schemes, the encryption-decryption and storage of the shares are concerned, one may not process is lossy. The original image is transformed into a necessarily be able to apply lossy compression haltoned image before deriving the share images. techniques since the loss may result in an inability to Halftoning is a lossy process. Furthermore, in many of the decrypt. Hence, encryption techniques applicable in the proposed schemes the reconstruction from the k shared compressed domain are needed. images creates a lossy version of the half-toned image Visual cryptography based on secret sharing has itself. This led to several researchers’ efforts on improving received considerable attention since the publication contrast quality of the decrypted images. Though they of [1] by Naor and Shamir. A secret sharing lose the ability of decryption by visual means, such encryption scheme creates several (n) shares of the encryption schemes have a large number of potential original information and distributes to n participants. decryption also opens an avenue to a wide variety of Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1874 The decryption is carried out by using a prescribed Visual Secret Sharing Scheme number (k, k<=n) of subset shares. Fewer than k shares (A) {2, 2} Shared Key Encryption: This shared key are insufficient to reconstruct the original data. The algorithm [5] that works directly in the JPEG domain, thus scheme proposed in [1] generated two shared key images enabling shared key image encryption for a variety of from a given binary image as a printed page and a applications. The scheme manipulates the quantized DCT transparency of the same size. When the transparency is coefficients and the resulting noise-like shares are also stacked on top of the printed page, the original image is stored in the JPEG format. The decryption process that formed. The two keys are generated in such a way that the combines the shares is lossless and hence the original share images are “random" looking with no semblance to JPEG file’s fidelity is preserved. Our experiments indicate the original image. It is a highly secure mechanism since that each share image is approximately the same size as the decryption is being performed by the human visual the original JPEG retaining the storage advantage system when both shares are brought together. This is a provided by JPEG. 2-out-of-2 or {2,2} secret sharing method. Several Both encryption and decryption require only small publications that followed this development extended the modifications to standard JPEG computational basic visual cryptography using concepts from digital procedures. This in turn implies an easy adaptation for a halftoning [2, 3] to address gray scale images and color hardware implementation which is particularly useful for pictures [4]. In many of these schemes, the encryption- digital camera applications. decryption process is lossy. The original image is transformed into a haltoned image before deriving the Monochrome Images: The lossy version of JPEG image share images. Halftoning is a lossy process. Furthermore, compression uses DCT.A monochrome image is first split in many of the proposed schemes the reconstruction into 8×8 non-overlapping blocks of pixels. An 8×8 DCT is from the k shared images creates a lossy version of the applied to each block and the resulting coefficients are half-toned image itself. This led to several researchers’ scalar quantized using a quantization matrix. The efforts on improving contrast quality of the decrypted quantized coefficients are then converted from a two- images. dimensional representation to a one-dimensional vector However, in some of the recent publications [6, 7] by a process known as zig-zag scanning and sent to an the original intent of performing the decryption using the entropy coder that uses either Huffman or arithmetic human visual system with a simple mechanical system of coding. The process is shown in Fig 2. stacking transparencies is lost by requiring computer The zig-zag transformation transforms 8x8 two 2D processing to reconstruct the image. Though they lose values into 64 one dimensional quantized coefficients. For the ability of decryption by visual means, such encryption an 8×8 block Bn with an index X , let the quantized schemes have a large number of potential applications in coefficients be denoted as, where X corresponds to the the Internet world [6]. This has also lead to development DC coefficient and the rest to the AC coefficients. The of methods that apply to color images. In addition, the index n can be obtained as the standard scanning order of methods described in [6] and [7] also address blocks of the image as defined in the JPEG standard. We computational complexity issues by designing schemes will also use the notation of that require simpler bit-level arithmetic operations during decryption. In this paper, we describe a method similar in X =[X , X X ,…, X ] (1) spirit to these schemes but addressing a larger domain of images stored in compressed digital formats. According to baseline JPEG specification, the input In [5] the author proposed a scheme for shred key image components are represented by 8-bit pixel values encryption, which is used in this paper for creating shares and the quantized samples are limited to at most 15 bits of from a secret image. The author a proposed scheme for magnitude and a sign bit. For gathering the statistics for {2,2} shared key encryption for JPEG images and entropy coding purposes, XN i values are placed in bins suggested the implementation for {n,k} shared key according to the number of bits needed to represent its encryption. Based on this paper the {n,k} shared key magnitude in binary. This is given by encryption has been developed and shown the results in this paper. N=log X (2) n n n n n n n 1 1, 1 1 2 1 n ( ) ( ) [ ] [ ]{ } ( ) [ ] [ ]{ } ( ) .n1 i.n1 .n2 i i .n1 i 0,1 , 1, 0 ifb L 1 b L b L 0,1 , 1, 0 ifb L 1  = ∈ = ( ) ( ) ( ) N .n1 .n1 N .n1 N-L i i i L=1 X L X L X2 b N-L X2+∑ ( ) ( ) ( ) N .n2 .n2 N .n1 N-L i i i L=1 X L X L X2 b N-L X2+∑ Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1875 Fig. 1: {2,2} Shared Key Encryption Mechanism for Fig. 2: Shared Key Decryption Process. JPEG images Now,X can be represented in two’s complement form asi n X b (N) b (N-1)… b (0) (3)i = i i i nb n n n Where each b (l), l=0,1,2,…Ni n N is a binary value, either zero or one. Hence, the value of Using the above procedure, we obtain two X ni can be obtained as N sequences, Xn1 and Xn2, that represent zig-zagged, quantized coefficients for 8×8 blocks for the entire image X -b (N) X 2 + b (N-L) X 2 L=1 (4) based on the original sequence Xn.These two sequencesi = i in n N n N-L Note that N is dependent of both i and n and we arithmetic coding techniques to produce the two share have not explicitly shown the dependency to reduce images in the JPEG format. The sequence Xni and the clutter. Now, let us consider an encryption system where binary representation Xnbi can be reconstructed simply the image to be encrypted is given in the JPEG format. Let by a bit-wise XOR operation (+) of the N+1-bit shares. (8) the image be decoded partially to obtain the zig-zagged, quantized coefficients X =0,1,2,3,…63.corresponding toi n block Bn. At this stage, the two’s complement Color Images: Just as with the JPEG compression, the representation X of X as indicated in the above proposed method is color blind. JPEG uses a componenti i nb n equation is available. Now, two versions, X and X , model for applications to enable coding of color images.I In1 n2 are generated using a {2, 2} shared secret key encryption Typically, most applications use three components in the method based on random assignment. We use an YCbCr color space. The chrominance data is sub-sampled assignment scheme based on the one proposed by [7]. for better compression efficiency. The proposed Each bit b n i (l) is split into two shares using the encryption scheme uses the same JPEG approach to following scheme: handle color images. Since the resulting image shares are (5) JPEG is also suitable for our application. JPEG supports The above procedure is applied to all N+1 bits of X encryption technique in the previous subsection relies oninb to obtain X i and X i whose values X and X a standard baseline mode of JPEG. JPEG also has ai i i in1b n2b n1 n2 respectively are calculated as number of other modes such as progressive DCT, (6) and (7) can further be entropy coded using either Huffman or JPEG images, any color space that can be handled by up to 255 components in one image and hence support for a large variety of image formats. The description of the Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1876 hierarchical and lossless. The progressive DCT mode by multiple scans of the quantized coefficients allows incremental transmission of the image so that the picture could be reconstructed sequentially with increasing fidelity. There are two modes for performing progressive DCT: spectral selection and successive approximation. In spectral selection, the AC coefficients are sent after sending the DC coefficients. The successive Fig. 3: Binary tree structure of {n,k} encryption approximation uses a lower precision at the start and improves the precision in the subsequent scans. A mixed mode by combining the two schemes is also possible. For the progressive-DCT JPEG encoding, the proposed encryption scheme applies directly. Once the shares are created, the progressive-DCT based scans could be applied to generate two JPEG shares. During the decode, the shares have to be completely decoded to produce Xn1 and Xn2. XOR operation on these values produce the Xn sequence which can further be processed to obtain the clear picture. JPEG also has a lossless mode. The lossless coding uses differential pulse code modulation (DPCM) and Huffman or arithmetic coding. The proposed encryption method does not directly apply to lossless mode but a scheme described in could be used for this purpose. The hierarchical mode in JPEG uses multi-scale approach to compression. While the proposed scheme can potentially work in the hierarchical mode with DCT- based coding, it will not work in the lossless hierarchical mode. The scheme [5] for share generation is listed below. Read the image in JPEG format and perform variable- length decode to obtain the quantized DCT coefficients, X n, for each block Bn. Using random numbers from a pseudo-random number generator, produce the Sequences Xn1 and Xn2. Perform entropy coding for the two sequences to produce two JPEG share images with the same dimensions and color space. The decryption procedure is simply the reverse of it, where the decoder has also been modified to read two JPEG images and perform entropy decoding to get two share sequences of the quantized DCT coefficients. The sequences are XORed to produce the decrypted Table 1: Shared images and their positions in linear array Secret Share Share Share Share Share Share Name Image 1 2 3 4 5 6 ArrayPosition 1 2 3 4 5 6 7 Share Share Share Share Share Share Share Share 7 8 9 10 11 12 13 14 8 9 10 11 12 13 14 15 sequences and the rest of the decode operations, dequantization and inverse transform, are Continued to produce the decrypted image. {N,k} Shared Key Encryption Algorithm: We can extend the {2,2} encryption to {n,k} encryption by extending the scheme for the generated shares. (i.e). Again generating shares for the Shares 1 & 2. From Share 1 we will get Share 3 and Share 4.Similarly from Share 2 we will get Share 5 and Share 6.This scheme looks like a downward growing binary tree. For the better programming of binary tree, we put it into single dimensional array as following. The child node of a parent node ‘p’ (p is position) can expressed as, Left child=2 x p Right child= (2 x p) +1 RESULTS {2, 2} Shared Key Encryption: We performed the experiments on several types of images and compared its performance. The shares were generated using the proposed method. The decrypted image is exactly same as the original, From Figs.; it is clear that the generated shares have no visual resemblance to the originals and are “random" looking. The randomness is slightly modulated by the underlying image shapes. Hence, the storage and transmission gains obtained by JPEG are directly applicable to the proposed method. {N,2} Shared Key Encryption: Here 14 Share images have been generated from the secret image. The decryption can be carried out from the following combination of share images. Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1877 Fig. 4: Secret Image Share 1 Share2 Decrypted from Share 1 and Share 2 images Figure 2 {2,2} Shared key encryption 2 Shares: {Share 1, Share 2} 3 Shares: {Share 2, Share 3, Share 4} {Share 1, Share 5, Share 6} 4 Shares: S=Share {S3,S4, S5, S6} {S1, S5, S13, S14} {S1, S6, S11, S12} {S2, S3, S9, S10} {S2, S4, S7, S8} 5 Shares: {S4,S5,S6,S7,S8}{S3,S4,S5,S13,S14} {S3,S5,S6,S9,S10}{S3,S4,S6,S11,S12} {S1,S11,S12,S13,S14}{S2,S7,S6,S8,S9,S10} {S1,S2,S3,S7,S8}{S1,S2,S4,S9,S10} {S1,S2,S5,S11,S12}{S1,S2,S6,S13,S14} 6 Shares: {S5, S6, S7, S8, S9, S10} {S3, S4, S11, S12, S13, S14} {S3,S5, S9, S10, S13, S14} {S4, S6, S7, S8, S11, S12} {S3,S6,S9,S10,S11,S12} {S4,S5,S7,S8,S13,14} {S1,S3,S5,S6,S7,S8} {S1,S4,S5,S6,S9,S10} {S2,S3,S4,S5,S11,S12} {S2,S3,S4,S6,S13,S14} 7 Shares: {S6,S7,S8,S9,S10,S11,S12} {S3,S9,S10,S11,S12,S13,S14} {S4,S7,S8,S11,S12,S13,S14} {S5,S7,S8,S9,S10,S13, S14} {S1,S3,S5,S7,S8,S13,S14}{S1,S3,S6,S7,S8,S11,S12} {S1,S4,S5,S9,S10,S13,S14}{S1,S4,S6,S9,S10,S11,S12} {S2,S3,S5,S9,S10,S11,S12}{S2,S3,S6,S9,S10,S13,S14} {S2,S4,S5,S7,S8,S11,S12}{S2,S4,S6,S7,S8,S13,S14} 8 Shares {S7, S8, S9, S10, S11, S12, S13, S14} {S1,S2,S3,S4,S7,S8,S9,S10} {S1,S2,S5,S6,S11,S12,S13,S14} {S2,S6,S7,S8,S9,S10,S13,S14} {S2,S5,S7,S8,S9,S10,S11,S12} {S1,S4,S9,S10,S11,S12,S13,S14} {S1,S3,S7,S8,S11,S12,S13,S14} {S1,S2,S4,S6,S9,S10,S13,S14} {S1,S2,S4,S5,S9,S10,S11,S12} {S1,S2,S3,S6,S7,S8,S13,S14} {S1,S2,S3,S5,S7,S8,S11,S12} 9 Shares: {S1,S3,S4,S5,S6,S7,S8,S9} {S2,S3,S4,S5,S6,S11,S12,S13,S14} 10 Shares: {S1,S3,S4,,S6,S7,S8,S9,S10,S11,S12} {S1,S3,S4,S5,S7,S8,S9,S10,S13,S14} {S2,S3,S5,S6,S9,S10,S11,S12,S13,S14} {S2,S4,S5,S6,S7,S8,S11,S12,S13,S14} 11 Shares: {S1,S3,S4,S7,S8,S9,S10,S11,S12,S13,S14} {S2,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14} {S1,S2,S4,S5,S6,S9,S10,S11,S12,S13,S14} {S1,S2,S3,S5,S6,S7,S8,S11,S12,S13,S14} {S1,S2,S3,S4,S6,S7,S8,S9,S10,S13,S14} {S1,S2,S3,S4,S5,S7,S8,S9,S10,S11,S12} 14 Shares {S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14} The numbers which are underlined and italic are containing the redundant shares. Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1878 Fig. 5: Fig. 6: Table 2: Shared images (n) Shares required --------------------------------------------------------------- for decryption(k) 2 4 6 8 10 12 14 2 1 1 1 1 1 1 1 3 - 1 2 2 2 2 2 4 - - 1 2 3 4 5 5 - - - 1+1 3+2 4+3 6+4 6 - - - 1 1+2 3+3 6+4 7 - - - - - 1+4 4+8 8 - - - - 1 4 1+10 9 - - - - 1 1 2 10 - - - - - 1 4 11 - - - - - 1 6 12 - - - - - - - 13 - - - - - - - 14 - - - - - - 1 Irredundant combinations 1 2 4 6 10 15 25 Total combinations 1 2 4 8 16 32 64 The numbers underlined and bold in table 2 are redundant combinations. From the results we can generalize the formula as Total Combinations=2(n / 2 ) -1 Where ‘n’ is the no of shared images. From the results the following are identified. For any image and any ‘n’ the shared images will have almost equal size. And never equal. For a specified image and specified ‘n’ the shared images created at different period will never same.The probability for being same is 1/( ImageLength*ImageWidth*3*8). The decryption can be carried out at different combination for different ‘k’ values. In the decryption combinations many set of combinations are redundant. Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1879 The graph plotted for different ‘n’ values vs. the sizes of the resulting shares are comparable to that of their combinations shows, it is binary exponential. straight JPEG representations. The proposed method can For the values ‘k’ greater than 4, contains the be extended to any other transform or wavelet domain redundant shares. techniques for image coding. An extension to implement Extension and Further Experiments looking into application of this scheme for secure Generalizing the Formula for Decryption: The scheme smartcards and digital rights management. can be generalized to a formula. Look out the first combination in all possible combination. REFERENCES (1,2) (2,3,4) (3,4,5,6) (4,5,6,7,8) (5,6,7,8,9,10) (6,7,8,9,10,11,12) (7,8,9,10,11,12,13,14).If you start at 1. Naor, M. and A. Shamir, 1995. in: A. de Santis (Ed.), position ‘p’ then up to 2p shares we need add to decrypt Visual Cryptography, Advances in Cryptology: successfully (i.e.) p, p+1, p+2,…, 2p.Similarly this can be Eurocrypt ’94, Lecture Notes in Computer Science, extended to get a generalized algorithm for decryption. 950: 1-12. Share Creation in JPEG 2000 Image: The proposed 1996. “Visual cryptography for general access scheme can be implemented in other transforms like structures," Information and Computation, wavelet (JPEG 2000) and any other transforms which is 129(2): 86-106. used for compression. The JPEG 2000 has higher 3. Lin C.C. and W.H. Tsai, 2003. “Visual cryptography compression and less visibility of artifacts. Thus it will be for gray-level images by dithering techniques," useful for higher compressed images. Pattern Recognition Letters, 24: 349- 358. 4. Hou, Y.C., 2003. "Visual cryptography for color Implementing in Reconfigurable Hardware: System images," Pattern Recognition, 36: 1619-1621, 2003. generator tool [14] would be useful when implementing in Rahman Mohseni-Astani, Poorya Haghparast and FPGA (Field Programmable Gate Arrays).The tool can be Sahab Bidgoli-Kashani, “Assessing and Predicting used for converting matlab functions into VHDL/Verilog the Soil Layers Thickness and Type Using Artificial code for the specified target like Spartan 2E,Virtex- Neural Networks - Case Study in Sari City of Iran”, 4,etc.Thus the encryption can be tested in hardware and Middle-East Journal of Scientific Research, the optimization can be achieved.More detals about the ISSN:1990-9233, 6(1): 62-68, 2010. system generator are available in [14]. 5. Ihsan Nuri Demirel, 2010. “Conceptual Description, Summary and Future Work: The proposed method can Participation, Assumption of Inefficiency”, Middle- take in JPEG and create ‘n’ shares in the JPEG format. The East Journal of Scientific Research, ISSN:1990-9233, shares are generated using the quantized DCT 6(1): 15-21. coefficients in the JPEG representation. The shares are 6. Subramania Sudharshan, 2005. ”Shared key used to reconstruct the original quantized DCT encryption of JPEG color images”, IEEE Transactions coefficients during decryption. The proposed scheme is on Consumer Electronics, 51: 4. applicable to color and monochrome images and offers all 7. Hou, Y.C., C.Y. Chang and F. Lin, 1999. "Visual the compression advantage of JPEG to all the share cryptography for color images based on color images. decomposition," Proceedings of the Fifth Conference The computational complexity of the encryption on Information Management, pp: 584-191. process is comparable to that of a standard JPEG encoder, 8. Chang, C.C. and T.X. Yu, 2002. "Sharing a secret gray an additional bit stream entropy encoder and a random image in multiple images," Proceedings of the First number generator. Similarly, the decryption complexity is IEEE International Symposium on Cyber Worlds, pp: also augmented by an additional entropy decoder when 230-237. compared to JPEG decoding. The hardware architecture of 9. Lukac, R. and K.N. Plataniotis, 2004. "Cost-effective the encryption and the decryption processes can easily encryption of natural images," Proceedings of 22nd be obtained by modifying the standard JPEG pipelines. Queen’s Biennial Symposium on Communications, (A software implementation based on the Matlab code is pp: 89-91, (Also from the URL http://www.ece. available from the author.) It was also shown that the queensu. ca/symposium/papers/2C_1.pdf) in FPGA is under development [14]. Currently, we are 2. Ateniese, G., C. Blundo, A. De Santis and D. Stinson, Hastiness in Obtaining Result, Voluntary Middle-East J. Sci. Res., 12 (12): 1873-1880, 2012 1880 10. Independent JPEG Group, http://www.ijg.org. 13. Michael W. Marcellin, Michael J. Gormish, Ali Bilgin 11. Mathematics Department, University of Salzburg, and Martin P. Boliek, 2000. An Overview of JPEG- pLab: Theory and Practice of Random Number 2000.Proceedings of the Data Compression Generation,http://random.mat.sbg.ac.at/. Conference, pp: 523-544. 12. http://www.cryptography.com/resources/whitepape 14. http://www.mathworks.com rs/VIA_rng.pdf 15. http://www.xilinx.com