Joint Video Compression and Encryption using …

1 978-1-4244-7932-0/10/$ 2010 IEEEJ oint Video Compression and Encryption usingArithmetic coding and ChaosAmit PandeDepartment of Computer Science,University of California,Davis, CA, USAE mail: ZambrenoElectrical and Computer Engineering,Iowa State University,Ames, IA, USAE mail: MohapatraDepartment of Computer Science,University of California,Davis, CA, USAE mail: Joint Video Compression and Encryption (JVCE)has gained increased attention in the past couple of years toreduce the computational complexity of Video Compression , aswell as provide Encryption of multimedia content for web this paper, we present a JVCE framework based on BinaryArithmetic coding (BAC). We first present an interpretation ofBAC in terms of a skewed binary map and then describe 7other possible chaotic maps which give similar Shannon optimalperformance as BAC. We then propose a modification of BACin which the overall length within the range [0,1) allocatedto each symbol is preserved, but the choice of map used toencode each symbol is based on a key.]

2 The encoder, referredto as Chaotic Binary arithmetic Coder (CBAC), has the effectof scrambling the intervals without making any changes to thewidth of interval in which the codeword must lie, thereby allowingencryption without sacrificing any coding efficiency. We alsopresent some some security enhancement features to show howthey can alleviate the limitations of our technique against knowncryptanalysis on BAC-based Encryption Terms Chaos, Encryption , Skewed Tent Map, Arith-metic coding , Cryptography, Data INTRODUCTIONJ oint Video Compression and Encryption (JVCE) has gainedincreased attention in the past couple of years to reduce thecomputational complexity of Video Compression , as well asprovide Encryption of multimedia content for web Video Encryption algorithms must efficiently cater tothe characteristics of Video bitstream which are differentfromtraditional digital data stream: Video content is larger insizeand structured in different ways to enable different applicationsand network communications.

3 Moreover, multimedia web ser-vices (such as Video -on-demand, multimedia messages, andvideo conferencing) over heterogeneous architectures such asmobile phones and laptops need scalable media transmissionschemes which have low decryption and re- Encryption costoverhead, shorter delays and QoS requirements (such as real-time playback and low delay). Future Video search enginesmust be able to search for a particular person or object fromsecure Video libraries. The increased trend towards embeddeddevices require such algorithms to have low is difficult to cater the multiple requirements of lowcomputational overhead, high security levels and other needsof compressed multimedia bitstreams [1] by the traditionalcompress-then-encrypt paradigm. Generic Encryption algo-rithms are thus disadvantageous for multimedia security. Se-lective Encryption schemes have been developed but most ofthem have proven to be weak against cryptanalysis [2], [3].JVCE schemes come to the rescue by providing Encryption atlow overheads and without changing the structure of multime-dia content.

4 In this paper, a JVCE scheme based on ArithmeticCoding is presented and security enhancements are proposedto make this scheme secure against coding [4] involves associating a sequence ofsymbols with a position in the range [0,1), and is usuallyimplemented recursively. It typically enables very high codingefficiency as multiple symbols are coded jointly. It has beenadopted for use in image Compression standards, includingJPEG2000 and to provide lossless entropy to large volumes of multimedia data and usefulproperties of compressed bitstream such as rate-adaptive trans-mission, scalability, DC-image extraction for content searchingetc generic Encryption algorithms such as AES, DES etchave disadvantages for multimedia security. Many multimedia-specific algorithms have been proposed in research some efforts have been made towards Joint de-sign of Encryption and Compression modules (particularlythe entropy coding techniques such as arithmetic coding ) toprovide a more flexible Encryption of data.]

5 These techniquesallow Encryption at little/ no computational overhead and (inmost cases) preserve the format compatibility of compressedbitstream. For example- Liu et al. [5] presented a system usingtable-based bit sequence substitutions to enable the arithmeticcoding stage to be simultaneously used for Encryption . Theauthors in [6], [7] associate a fixed length index to eachvariable length codeword to encrypt the indexes. However, allthese approaches suffer from Compression inefficiency whilethe latter also leads to generation of emulated [8], a chaos-based adaptive arithmetic coding techniquewas proposed. The arithmetic coder s statistical model is madevarying in nature according to a pseudo-random bitstreamgenerated by coupled chaotic systems. Many other techniquesbased on varying the statistical model of entropy codershave been proposed in literature, however these techniquessuffer from losses in Compression efficiency that result fromchanges in entropy model statistics and are weak againstknown attacks [9].

6 Recently, Grangetto et al. [10] presented a randomizedarithmetic coding (RAC) scheme which achieves encryptionby inserting some randomization in the arithmetic codingprocedure at no expense in terms of coding efficiency. RACneeds a key of length 1-bit per encoded symbol. Wen and Kimet al. [11], [12] presented a generalization of this procedure,called as key-Splitting arithmetic coding (KSAC) where akey is used to split the intervals of an arithmetic coder. Somelimitations and features of KSAC are presented next giving themotivation to improve the security performance of arithmeticcoding:1) KSAC introduces losses in coding efficiency which arelater restricted to a small value by putting some con-straints on the keyspace [11].2) The KSAC encoder may have to work with multiple sub-intervals and needs to compute one shortest representationarithmetic code for each subinterval, thereby increasingthe computational cost of encoder ) The memory requirements of KSAC coder are atleastdouble that of ) Although the key length can be arbitrary, the authorsrestrict it to 2 bits per encoded symbol [11].

7 5) Successful attacks have been demonstrated against KSAC scheme [9].This motivates us to present an arithmetic encoder whichcan encode data without any Compression inefficiency andpromises better security than existing this paper we first present arithmetic coding as a chaoticiteration on skewed binary map and then use this modelto propose a more robust Chaotic Binary arithmetic Coder(CBAC) scheme which is similar to RAC in that it incursno computational or memory overhead but provides morepossibilities of interval ordering (leading to keys of 3 bits persymbol). A security enhancement is proposed to counter theknown attack against arithmetic coding based arithmetic coding AS A NON-LINEAR CHAOTICSYSTEMThe work by Nagraj et al. [13] derives the equivalence ofarithmetic coding and chaotic piece-wise linear maps (whichthey refer to as GLS coding ). They develop a theory forskewed maps (skewed with a non-linearization parameterato be used for image Encryption ) to be used for encryptionand Compression purposes.

8 The above approach has two maindisadvantages, making the scheme prone to cryptographicattacks:1) A wrong guess in value of the skew parameteramaylead to imperfect reconstruction and not necessarily tocompletely random output. The first few symbols ofbinary string may be correctly guessed by a wrong, butclosely related value ) It is possible to iteratively guess the value ofabylaunching known plaintext attack. The closer the valueofagets to the originalavalue, the more symbols willbe reconstructed 1. (a) The binary map with p= (probability for symbol 0 ),Back-iterating the chaotic map to get the code word for encoding 100 withthis map. (b) mapping the symbol 0 , (c) mapping 00 and (d) mapping 100 to get the code-intervalThe equivalence of chaotic maps to arithmetic coding isexplained briefly with an encrypting the binary message 100 of length3 bits. For binary arithmetic coding , let p (probability foroccurance of symbol 0 ) be preselected to For arithmeticcoding, we will choose the interval [ ,1) in first iteration toencode 1 , [ , ) to encode the 10 and [ , ) toencode the 100.]]]

9 A number lying in the interval [ , )represents the arithmetic code for binary message 100 .Now, let us define the skewed binary map with the followingequations:y={x/pwhenx p(x p)/(1 p)whenx > p}(1)Iteration on this chaotic map (Figure II(a)) is equivalent todecoding the arithmetic code. The symbol decoded is definedas follows:Decode{ 0 whenx p 1 whenx > p}(2)Back iteration on this map is equivalent to the arithmeticencoding procedure, defined by the following equation:x={pywhen 0 (1 p)y+pwhen 1 }(3)To encode 100 with the p value precomputed to wesubstitute the p value to get the chaotic map as shown inFigure II(a). In this case, however the encoding is done inreverse order: from end of sequence to the beginning. We firstencode 0 and get the interval [0, ) (see figure II(b)), nextwe encode 00 to get the interval [0, ) (see figure II(c))and finally we encode 1 to get the interval corresponding to 100 as [ , ). So we have reached the same intervalas the arithmetic decoding part is also simple.]]]]

10 Let us say that thetransmitted code was Iteration on the chaotic map asin Equation 1 gives the values [ , , ] on twoiterations. Thresholding it using the rule in Equation 2 givesus the original sequence [1 0 0] or 100 .III. CHAOTICBINARYARITHMETICCODERIn the previous section we explained how arithmetic codingcan be viewed as re-iteration on skewed binary map. Thereare, however, eight equivalent modes of skewed binary mapswhich can be used for iteration. They are shown in Figure modes differ from each other in the way input is mappedinto the chaotic orbit. The maps differ in the interval in whichthe arithmetic code must lie for a symbol 0 or 1 but thewidth of interval remains the same. Hence, all the modes areequivalent as far as Compression efficiency is us define the generalized skewed binary map with thefollowing equations:y={n1x+c1whenx kn2x+c2whenx > k}(4)Decode{ 0 whenx [i1, i2] 1 whenx [i3, i4]}(5)Then, the back iteration on skewed binary map is defined bythe following equations:x={m1y+b1when 0 m2y+b2when 1 }(6)wherem,n,bandcvalues determine the slope of chaoticmap.