Digital Images Multiresolution Encryption

by Benoît Macq and Jean-Jacques Quisquater

ABSTRACT

Digital image transmissions often require compression, secrecy and transparency. We have developed a multiresolution encryption algorithm, where the low-resolution information of the images (i.e. their icons) remains unencrypted.

INTRODUCTION

Nowadays conditional access systems for digital image transmission or storage are a necessity. Among their range of applications one can point out:

• pay-TV,

• medical images for transmission on LAN or for database,

• confidential videoconferences and

• secret facsimile transmissions.

Digital images can be considered as a given number of bits and an encryption could be achieved by directly applying a conventional method, like the Data Encryption Standard (DES). The DES is a one-to-one mapping of blocks of 64 bits defined by a 56-bit secret key. This method would, however, have two major drawbacks:

• First, the image is not a random amount of data: the pixels are connected by a correlation process which could offer a possible path for breaking the encryption. More precisely, the unknown key could be retrieved by a method giving the maximum correlation for the data at the output of the decoding.

• The output of the DES is pseudo-random and no compression can be achieved after the encryption, since the apparent correlation has disappeared.

Applying a method like the DES after a compression coding of the image seems attractive since the output of the coding is more or less random and already encoded at the required bit rate. However, this method is also not satisfactory, for three reasons:

• A user could intend to protect his images independently from the nature of the transmission channel, i.e. independently from the compression algorithm in use in this channel.

• Compression techniques are very sensitive to transmission errors and are specifically protected. Generally, a specific framing and synchronization is added to the compressed data. A DES encryption would decrease dramatically the efficiency of this protection.

• In many applications, the encryption has to be somewhat transparent:
  - A broadcaster of pay-TV does not always intend to prevent unauthorized receivers from receiving his program, but rather intends to promote a contract with non-paying watchers.

  - The access to the icons of a secret image bank could also remain unprotected.

These observations have led us to propose a new image encryption technique. In our technique the encryption is achieved before the compression (see Figure 1). We propose a multiresolution scheme which produces a "compressible" image with a certain level of transparency.

SPECIFICATIONS FOR IMAGE CRYPTOSYSTEMS

Our cryptosystem can be modeled as in Figure 1. In this figure, the encryption function is isolated from the other components of the transmission system. Our algorithm is based on the following specifications:

• lossless: The encryption process has to be reversible, with perfect reconstruction of the image, DK(EK(I))=I.

• multiresolution: The algorithm has to be somewhat transparent, encoding only the details above a given resolution. Furthermore, it allows conditional access for resolution: e.g., one could provide High- Definition TV with free access to the TV signal. More formally, the two first properties are related to two factors:
  • - the transparency, which is maximum when D(E(I)=I;

  • - the opacity, which is minimum when E(I)=I and maximum when E(I) is totally scrambled. So the variable opacity of the cryptosystem will allow the user of the system to decide on the degree of unrecognizability of the image.

• compressible: The compression of the encrypted image has to remain efficient, i.e., the encrypted image must have similar statistical properties to a real picture, i.e., the compressions of I and E(I) for a given rate have to lead to similar coding distortions.

• secure: The cryptosystem has to be resistant to any known attack. Attacks specific to high redundant messages like images are to be taken into account. Notice that there are some connections between the secure and the compressible conditions, since if the encrypted image is highly correlated it is highly compressible and also difficult to attack by maximizing the correlation.

• low-complexity: The algorithm has to be based on low-cost operations.

THE MULTIRESOLUTION ENCRYPTION ALGORITHM

The core of the system is a one-to-one lossless multiresolution mapping of images based on a new operator that we define as the L-H mapping. The L-H mapping maps a pair of pixels (x(i-1), x(i)) into two numbers (xl, xh), xl being close to the half-sum of the pixels, xh being close to the pixel half-difference. The signals xh and xg can be interpreted as the approximation and the detail of the pixel pair. This new mapping is depicted in Figure 2 and can be easily implemented by using some logical gates.

The L-H mapping is applied first in the horizontal direction and then in the vertical direction, only on the horizontal approximation signal. The process is applied recursively on the approximation signal according to the decomposition pattern shown in Figure 3. A corresponding image is shown in Figure 4. We denote this decomposition as the Lossless Multiresolution Transform (LMT). A permutation of lines or columns after the LMT, followed by the corresponding inverse LMT, allows us to generate an encrypted image from which the original picture can be reconstructed.

Let us give some details on the process. We denote by xi[j] the value of the pixel at position (i,j) of the resulting image after a LMT. For the sake of simplicity, we assume that the number of pixels in a column or a row is a power of 2, that is, 2[ l] for some l: these pixels are numbered from 0 to 2[l] -- 1. We denote by xi a column of pixels at position i and by x[j] a row of pixels at position j. A permutation of columns (resp. rows) of pixels is a reversible transformation from any subset of columns (resp. rows) into itself. We denote by PK a permutation indexed by K. This value K is related to the set of chosen permutations and is called the key when used in a cryptographic scheme. A set of consecutive columns (resp. rows) in the range [i1,...,i2], i1 [[sterling]] i2, is denoted by xi1,i2 (resp. x [i1,i2]): the corresponding permutation of these columns (resp. rows) is denoted by xPK(i1i2) (resp. x[PK(i1,i2)]). Using L to denote the LMT, we have

     L[-1](PK(L(I))) = EK(I)

   and

     DK(X) = L[-1](PK[-1](L(X)))

The opacity of the encryption can be modulated by the number of L-H decomposition. In Figure 3, we have a 3-level decomposition.

An encrypted image is shown in Figure 5. In order to increase the compressibility of the scheme, we could perform conditional permutations of the values; the detail values are permutated by data in the same context (we permute xh values having the same range for the corresponding xg value and neighborhood).

FUTHER ISSUES

The method proposed in this paper is preliminary. Further issues are related to the improvements (and how to measure them) of the algorithm properties (compressibility, security, etc.).

REFERENCES

The use of cryptographic scrambling for protecting handwritten signatures and signal television is very old; see the standard reference [3] for instance, and the two relevant old papers [4] and [5].

A recent book about cryptology is [6].

[1] Proceedings of the First International Seminar on Conditional Access for Audiovisual Services, Rennes, France, June 1990.

[2] Takeshi Kimura, Masafumi Saito and Seichi Namba, "Some studies on conditional access for DBS television service--Algorithms of permutation scrambling and an experimental decoder with smart card" in [1], pp. 107--122.

[3] David Kahn, The codebreakers. Macmillan Publishing Co., New York, 1967, pp. 827--836.

[4] Signature scrambler foils forgery, Management and Business Automation, Sept. 1960, p. 53.

[5] Don Kirk, Engineering report on encoding television signals, Jerrold Electronics Corporation, Philadelphia, 1955.

[6] Gus J. Simmons (Editor) Contemporary cryptology. The science of information integrity, IEEE Press, 1992.

BIOGRAPHIES

Benoît Macq received the `Ingénieur Civil Electricien' and the `Docteur en Sciences Appliquées' degrees from the Université Catholique de Louvain (UCL), in 1984 and 1989, respectively. He has worked on telecommunication planning in the Tractionnel society in 1985, and on video coding in the Telecommunication Laboratory of the UCL from 1986 to 1990. From 1990 to 1991, he was with the Philips Research Laboratory Belgium. He is now permanent researcher of the Belgian NSF (`Chercheur Qualifié' du FNRS), at the Telecommunication Laboratory of the UCL.

        Laboratoire de Telecommunications
        2, Place du Levant
        B-1348 Louvain-la-Neuve
        BELGIUM
        e-mail:  Macq@tele.ucl.ac.be

Jean-Jacques Quisquater received his MS in applied mathematical engineering (1970) from the Université Catholique de Louvain and his PhD in computer science (1987) from the University of Paris (Orsay). Formerly, he was project leader and senior scientist in information security and cryptology at Philips Research Laboratory Belgium. Since 1992, he has been an associate professor at the UCL. He also teaches at the Ecole Normale Supérieure (Paris) and at the University of Namur.

        Laboratoire de Microélectronique
        3, Place du Levant
        B-1348 Louvain-la-Neuve
        BELGIUM
        e-mail  : quisquater@dice.ucl.ac.be

---