14.2.1 Image and Video Coding

Multimedia technology has been rapidly developed in the past several decades. Multimedia coding – compression and binary representation of multimedia data – plays a key role in multimedia applications [1]. Among different forms of multimedia data, digital images and videos are widely used. A digital image is a two-dimensional matrix of pixels whose values represent the brightness or the color of discrete points on the image plane. Depending on the nature of an image, a pixel value can be either a scalar, which is the case of binary and grayscale images, or a triplet representing some color, which is the case of red-green-blue (RGB) color images, for instance. A pixel value can also contain more than three color components, which is the case for multispectral images, but this chapter will not discuss such cases. However, note that all facts about RGB images discussed in this chapter can be generalized to multispectral images because they are largely independent of the dimension of pixel values. Similarly, a digital video is a three-dimensional matrix of pixels where the additional dimension is time. In other words, a digital video is simply a collection of digital images with a sequential order in temporal domain. Each image contained in a digital video is called a frame, and the number of video frames per second is called the frame rate of the video. In some video coding systems, a video frame is divided into a top field composed of odd rows and a bottom field composed of even rows; the two fields are coded separately, which is called interlaced video coding. This chapter does not differentiate video frames from fields to simplify discussion.

Whenever talking about coding, both encoding and decoding are always considered here. The encoding process (or an encoder) transforms an image or a video into a bitstream consuming less space, and the decoding process (or an decoder) recovers the encoded bitstream back to the original uncompressed image/video. An encoder and a decoder are often called a codec collectively.

The encoding and decoding processes are basically symmetric in structure, but they can have completely different computational complexities. Normally, the decoder is much less computationally costly than the encoder. The asymmetry is mainly due to different goals of the two processes: encoding tries to find the compression transform with the best overall encoding performance (compression efficiency as one major but not the only factor), but decoding merely translates what has been encoded in a bitstream into perceptual information following the transform selected by the encoding process. In some cases, however, there is a different scenario: the encoding process should be computationally light but the decoding process can be more computationally expensive. A typical application is wireless multimedia sensor networks (WMSNs) [2], in which encoding is done by resource-constrained sensor nodes (often powered by battery) and decoding by computationally more powerful devices like multicore computers. A special multimedia coding architecture called distributed coding has been developed to handle such asymmetric coding [3].

Although there are many different image and video coding schemes, almost all of them follow the basic structure shown in Figure 14.1. Because of the similarity between the encoder and the decoder, their functionality is briefly explained on the example of an encoder. In the first step, the input image or video passes a preprocessing step, which can include several different processes, such as color space conversion, signal partitioning, and prefiltering (for example, subsampling and noise removal). The main goal of this step is to prepare data for future steps and remove some redundant information that does not need to be processed by later steps. For instance, encoding of color images and videos normally involves a conversion from RGB space to another color space, such as YCbCr and YUV, to separate the luminance and chrominance components so that the lower sensitivity of the human visual system to chrominance components can be exploited to reduce information needed for encoding. The reduction of chrominance information is done by subsampling the chrominance components, meaning to sample them with a lower (normally halved) sampling rate than the luminance component. While this immediately leads to a 2:1 compression ratio, the visual quality of the image/video reconstructed from the halved data remains almost as good as that of the original image/video. Partitioning is another widely use preprocessing technique, which is often useful for speeding up the encoding process.

The second step is lossy coding. It aims at removing psycho-visually redundant information, thus creating an image that is perceptually nearly indistinguishable from the original. The lossy coding part is usually realized by converting the data from spatial domain to frequency domain via a transform, such as the discrete cosine transform (DCT) [4] and the discrete wavelet transform (DWT) [5], and then quantizing the resultant transform coefficients to be integers. The main purpose of using a transform is to decorrelate the original image/video so that less correlative information exists in the new transform domain than in spatial domain. Performing a transform on the whole image/video is computationally expensive, so the common practice is to first partition the image and each video frame into n × n blocks and apply the transform locally on each block. The lossy coding step is optional because in some applications, such as medical imaging and forensics, it may not be desired to lose any information (even when it is invisible to human eyes).

The lossy coding step is followed by lossless coding, which aims at encoding the data in a more compact form so that less bits are needed to represent the same amount of information. Since no information loss is involved in lossless codding, all information can later be exactly recovered by the decoder from the encoded bitstream. Lossless coding relies on information theory [6], which has introduced a concept called information entropy to measure the amount of information contained in a random source of messages and offered a number of effective ways of representing messages more effectively while still losslessly. All lossless coding methods based on information entropy are collectively called entropy coding. The two commonly used entropy coding algorithms are Huffman coding and arithmetic coding; both algorithms can be made context adaptive to improve their encoding performance. Besides entropy coding, some other lossless coding algorithms have also been developed. The two most important ones are dictionary coding and run-length coding. Dictionary coding compresses a message by building a static or dynamic dictionary of strings and replacing an input message by a sequence of dictionary entries. Run-length coding represents a message as a sequence of (run,level) pairs, which can effectively compress the message if the distribution of “run” has a long tail. Both methods have their roots in information theory, but normally they are not classified as entropy coding. Many lossless coding algorithms, including Huffman coding and arithmetic coding, belong to variable-length coding (VLC) because they encode an input symbol into a variable number of bits.

The last step of the encoding process is postprocessing. It mainly aims at collecting the output from the previous step and assembling the final bitstream. In some applications, the final bitstream may contain several quality layers that should be encoded in such a way that separated decoding is possible. When there are multiple streams involved, for example, audio and video streams of a TV program or the left- and right-eye video streams of a stereoscopic video, a container is needed to hold the multiple streams and some mechanism is needed to guarantee the synchronization among them. Different from previous steps, this last step does not involve any compression technique.

In addition to the above four steps, there is another optional step called predictive coding. It can be done together with the first two steps, which explains its multiple connections with other parts of the encoding process. As its name implies, the goal of predictive coding is to predict not-yet-encoded part from already-encoded data to reduce the amount of information for further encoding. If the prediction error (also called residual data) has a more skewed distribution than the original data, which is the normal case, information theory guarantees that the compression efficiency will be higher. For instance, for image and video coding based on DCT transform, the first transform coefficient (called DC coefficient) of each block can be predicted from the previous block’s DC coefficient with a fairly high accuracy. This prediction can also happen in temporal domain, where the motion of objects in the input video is estimated and the obtained motion vectors are encoded as part of the final bitstream. Predictive coding is particularly important for video coding because consecutive frames are often highly correlated in both spatial and temporal domains.

Different image and video coding schemes can be developed by combining different techniques for different steps of the whole encoding/decoding process. Various image and video coding standards have been established, among which JPEG and MPEG-1/2/4 are the most successful standards. The development of image and video standards on one hand takes advantage of existing technologies, but on the other hands also promotes new research by offering a platform for testing different kinds of new technologies. As a matter of fact, the latest image and video coding standards, such as JPEG2000 [7], JPEG-XR [8], MPEG-4 AVC/H.264 [9], and SMPTE VC-1 [10], represent the state of the art of the field.

Generally speaking, a multimedia coding standard defines a syntax format of the encoded bitstream and a method of decoding an encoded bitstream to reconstruct the original multimedia data (that is, the input of the encoder) with an acceptable perceptual quality. Multimedia coding standards are designed to offer balanced solutions to the following goals simultaneously: good perceptual quality, high compression efficiency, and low computational complexity of the codec. In addition, some other factors are often taken into account to enhance the applicability of the designed standard, which include flexibility to support diverse applications, backward compatibility with old standards, scalability, resilience against transmission errors, and so forth. Because of the limited space, existing image and video coding standards are not discussed in detail; this chapter aims to describe perceptual encryption schemes working with those standards in a more general sense.

14.2.2 Modern Cryptography and Cryptanalysis

Modern cryptography is the science of securing digital systems, which is often considered as a subfield of computer science although it does have a strong link to information theory (thus communications in general) and mathematics (especially number theory, finite field, and combinatorics) [11], [12]. Traditionally, cryptography is mainly about data encryption, but nowadays more complicated cryptographic systems, such as cryptographic hash functions, digital signatures, and security protocols, have been developed. This chapter is mainly focused on data encryption. The nature of modern cryptography implies that cryptanalysis, the study on how to break existing cryptographic systems, is extremely important and plays a key role in the development of any secure systems. In some sense, it can be said that modern cryptography is built on top of cryptanalysis; or that cryptology is composed of two subfields: cryptography and cryptanalysis, one is about designing secure systems and the other about breaking them. This subsection introduces only some very basic concepts and terms of modern cryptography and tries to avoid discussing any ad hoc designs and attacks; as these topics are widely discussed in References [11] and [12].

An encryption system is also called an encipher, and a decryption system is called a decipher. When there is no need to differentiate an encipher and a decipher or the same system can be used for both encryption and decryption, such a system can be simply called a cipher or a cryptosystem.¹ The plain message taken as the input of an encipher (and the output of a decipher) is called a plaintext. Similarly, the encrypted message as the output of an encipher (and the input of a decipher) is called a ciphertext. Denoting the plaintext and the ciphertext by P and C, respectively, the encryption procedure of an encipher can be described by

C=EKe(P),⁢(14.1)

where K_e is the encryption key and E (·) is the encryption function implemented by the encipher. Similarly, the decryption procedure of a decipher can be described by

P=DKd(C),⁢(14.2)

where K_d is the decryption key and D (·) is the decryption function implemented by the decipher. If an encipher and a decipher are concatenated by feeding the ciphertext C to the decipher, the following is obtained:

P=DKd(EKe(P)).⁢(14.3)

Basically, the decryption function D (·) can be considered as the inverse of the encryption function E (·). Figure 14.2 illustrates how an encipher and a decipher can work together to allow secure transmission of data over a public insecure channel.

1The term cryptosystem actually can be used to represent more cryptographic systems beyond ciphers, but in many application scenarios it is a synonym of cipher.

Note that if the encryption and decryption keys should be made public it is possible to have two different kinds of ciphers. When both keys have to be kept secret, the cipher is called a private-key cipher or a symmetric cipher. The second name comes from the fact that for most private-key ciphers the encryption key and the decryption key are identical, or the decryption key can be derived from the encryption key so that they can be considered as identical. The main problem with private-key ciphers is the key management issue. Since the keys have to be kept secret, they have to be transmitted to both the sender and the receiver in advance via a secret channel. For n users in a community, communications between any of these users will require secure transmission of n (n − 1)/2 keys, which can become difficult or impossible to manage when n becomes large. This problem can be solved if only the decryption key needs to be kept secret but the encryption key can be made public, thus leading to the so-called public-key cipher or asymmetric cipher. Apparently, for an n-user community only n encryption keys need to be published to support secure communications between any two users. Normally, public-key ciphers are much slower than private-key ciphers due to their special properties, but they can be combined in such a way that a public-key cipher is used to implement the key management process of a private-key cipher. This chapter is more concerned about private-key ciphers because encryption of multimedia data is always performed by a private-key cipher.

Private-key ciphers can be further divided according to their encryption structure into block ciphers and stream ciphers. Block ciphers encrypt the plaintext block by block in the same manner, meaning that the same plaintext block will lead to the same ciphertext block independent of the position of the block in the whole plaintext/ciphertext. In contrast, stream ciphers encrypt the plaintext based on a pseudo-random sequence (called a keystream) generated under the control of the encryption key, thus allowing producing different ciphertext blocks for two identical plaintext blocks at different positions. Over the years, many different block ciphers and stream ciphers have been proposed, among which Advanced Encryption Standard (AES) [13] was the most widely used block cipher and (Alleged) Rivest Cipher 4 (RC4) the most widely used stream cipher [14] at the time this chapter was written.

While block ciphers are memoryless compared with stream ciphers, they can be made to behave in a way similar to a stream cipher by running it under different modes of operation. There are many different modes of operations, among which the naive way of running a block cipher is called the electronic code book (ECB) mode. By introducing ciphertext feedback, that is, revising the encryption procedure as follows:

Ci=E(Pi⊕Ci-1),⁢(14.4)

the so-called cipher block chaining (CBC) mode is obtained, where C₀ is a given initial vector (IV) and ⊕ denotes XOR operation. There are also other modes that can transform a block cipher into a stream cipher, thus making block ciphers a foundation of building stream ciphers. This can be done, for example, by repeatedly encrypting an initial vector, a counter, or a combination of both. One of the reasons why more advanced modes of operation are needed is a security problem with the ECB mode, as shown in Figure 14.3.

Following a well-known principle proposed in References [15] and [16], the security of a cipher should rely solely on the decryption key K_d, but not about secrecy of the algorithm itself. This is widely accepted in modern cryptography because an obscured algorithm can be easily reverse engineered by crackers or exposed by insiders. Keeping this principle in mind, an upper bound of the security of a cipher is defined by the size of the key space, that is, the number of all possible keys. This is because the simplest attack on a cipher is to exhaustively try every possible key and see which one can give a meaningful output. Such a naive attack is called brute-force attack in cryptanalysis. Considering the computational power of today’s computers and distributed computing, the key space is required to be as large as 2¹²⁸ or even 2²⁵⁶. In addition to brute force attack, there are also attacks defined according to the capability of the attack to access/choose plaintexts and/or ciphertexts:

• ciphertext-only attack: the attacker can access the ciphertexts only;

• known-plaintext attack: the attacker has access to some plaintexts and the corresponding ciphertexts;

• chosen-plaintext attack: the attacker can choose plaintexts and get the corresponding ciphertexts; and

• chosen-ciphertext attack: the attacker can choose ciphertexts and get the corresponding plaintexts.

The ciphertext-only attack represents the most common attacking scenario because the ciphertext is supposed to be transmitted through a public channel (otherwise, data encryption is not needed at all). The known-plaintext attack is often possible in practice because many files have fixed headers and the contents of encrypted messages may be guessed in some cases (or simply exposed by the sender or receiver intentionally or unintentionally²). Chosen-plaintext and chosen-ciphertext attacks become possible when the attacker gets temporary access to the encipher and the decipher (but not the key), respectively. Note that the goal of a ciphertext-only attack is usually the plaintext, but the other attacks normally target the decryption key.

2For instance, a receiver may decide to reveal a secret message once he/she believes that the value of the message itself has expired. But the exposure of this message may be useful for an attacker to accumulate information for breaking future messages encrypted with the same key.

Besides the above attacks, there are also many other attacks defined in different contexts. For instance, when a cipher is implemented in a real product, the energy and/or the time consumed on encrypting different plaintexts with different encryption keys may differ. Such differences may be captured by an eavesdropper to derive useful information about the plaintext and the key, if one has access to the environment of the encryption machine. Such implementation-oriented attacks are called side channel attacks and they have been proved very effective in breaking many real implementations of theoretically secure ciphers.

14.3.1 Threat Model

A typical multimedia encryption system consists of an encoder-encipher (equipped with an encryption key K_e) and a decoder-decipher (equipped with a decryption key K_d), as shown in Figure 14.4. The input data may be already compressed in some applications, in such cases a decoder (or a partial decoder) is needed to decode the data first before encoding and encryption. A decoder without access to the decryption key K_d may try to decode the encoded-encrypted multimedia data. It is also possible that some multimedia processing units are inserted between the encoder-encipher and the decoder-decipher to perform some additional manipulation on encoded-encrypted multimedia data, such as watermark embedding and detection, re-encryption, filtering, bitrate re-control, re-packetization, transcoding, and so on. In most cases, these in-between multimedia processing units have no access to the encryption key nor to the decryption key. They may even be encryption-agnostic, that is, unaware whether the bitstream has been encrypted. On the other hand, the encoder-encipher often has no clue which multimedia processing operations may happen after the encoded-encrypted data are sent out to the transmission channel.

The threat model of such a multimedia encryption system is as follows. An attacker may appear at any point after the encoder-encipher and may have access to a compliant decoder, but no access to the decryption key. The attacker is assumed to know all the details of the encryption algorithm and of the key management process. The attacker may have access to a database of multimedia data of the same type as the plaintext. The main goal of an attacker will be to break the decryption key, or to completely/partially recover perceptual information in the encrypted multimedia data. In other words, both ciphertext-only attacks, known/chosen-plaintext attacks, and chosen-ciphertext attacks are possible threats. Side channel attacks may also be possible if the attacker has access to the ambience of the encoder-encipher or the decoder-decipher.

14.3.2 Three Approaches to Multimedia Encryption

According to where encryption is added into a multimedia encoder, there are three possible approaches to realize multimedia encryption, as shown in Figure 14.5: encryption before encoding, encryption after encoding, and joint encryption-encoding. The third approach also covers the case when an encoded multimedia file/bitstream is (partially) decoded and a joint process of encryption and (partial) re-encoding is performed to generate the encrypted multimedia file/bitstream. Note that the (partial) decoding and re-encoding processes may not involve decompression and/or re-compression. One typical example is sign bit encryption, in which only partial decompression is involved in the decoder at the encipher side, since the encrypted sign bits can be directly put back into their original places in the input (already encoded) multimedia data.

The first two approaches are much simpler due to their independence of the encoding process. Unfortunately, they suffer from some nontrivial drawbacks that cannot be easily overcome without introducing dependence on the encoding process. The following briefly discusses the three approaches of multimedia encryption and explains why the third approach, that is, joint encryption-encoding, is of greater interest.

14.4.1 Definition and Performance Evaluation

Perceptual encryption is selective multimedia encryption where only a specific amount of perceptual information is encrypted by encryption. Equivalently, perceptual encryption can be seen as intended quality degradation by the means of encryption but the degraded quality can be recovered by a decryption key. The nature of perceptual encryption leaves part of the data untouched and allows a decoder to recover unencrypted perceptual information without accessing to the decryption key. Ideally, a fully scalable perceptual encryption should allow the perceptual quality to be downgraded under the control of a continuous quality factor q ∈ [0, 1]. When q = 1, the maximum amount of perceptual information is encrypted and the perceptual quality becomes minimal; when q = 0, the minimum amount of perceptual information is encrypted and the perceptual quality is maximized; when 0 < q < 1, part of the perceptual information is encrypted and the perceptual quality is downgraded accordingly. Figure 14.6 shows an illustrative view of a perceptual encryption scheme.

Given the above definition of perceptual encryption, the following facts about the control factor q should be noted:

• Despite extensive research on visual quality assessment (VQA), there still does not exist a well-accepted objective measure of visual quality that can replace an average human observer’s subjective quality assessment. Therefore, the control factor q is generally chosen to represent a rough measure of the quality degradation.

• While the relationship between the control factor q and the quality degradation cannot be linear (due to the lack of a proper VQA metric), the monotonicity should be maintained, meaning that a larger q should statistically correspond to a higher level of quality degradation. This implies that a selective format-compliant encryption scheme is not necessarily a perceptual encryption scheme unless the selective encryption can downgrade the perceptual quality in a monotonic manner under the control of a factor q.

• In most cases, the control factor q is defined as a parameter of the encryption scheme that have a direct relationship with the visual quality of the encrypted image/video, for example, the percentage of syntax elements encrypted.

• For digital videos, the quality degradations of different frames may be different, so the control factor represents the average quality of all frames.

• Depending on applications, the control factor may have different levels of granularity, so there are may be only a limited number of possible values of q.

• Multiple control factors may be used to have a finer control of different aspects of visual quality degradation.

As in general multimedia encryption schemes, there are multiple performance factors to be considered when evaluating the performance of a perceptual encryption scheme. Among all the performance factors, main attention is focused on security since all the other factors are not unique for perceptual encryption. There are two unique features making the security of perceptual encryption schemes essentially different from other kinds of multimedia encryption schemes: i) the existence of two separate sets of data (one encrypted and one unencrypted) containing perceptual information; and ii) the unencrypted data are decodeable to an attacker who does not know the key. The need of maintaining some level of perceptual quality immediately leads to two different levels of security that should be considered:

• cryptographical security – measurement of security against cryptographical attacks that try to recovery the plaintext of the encrypted data;

• perceptual security – measurement of security against perceptual attacks that try to recover as much perceptual information as possible out of the unencrypted data without any attempt of breaking the underlying encryption algorithm.

Although most perceptual encryption schemes are based on cryptographically strong ciphers, the cryptographical security may not be guaranteed because the interface between the cipher and the image/video coding system may create new insecure points so that the cipher fails. Perceptual security is a unique concept for perceptual encryption and covers perceptual attacks that can recover perceptual information from the encrypted data in noncryptographical means. Perceptual attacks are by definition indifferent of any details about how the encryption algorithm works, which means that they are more general and can also be generalized to applications where some data are missing, corrupted, or distorted due to other reasons (for example, transmission errors and noise, and/or intended or unintended data removal, truncation, and manipulation).

In the following, a brief survey of perceptual encryption schemes for digital images and videos is provided, then the two levels of security are separately discussed with greater detail.

14.4.2 Perceptual Encryption Schemes

This subsection does not attempt to give a complete coverage of all schemes in the literature; it aims at highlighting the main relevant techniques and some representative schemes that can better demonstrate interesting features of perceptual encryption schemes in general. Most perceptual encryption schemes are conceptually simple and straightforward, and the main technical question is what data should be selected for encryption given a specific image and coding standard as the carrier of the multimedia data. Despite the conceptual simplicity of many perceptual encryption, performance evaluation of them especially security analysis is non-trivial, as will be shown later. Throughout the subsection, it is assumed that perceptual encryption is implemented by adopting a cryptographically strong cipher like AES or RC4 unless otherwise stated.

14.4.3 Cryptographical Security

The following discusses cryptographical security from the perspectives of different attacks. If one can break the cipher used to encrypt the selected part of the image and video data, then the whole perceptual encryption scheme will collapse. While normally a cryptographically strong cipher like AES or RC4 is used to guarantee security, the way how such a cipher is applied to image and video data can make a difference. This becomes more obvious when the cipher has to be applied in a way different from its original design. For instance, some perceptual encryption schemes are based on random permutations of selected syntax elements of an image/video bitstream. A stream cipher is usually used to produce a pseudo-random permutation map, which is then applied to achieve the effect of encryption. Here, the use of the stream cipher differs from the normal usage in cryptography, where the keystream is used to mask the plaintext (normally via XOR or modular addition) rather than to shuffle their positions.

14.4.4 Perceptual Security

For perceptual security, one does not care about any detail of the encryption algorithm, but cares about how to recover a better quality out of the unencrypted data. This means that all attacks in this category fit into the class of ciphertext-only attacks.

From an attacker’s point of view, the problem to be solved can be described as follows:

• What is available – the unencrypted visual data and the known semantics of such data (for example, the encrypted data are all DC coefficients or sign bits).

• What is a successful attack – if one can recover the plaintext image/video with a quality (statistically) better than that of the ciphertext (that is, the one defined by the quality control factor q).

• What are the constraints – both the time complexity and the space complexity should be sufficiently low to make the attack practical even for relatively large images and videos.

The above points are self-explanatory, but the last one needs a bit more discussion. How high the time complexity, that is, how slow an attack, is allowed depends on the application. If the attacker wants to crack a live broadcast program, the attack will have to be fast enough to catch the frame rate, meaning that the attack should be done in O (10) milliseconds. If the attacker just wants to crack what is stored on a hard disk or a DVD disc, then it is possible to run the attack for hours or even days. When an attacker has access to a botnet or a supercomputer, the above requirement can be relaxed at an order of O (10⁶). Note that an attack running in polynomial time (in the so-called P complexity class) may not be practical at all if either the hidden constant factor or the fixed exponent is too large. The requirement on the space complexity is normally tighter because the storage available to an attacker is largely fixed and does not grow over time.

All attacks in the perceptual security category follow the same basic approach; namely, replace the encrypted data by an estimate from the available unencrypted data/information and then run the decoder to get an approximate edition of the plaintext image/video. The more accurate the estimate is, the better the recovered quality and the more successful the attack will be. Since this approach is very similar to error concealment in multimedia coding, these attacks are collectively called error-concealment attacks (ECAs) [34]. Some researchers also use the term concealment attacks or replacement attacks [59].

Error-concealment attacks have been so far the most successful attacks on perceptual encryption and some very promising results have been obtained in recent years on DCT-based encryption. It is also likely that these attacks can be easily generalized to other transforms, including DWT. Some error-concealment attacks also have more profound implications on image and video coding (compression) in general. Such attacks are discussed in more detail in the next section.

Since the performance of an error-concealment attack has to be judged against the quality defined by the ciphertext, measuring the perceptual information for the comparative purposes becomes an important task. The golden standard of perceptual information measurement is subjective evaluation by human experts. However, subjective quality assessment is very time-consuming and costly, so researchers have proposed various objective visual quality assessment (VQA) metrics for digital images and videos [66], [67]. Traditionally, image and video coding community has been using a simple metric called peak signal-to-noise ratio (PSNR). For an M × N image or video frame I* = {I* (i, j)} and its distorted version I = {I (i, j)}, where 1 ≤ i ≤ M and 1 ≤ j ≤ N, PSNR is defined as follows:

PSNR=10⋅log10Imax2∑​i=1M∑​j=1N(I(i,j)−I*(i,j))2/(MN),⁢(14.5)

where the denominator, called mean square error (MSE), is also widely used in objective quality assessment. Unfortunately, neither PSNR nor MSE matches subjective quality very well [67, Figure 1.1], so more advanced VQA metrics, such as the structural similarity index (SSIM) [68], visual information fidelity (VIF) [69], and visual signal-to-noise ratio (VSNR) [70], have been proposed. Although VQA metrics are commonly tested on various test databases to demonstrate their good correlation with subjective data collected from human observers, a recent comprehensive comparative study has shown that none of existing VQA metrics consistently outperforms all others [71].

Some encryption-oriented VQA metrics have also been proposed to obtain more accurate measurements on encrypted images and videos. Such metrics include the luminance similarity score (LSS) and edge similarity score (ESS) [72], neighborhood similarity [73], similarity of local entropy [74], and a number of metrics based on image histogram and radial Fourier spectrum [75]. Basically speaking, these encryption-oriented VQA metrics focus more on a specific aspect of the overall visual quality that is supposed to be influenced by perceptual encryption in a more scalable way (meaning that no abrupt change will happen as the quality factor q changes slightly). The main drawback of all the existing encryption-oriented VQA metrics is the lack of performance evaluation against subjective quality. This makes it difficult to judge whether there exist the best metric and if so, which one it is.

14.5.1 Naive Attacks

The naive ECA is the simplest ECA in the sense that it just tries to replace all encrypted syntax elements of the same kind by a fixed value according to their semantic meanings. This can be more easily explained by how such an attack works with DC encryption of DCT-transformed images. While one has no idea what the DC coefficients are, it is known that they have a range determined by the valid range of pixel values. For N × N DCT and eight-bit grayscale images, this range is [0, 255N]. By setting all DC coefficients to any value in this valid range, for example, 0 or 255N/2, and then scale the dynamic range of the resultant image to [0, 255], an image with an overall quality better than the ciphertext can be produced. Figure 14.9 shows the result on the test image Cameraman. One can see that the image obtained via the naive ECA obviously has a higher visual quality than the ciphertext image. Using PSNR as the objective VQA metric, the same conclusion can be reached: the ciphertext image has PSNR = 11.5883 dB, whereas the image recovered from this ciphertext by the naive ECA has PSNR = 13.0428 dB. The naive ECA is the widely acknowledged attack. Most perceptual encryption schemes were tested against this attack to validate its perceptual security.

14.5.2 Local Constraints-Based Attacks

In the naive ECA, all encrypted syntax elements of the same kind are replaced by the same fixed value. Such a global replacement is not necessarily (generally not) the best choice. By considering a small local window around each encrypted syntax element, some local constraints with a tighter range than the global range may be found. Once again, this can be best demonstrated by the case of DC encryption. Since the two-dimensional DCT is performed blockwise, the local window can be naturally selected as the block each encrypted DC coefficient lies in. In this case, Property 14.1 gives an interesting local constraint of the unknown DC coefficients defined by the known AC coefficients.

The local constraint defines a valid range of the DC coefficient of the block containing it, which is a proper subset of the global valid range with high probability. Therefore, if the midpoint of the tighter range is used to replace the encrypted DC coefficient, the ECA attack should give results closer to the plaintexts with a higher visual quality. Figure 14.10 shows the result of such an advanced ECA applied to the ciphertext in Figure 14.9a. Comparing Figure 14.10 with Figure 14.9b reveals that the visual quality is further improved, which is also reflected by higher PSNR, that is, 13.8837 dB.

This advanced ECA on DC coefficients can also be generalized to any encrypted DCT coefficients. When more than one DCT coefficient are encrypted in each block, the local constraints have to be calculated jointly by checking all possible values of the encrypted DCT coefficients and taking those values that do not produce invalid pixel values.

14.5.3 Prior Statistics-Based Attacks

If the attacker can have access to an image database that represents the statistics of the plaintext image of interest, then it will be more beneficial to replace the encrypted syntax elements by the means of the most likely values rather than the midpoints of the valid ranges. Such an advanced ECA was demonstrated in Reference [76] on an image encryption scheme based on two-dimensional discrete prolate spheroidal sequences (DPSS) [77]. This image encryption is not a real perceptual encryption scheme, but the basic idea behind the statistics-based ECA demonstrated in Reference [76] can be generalized to any perceptual encryption scheme. To be more exact, the advanced ECA exploits statistics of the ratios between the encrypted DPSS transform coefficients and the most significant unencrypted coefficient. Then, the statistics are used to derive a better estimate of each encrypted DPSS transform coefficient. Compared with the results of the naive ECA, the performance of the statistics-based ECA is significantly better, as shown in Figure 14.11.

14.5.4 DC Encryption Attacks Using Coefficient Recovery

All previously introduced ECAs are relatively simple and the recovered image can hardly reach a PSNR value larger than twenty. In Reference [38], the authors proposed a method that can boost the performance of an advanced ECA to a level far more than all previous ECAs. This attack was aimed at DC encryption of DCT-transformed images/videos. To facilitate the following discussion, this method is named here as USO by taking the initials of the three authors. The USO method is based on Property 14.1 of digital images and Property 14.2 of natural images.

The two properties play two different roles and can work together to design an iterative ECA. Namely, Property 14.2 allows the attacker to estimate the DC coefficient of a block relative to its neighbor blocks by minimizing the pixel difference along the block boundaries, and Property 14.1 applies a tighter range of the DC coefficient on each block so that the intersection of all the relative DC coefficients can give a rough estimate of the global brightness of the image. After an attacker has the global brightness and all the relative DC coefficients, approximations of absolute values of the encrypted DC coefficients can immediately be obtained. Note that the estimation process of the relative DC coefficients involves a scanning process, which starts from a corner block of the image and then continues through the whole image toward the opposite corner to derive all the relative DC coefficients one after the other. It is obvious that such a scanning process suffers from error propagations. To mitigate this problem, Reference [38] proposed to have four different scans starting from the four different corners and then average the results to get a less noisy result. After the whole process, the recovered plaintext image may still have pixel values out of the valid range, then a scaling or truncating operation is applied to remove those invalid pixel values. Figure 14.12 shows the result of the USO attack on the test image Cameraman. As it can be seen, the perceptual quality of the recovered image is boosted a lot. The PSNR value becomes 19.6975 dB, much higher compared to that of the naive ECA and the simple advanced ECA described in Sections 14.5.1 and 14.5.2. For some other images, such as Lena, the PSNR can go beyond 20 dB.

14.5.5 DC Encryption Attacks via Underflow/Overflow Rate Minimization

While the USO method works largely well, it sometimes suffers from a relatively low accuracy of the DC estimation when the error propagation is not under control so that many pixel values go out of the valid range. For the averaged result from the four scans shown in Figure 1 of Reference [78], the pixel values range in the interval [−88.6, 303.0]. By scaling the range to [0, 255], the finally recovered image has a low PSNR value of 14.3 dB.

To further reduce the error propagation effect, Reference [78] proposed to apply Property 14.1 during the relative DC estimation process rather than after it. To be more exact, during the scanning process, the underflowed and overflowed pixel values are checked for each block. Once such underflows and/or overflows happens, the whole block is shifted toward the valid range of pixel values until all underflowed and overflowed pixel values disappear. The modified DC estimation process makes the final result more sensitive to the global brightness, or equivalently the DC coefficient of the first block in each scan. Reference [78] also proposed an iterative process to get a more accurate estimate of the first DC coefficient, which is based on an interesting observation that roughly holds for various natural images: the more accurate the estimate of the first DC coefficient, the less frequently underflowed and overflowed pixel values appear in each block. In other words, the underflow/overflow rate is a unimodal function (with only one global minimum) of the estimate of the first DC coefficient. Based on this observation, the authors proposed to search all possible values of the first DC coefficients and take the one with the minimum under-flow/overflow rate as the estimate. Since this rate is a unimodal function, the searching process can be done effectively with a time complexity of O (M_B log₂(N(t_max − t_min)/Δ)). This method was named as underflow/overflow rate minimization (FRM).

Because the iterative process of searching for the optimal value of the first DC coefficient, the FRM method is generally slower than the USO method, but it outperforms the USO method significantly according to experimental results carried out on 200 test images. The authors tested the performance improvement measured in ten different VQA metrics, and the FRM method was proved to be consistently better than the USO method. Figure 14.13 shows an example of using the FRM and USO methods for recovering a test image Cameraman; it can be seen that the FRM produces a result with an obviously better visual quality. For a detailed comparison between the USO and FRM methods, the readers are referred to Reference [78, Sec. 3.3].

14.5.6 Optimization-Based Approach to DCT Encryption Attacks

Both the USO and FRM methods can break DC encryption only. They cannot be easily generalized to more general cases, such as AC encryption or combination of DC and AC encryption, because Properties 14.1 and 14.2 describe the relationship between one unknown coefficient and all other known coefficients. The question about where an generalized attack exists was answered by in Reference [79] affirmatively.

This time the whole ECA is modeled as a discrete optimization problem and solved as a linear program. For the ECA breaking DC encryption, the discrete optimization problem can be described as follows:

minimize f({x(i,j)}0≤i,j≤N−1)⁢(14.7)

subject to x = A · y, x_min ≤ x(i, j) ≤ x_max, and y (k,l) = y^* (k,l) for all AC coefficients. The terms x (i, j) and y (k,l) are variables denoting the value of pixel (i, j) and the DCT coefficient (k,l), respectively. The term A represents the linear relationship between pixel values and DCT coefficients defined by the blockwise two-dimensional DCT, and y^*(k,l) represents the ground truth of y (k,l). Note that the last constraint fixes all AC coefficients to their ground truths while the DC coefficient y (0,0) remains as a variable. In principle, the objective function f can be any convex function to allow a polynomial-time optimization algorithm. However, considering Property 14.2, the authors chose the objective function to be Σ_{{(i,j),(i′, j′)}}|x(i, j) − x (i′, j′)|, where the sum ranges over all pairs of neighboring pixels. This choice makes the optimization problem a linear one, which can be solved efficiently by using the linear programming (LP) technique [80]. The linearization is done by introducing variables h_{i,j,i′,j′} into the model as follows:

minimize ∑​hi,j,i′,j′⁢(14.8)

subject to x (i, j) − x(i′, j′) ≤ h_{i,j,i′,j′}, x (i′, j′) − x (i, j) ≤ h_{i,j,i′,j′}, and the constraints related to Equation 14.7. In the above model, the variable h_{i,j,i′,j′} will be tight at |x (i, j) − x (i′, j′)| for the optimum solution.

With the above optimization model, the generalization from DC encryption to DCT encryption is straightforward: one can simply fix y (k,l) = y ^*(k,l) for known DCT coefficients while keeping all unknown variables in their natural ranges. The generalized model maintains the linearity, so it can still be solved via linear programming. Given an n × m image and U unknowns in each of B blocks with dimensions N × N, the optimization model contains 2nm − (n + m) variables h and UB variables y while all other unknowns can be determined by these key variables in a presolve step. The average time complexity and space complexity of the optimization problem were experimentally verified to be O (n²m²U) and O(nmU), respectively.

The performance of the linear programming-based ECA works nearly perfectly for breaking DC encryption. For the test image Cameraman, the recovered image reaches a PSNR value of 26.4866 dB (see Figure 14.14). For the DC encryption case, the linear programming-based method outperforms the FRM method statistically with a significant margin (see Figure 2 of Reference [79]). What is more surprising, even when more than ten most significant DCT coefficients are encrypted, the linear programming-based ECA can still recover the plaintext with relatively high perceptual quality for some images. Figure 14.15 shows an example on the test image Cameraman when sixteen most significant DCT coefficients are missing from each block.

The big success of the optimization-based ECA is rather unexpected, especially when it turned out that a relatively simple optimization model can work so perfectly. The results not only reveal that DCT encryption largely failed, but also lead to some more profound implications on image and video coding. It raises the question about how much information should be encoded for a DCT-based image and video coding scheme. In addition, some digital watermarking and data hiding schemes can also be handled by the same optimization model if they use some AC coefficients to hide the watermarks/hidden information.