Cryptography arises from the need to ensure confidentiality, integrity and availability of information. Consequently, cryptographic systems are designed and implemented, with the aim of transforming meaningful information into unintelligible data through a hiding mechanism that uses secret cipher keys and allows exclusive access of authorized users to the original information by a decryption process. On the other hand, cryptanalysis seeks to detect vulnerabilities in cryptosystems in order to retrieve or supplant information [29].

There are two types of cryptosystems: symmetric and asymmetric. In symmetric type, the same key is used at both ends of a communication channel, while in asymmetric type each user has a public and a private key [29]. Algorithms based on CAs or chaos that have been proposed for image and video encryption are usually of symmetric type.

In this work, density of periodic points, topological transitivity, and sensitive dependence on initial conditions of the combination of CAs pseudo-random behavior among with additional operations of integer numbers are used to induce the confusion and diffusion properties that should be part of a cryptographic method [30-32].

The confusion property seeks to ensure that the cryptosystem evolution in time is independent of the encrypted text and the cipher key, that is, that the relationship between text and password is sufficiently complex to guarantee security. On the other hand, the diffusion property seeks that small changes in the original text should generate completely different encrypted text [30].

The kind of CAs formulated in this paper are named Composite Cellular Automata (CCAs). They are one- dimensional and ECA-based, since their transition rules are a combination of elementary rules. They are called composite rules, with which new possible behaviors emerge that cannot be obtained independently through ECAs.

Formally, a composite rule F is given by expression in eq. (4), where f _i is an elementary rule and r is the number of elementary rules that constitute F.

In turn, each f _i defines the state for a set of r cells in the CCA from 𝑖 to 𝑖+𝑟−1 through the expressions in eq. (5). The number of bits that represent a composite rule is 8 x r because an elementary rule is identified by eight bits.

Fig. 4 shows a 6-cell periodic boundaries CCA that evolves with a composite rule with r = 2.

Figure 4 Source: The Authors.

Utilization of CCAs has several advantages: a greater number of rules, the possibility of establishing new reversible rules, and an efficiency that resembles ECAs homogeneity.

A reversible CCA evolves with a composite reversible rule, that consists exclusively of elementary reversible rules. The number of cells of a CCA must be multiple of r to ensure that every f_i on F is used the same number of times.

For simplicity purposes, alternative notation presented in Table 1 is used to identify any reversible composite rule as a string of r characters, each one has six possible values (‘A’, ‘A̅’, ‘B’, ‘B̅’, ‘C’, ‘C̅’). Nevertheless, not all possible combinations of these values identify a reversible composite rule. In the proposed method, the r value is equal to 8.

In the CCAs environment, new NSRR arise, that involve displacement in the same direction, labeled as Composite Shift Rules (CSR), and formed exclusively of the elementary rules ‘A’ and ‘A̅’, or ‘C’ and ‘C̅’. Fig. 5 shows the behavior of a CCA with initial state ‘11100000’ that evolves four times with rule ‘AAAAAA̅AA’ and other four with rule ‘CCCCC̅CCC’ to return to its initial state.

Figure 5 Source: The Authors.

In addition, reversible rules with capability to change the order of bits of an initial state arise, labeled as Bit Position Change Rules (BPCR). Fig. 6 shows the behavior of a CCA with initial state ‘00101010’ that evolves four times with composite reversible rule ‘BCABCABB’. Note that this BPCR is also an SRR. Nevertheless, there exist NSRR type BPCRs, as in the case of rules ‘BC̅ABC̅ABB’ and ‘BCA̅BCA̅BB’.

Figure 6 Source: The Authors.

Finally, Identity-Complement Rules (ICR) arise, they are composed exclusively of the elementary rules ‘B’ and ‘B̅’, and they are also SRR.

In Fig. 7, reversible composite rule classification performed in this work is shown.

Figure 7 Source: The Authors.

The number of composite reversible rules N _CRR for a given r value is calculated using eq. (6)-(9), where N _BPCR , N _CSR and N _ICR represent the number of BPCR, CSR and ICR type rules, respectively.

Note that N _CRR grows considerably as the r value increases.

From possible composite reversible rules with r value equal to 8, sixteen pairs were selected with the purpose of establish a different 4-bit sequence identifier for each one, they are listed in Table 2. The first eight pairs are CSR, and the eight remaining pairs are BPCR. The rules on the first column (rule set 1) are used in encryption, and the remaining (rule set 2) in decryption, that is, in original information recovery.

As a strategy for the selection of eight first pairs of rules (numbered from 0 to 7 in Table 2), entropy values of the 256 possible 8-bit strings, finding 70 different combinations with entropy value 1, that is, strings which have four zeros and four ones in any order. From this string set, a group of eight was selected with a Hamming distance equal to four or six [35]. With these strings, eight CSR were constructed, first four are composed of ‘A’ and ‘A̅’; and remaining four are composed of ‘C’ and ‘C̅’, being the number 1 replaced by ‘A’ or ‘C’ and the number 0 replaced by ‘A̅’ or ‘C̅’.

Table 2

Source: The Authors.

Similarly, as a strategy for the selection of rest pairs of rules (numbered from 8 to 15 in Table 2), the set of 15 possible 8-bit strings with exactly two pairs of consecutive ones are considered because their entropy is also 1, and a group of eight with a Hamming distance equal to two, four or six was selected from this set. With these strings, eight BPCR were constructed, being each pair of ones replaced by the elementary rule pair ‘CA’, ‘C̅A’, ‘C̅A̅’ or ‘CA̅’, and each zero is replaced by ‘B’ or ‘B̅’.

In the encryption process, the sender stores the original video with hidden RoIs, the isolated cipher RoIs and their location in the video frames. Thus, a receiver can recover the encrypted video completely through the stored data and the correct keys.

The encryption method is tested with a straightforward mechanism for RoI detection, that consider perceptible motion patterns in video as RoIs. An initial frame is considered as background, and the next frames are compared with initial frame to determine the pixels with changed value. If a group of pixels with changed value is connected and has a size greater or equal than 256 pixels, it will be enclosed by a rectangle and considered as a RoI. If two RoIs are 16 pixels away or less, they are grouped into an only RoI. Finally, each RoI dimensions are rounded to the closest multiple of 8 in order to allow a correct encryption process. This process was implemented through a routine in Matlab, using Image Processing Toolbox and Image Acquisition Toolbox libraries.

Starting with an LCA from a predetermined image (such as example in Fig. 3) an initial sequence of 1027 consecutive bits is extracted to form a 1027 columns matrix along with the LCA bits from a RoI, repeating, if required, bits from initial sequence to fill all columns. Subsequently, XOR operation is performed with each column entries, obtaining a 1027-bit sequence that will be the key to encrypt every RoI in a frame.

The first 1023 bits in the key are named P_s0, and the remaining four bits in its decimal representation define the value N ₀ that indicates the iteration number to evolve P_s0 with elementary rule 30.

The encryption proposal consists of eight steps that are applied on each video frame.

Step 1: RoIs detection, extraction and replacement by black rectangles in the original frame for storage.

Step 2: Transpose RoIs which height is greater than their width.

Step 3: A RoI in the frame is selected for key generation as explained in Section 3.5. RoIs in different frames are encrypted with different keys.

Step 4: Let S _ECA be an ECA initial state, and N the number of evolutions with elementary rule 30, the 1023-bit sequence ps is calculated by expression in eq. (10), assigning to S _ECA and N the previously defined values of ps₀ and N ₀ respectively.

Step 5: Bit in position 1024 from the key is appended to ps and read from right to left in 4-bit segments. Decimal representation of each segment is obtained adding one, avoiding the appearing of zeros, forming a list of 256 integer numbers in the interval from 1 to 16 called multiplier sequence ms.

Step 6: Composite rule identifiers sequence R, expressed by eq. (11) is obtained from algorithm 1, assuming that ps and ms have periodic boundary conditions, where Ns, previously specified in eq. (3), is the maximum number of CCAs in the LCA that is obtained with the RoI of the largest width or height in the frame, and R_i is a 4-bit string associated to a composite rule in Table 2.

In this step, rule 30 (eq. 10) is used to evolve ps, that along with multiplication and modulo of integer numbers in ms contribute to guarantee key sensitivity. The values in ms are used in the algorithm 1 to define numbers for the ps evolution with elementary rule 30 and determine the js values that acts as a displacement number for ps. Note that the bits that constitute R are 4-bit sequences coming from a specific ps state.

Step 7: Evolution of LCAs obtained from each RoI. Each row that constitutes the layers in the LCA is considered the initial state of an CCA which corresponding evolution rule is identified by R _i . For encryption, the bits that form each LCA are reordered in three different ways:

By rows for each layer.

One evolution is performed after each rearrangement, thus, every LCA evolves three times. For decryption, each LCA evolve before each rearrangement, which order is inverted.

Source:

Step 8: Obtain encrypted RoIs from evolved LCAs. Transpose the previously transposed RoIs in Step 2 to recover their initial dimensions.

The sender stores the cipher RoIs, and the receiver decrypt them to completely recover each frame of video. Decryption uses the second rule set in Table 2 to perform the same process except for steps 1 and 3, because the decryption key for original video recovery is the same encryption key.

In order to show that proposed method is functional, robust and effective, a surveillance video segment coming from a security camera in the Universidad Distrital Francisco José de Caldas from Bogotá was encrypted. Fig. 8 shows a video frame, RoIs extraction and hiding, encryption and recovery of original image results.

Figure 8 Source: The Authors.

Executions of this algorithm were performed on a computer with 8GB RAM and processor Intel Core i3 in the Matlab 2018a platform. Encryption and decryption times in for different sizes of image are shown in Table 3.

Table 3

Source: The Authors.

Proposed algorithm depends on image dimensions, that is, the number of CCAs that evolve in Step 7 and their length. Therefore, its computational complexity is 𝑂(3×𝑀×𝑁).

In Fig. 10, histograms of original and cipher images from Fig. 9 are presented, proving that frequency distribution of pixel values in cipher images is uniform as expected.

Figure 10 Source: The Authors.

For a grayscale image I, the entropy H(I) measures the pixel distribution values, which optimal values for a cipher image tends to 8 [13, 30]. It is defined by eq. (12).

Where x_i is the i _th gray value of I,p(x_i) is the occurrence probability of x _i and L is the number of pixels that constitute the image. For color images, this conception is applied on each RGB channel. Entropy values of original and cipher images in Fig. 9 are listed in Table 4, proving that encrypted images by proposed method present high randomness.

Table 4

Source: The Authors.

Obtained entropy values for cipher images are comparable to the values obtained in [1, 3, 5-13, 16, 17]. In addition, entropy value of cameraman cipher image in [13] is 7.988, less than the obtained with this method.

Let E₁ and E₂ denote two images which result of encrypt two almost identical images with one-pixel difference, the Number of Pixel Changed Rate (NPCR) is the number of pixels at the same location in E₁ and E₂ with different values, and it is defined by eq. (13)-(14).

The Unified Averaged Change Intensity (UACI) is the average absolute value of the difference between each pair of pixels at the same location in E₁ and and E₂, it is defined by eq. (15).

For two random images, NPCR and UACI optimal values are nearly 99.6094% and nearly 33.4635%, respectively [36].

Let I₁ denote an image from Fig. 9, I₂ equal to I₁ except for a modified pixel value. E₁ and E₂ are the images obtained by encrypt I₁ and I₂,respectively. Minimum, maximum and average obtained values of NPCR and UACI in 10 executions are presented in Table 5, which are close to the optimal values, proving that the proposed method resists differential attacks.

Table 5.NPCR

Source: The Authors.

The correlation coefficient for an image is a decimal value between -1 and 1 defined by eq. (16)-(19) and it is calculated from a random adjacent pixel sample in different directions. In plain images, the correlation coefficient is close to 1, and the expected value in cipher images is close to 0 [13].

In order to measure the existent correlation between adjacent pixels in images from Fig. 9(g) and Fig. 9(h), a set of 1000 random pairs of pixels in horizontal, vertical and diagonal position were considered for each RGB channel.

Obtained values are grouped in Table 6, showing an almost null correlation value in every channel of the cipher image.

Table 6

Source: The Authors.

Fig. 11 shows the horizontal, vertical and diagonal values of adjacent pixels in the green channel for the original and the cipher image.

Figure 11 Source: The Authors.

A feature of secure cryptosystems is key sensitivity, that means, a slight change in the cipher key must produce a completely different cipher result [30].

In order to prove key sensitivity from the sender side, the image from Fig. 9(c) was encrypted using two keys K₁ and K₂ with one-bit difference, obtaining the results shown in Fig. 12. The UACI and NPCR values related to the images in Fig. 12 (b) and (c) are 99.61% and 33.42% respectively, that implies that these cipher images are completely different.

Figure 12 Source: The Authors.

In order to prove key sensitivity from the receiver side, K₁ are K₂ are used to decrypt the image from Fig. 12(b), obtaining the results shown in Fig. 13.

Figure 13 Source: The Authors.

Note that original image is completely recovered by using K₁, but it is not possible to retrieve encrypted information by using K₂

It is remarked that every sensitivity test shows similar results, independently of the position occupied by the difference bit between K ₁ and K ₂ . Therefore, this method presents key sensitivity.

The results presented in this section expose that the proposed method resists brute force attacks, correlation attacks, differential attacks, chosen-plaintext attacks according to performance results in encryption of Fig. 9(a), and known-plaintext attacks as an effect of the strategy in Section 3.3, which frustrates the possibility of obtain the rules in R without having the cipher key.

Although there are few encryption works focused on surveillance videos using the guideline proposed in this work, it was possible to calculate a collection of performance measures reported independently in several references, highlighting that the obtained measures are comparable with those in [1,3,5-13,15-17]. That implies high security of the proposed method and makes this work a significant contribution in the fields of image and video encryption.