A Tabu Search Algorithm for General Threshold Visual Cryptography Schemes

Across the network, communication of critical and sensitive information like Quick Response (QR) images, medical images, medical reports, financial documents, and military maps. Secret Image's (SI) definition is given as real-time images that have confidential information. It is essential to consider security-related issues as digital services have swiftly and greatly progressed in this digital communication age. Especially in India, a Digital India is being made a reality through 462 million Indians endeavors. There is communication across the network of millions of information in the form of videos, audio, real-time images, and text. It signifies that security is, of course, a critical concern for this whole idea. At the time of SI communication, consideration of the SI's integrity, quality, and security is paramount. There is extensive utilization [1] of encryption/decryption and information hiding techniques for the SI's protection.

Human beings are inclined to preserve and protect important things, information or messages from potential loss or misuse. A lock and key system is used for storing items in safe places. Yet, there are two ways in which these items can be stolen. When the key is found, it could open to steal the items. Also, the system could be physically broken if the key is not found. A certain combinational key system has been developed to make the key more secure. This combinational key is shared between different people, or it is split into pieces (shares) that are kept at diverse locations. Must bring this distributed information back together, and key identification must occur to open the lock. At times, it is necessary to transfer the information from one place to another securely. It is quite necessary [2] to transmit this information through the preservation of its privacy.

The science of utilizing mathematics for data's encryption and decryption to keep the messages secure by modifying the data in an intelligible form (the plain text) into an unintelligible form (the ciphertext) is referred to as cryptography. Origins of the term cryptography have come from the Greek word "kryptós", which means "hidden", and from the word "gràphin", which means "writing". Hence, "hidden writing" is the cryptography term's correct meaning. This cryptosystem comprises the key, the ciphertext, the decryption algorithm, the encryption algorithm, and the plaintext. The plaintext will comprise of data or message that is readable and also normal. There is a key's utilization by encryption for the conversion of this plaintext into its ciphertext. The ciphertext is encrypted through the application of an encryption key on the plaintext. The process of decryption will retrieve the plaintext from its ciphertext. The cryptosystem (the cipher system) is controlled by a key that is only known by either the sender or the receiver. Such data are made secure with this very powerful cryptography. Additionally, cryptanalysts can successfully break ciphers to acquire plaintext [3] from analysis of the cipher's contents.

As a security technique, Visual Cryptography (VC) will perform image encryption such that there is visual decryption of the original Image. This technique will randomly expand a secret image onto multiple visual key images. A share is a term used for each visual key Image. These visual key images are generally printed on transparent sheets, and there is visual decoding of the secret Image when there is an overlapping of a qualified subset of the keys. An example of VC with two visual keys is displayed in Figure 1. No information related to the secret Image is extracted when there is only a single individual visual key in VC. Even though there is the secret Image's display after the overlapping of multiple visual keys, there is no direct observation of each key from the overlapped outcome. The secret Image, as well as the visual keys, are safeguarded as being invisible to unauthorized users [4] for diverse security applications.

1.png

Figure 1. Example of VC: (a) visual key 1, (b) visual key 2, (c) Visually decoded secret image when the two visual keys printed on transparent sheets are overlapped

The VC utilizes two clear-cut pictures. While the first picture comprises random or noisy pixels, the second picture comprises secret data. The secret data’s recovery from encrypted pictures is essentially tough. For the data’s revelation, it is necessary to utilize the layers and the transparent pictures. Printing of the two layers onto a single transparent sheet is the simplest VC implementation. The VS’s benefit is its ability to furnish computation problems when decoding and re-establish the secret image through stacking activity. With this property, the VC is specifically valuable for the low computation strategy [5]. Presentation of the VC technique was done in 1994 by Naor and Shamir. This secret imparting scheme offers greater security for a binary image. During the human vision, this scheme’s legitimate deciphering is another benefit. VC strategies have numerous levels. For example, Colour images, gray images, and binary images are utilized for the VC’s implementation. As per Naor and Shamir, an edge Visual Cryptography Scheme (VCS) can encode a provided secret picture into n shadow pictures (shares), in which any k or a greater amount of them can visually recover the secret image, but any or a lesser amount of them are unable to recover the secret image [6]. This scheme misuses the human visual framework for reading a secret message from some overlapping shares function; it will overcome the traditional cryptography’s requirement for complex computations. Naor and Shamir gave the VC’s elemental model for application in diverse applications with its incorporation of visual authentication, data hiding, etc. However, the model concept is why the complete restriction of these applications to the binary images’ utilization. There is a drastic decrease in VC’s applicability as binary images are generally restricted to text message representations.

For VCs, this work has proposed the ProbVSS and TS algorithm. The organization of the investigation is provided in the subsequent sections. Associated works in literature have been overviewed in Section Two. Diverse, utilized methods have been detailed in Section Three. The experimentations have been discussed in Section Four, and this work is concluded in Section Five.

The difference between black’s white pixel densities and the recovered images’ white reconstruction areas constitute the basis of the contract’s classical definition. In traditional VCS, contrast is often utilized for the measurement of the recovered images’ display quality. There is a discussion about the ProbVSS and TS algorithm in this section.

3.1 Probabilistic Visual Secret Sharing (ProbVSS) Scheme

B₀ and B₁ are the two collections of n´m Boolean matrices which are used for a (k;n) VSS Scheme’s representation. When a white (resp. black) pixel is shared, there is random selection of a single row of the Boolean matrix B₀ (resp. B₁) to a relative shadow by the dealer. The gray level of the m subpixels in every one of the n shadows is the chosen matrix’s definition. The validity of a VSS Scheme is dependent on the fulfillment [17] of the following conditions:

1. $H(V) \leq d-\alpha m($ resp. $(H(V) \geq d)$ is fulfilled by the OR"-ed $\mathrm{V}$ of any $\mathrm{k}$ of the $\mathrm{n}$ rows for any $\mathrm{S}$ in $B_{0}\left(\right.$ resp. $\left.B_{1}\right)$.

2. For any subset $\left\{i_{1} ; i_{2} ; \ldots i_{q}\right\}$ of $\{1 ; 2 \ldots ; n\}$ with (q<k) the two collections of $q \times m$ matrices which are gained from the restriction of each $n \times m$ matrix in $B_{0}$ to $B_{1}$, to rows $\left\{i_{1} ; i_{2} ; \ldots i_{q}\right\}$ cannot be discerned as they comprise of similar matrices with similar frequencies.

Contrast is the term used for the first condition whereas, security is the term used for the second condition. Because of the security condition, if it does not have greater than k shadows, it would not be able to gain any information related to the shared secret.

The basic (2, 2) VSS scheme will stack two shadows for the shared secret’s recovery such that the “black” will now be 2B0W while the “white” will now be 1B1W, in which, $x B y W$ will indicate that it has utilized x black sub pixels and y white sub-pixels for an original pixel’s representation. Since each pixel’s representation is given as 1B1W sub-pixels, the scheme is unable to obtain any information from any single shadow.

White set $C_{0}$ that contain $n_{\lambda}$ a matrix, and black set $C_{1}$ that contains $n_{\gamma} n \times 1$ matrix are the two sets which provide the $(k ; n)$ ProbVSS scheme's representation. When a white (resp. black) pixel is shared, the dealer will initially pick one $(n \times 1)$ column matrix in $C_{0}$ (resp. $\left.C_{1}\right)$ randomly, and later, will randomly pick a single row of this column matrix to a relative shadow. The colour level of pixel in every one of the n shadows is defined by this chosen matrix. Validity of a ProbVSS Scheme is based on the fulfilment of the below conditions:

1. The " $O R$ " value of any $k$ -tuple column vector $V$ will be $L(V)$ for these $n_{\lambda}\left(\operatorname{resp} . n_{\gamma}\right)$ matrices in the set $C_{0}\left(\right.$ resp. $\left.C_{1}\right) .$ A set $\lambda$ (resp. $\gamma$ ) is formed from these values of every matrices.

2. $p_{0} \geq p_{T H}$, and $p_{1} \leq p_{T H}-\alpha$ are satisfied by the two sets $\lambda$ and $\gamma$, wherein, $p_{0}$ and $p_{1}$ are the appearance probabilities of the " 0 " (white color) in the respective sets $\lambda$ and $\gamma$.

3. $p_{0}$ and $p_{1}$ will be similar for any subset $\left\{i_{1} ; i_{2} ; \ldots ; i_{q}\right\}$ of $\{1 ; 2 ; \ldots ; n\}$ with $(q<k)$.

While the first two conditions are referred to as contrast, the third condition is referred to as condition security. Based on the earlier-mentioned definition, as matrices in C₀ and C₁ are (n×1) matrices, the Pixel Expansion will also be one. However, as the traditional VSS scheme’s B₀ and B₁ are (n×m) matrices, the Pixel Expansion will be m.

3.2 Tabu Search (TS) Algorithm

To maximize the contrast of recovered images, subject to density-balance constraints, Tabu Search is used to optimize this.  Given k, n, and the blackness requirement, the proposed optimization-based threshold VCS model determines a set of choice probabilities. An extensive range of challenging combinatorial optimization problems can be resolved with the powerful solution technique known as TS. This local search technique is capable of avoidance of a local minimum or a cycle’s repetition of a cycle through its combination with a variety of approaches. Glover gave the first introduction of the TS which exhibited huge effectivity in the resolution of tough optimization problems. TS will utilize an evaluation function for retaining the solution, which can enhance the f value (which is picked from a set of neighboring solutions N(s)) such that there is the existing solution’s [18] replacement with a chosen best neighbor at every iteration.

The TS’s primary characterization is given as a Tabu List T (memory) that is made up of the last solutions visited but does not provide the possibility of a solution which has already been accepted and stored in the Tabu List. Long-term memory and short-term memory are the TS’s two utilized types of memory. An aspersion criterion is utilized for the long-term memory’s execution. This type of memory will permit a Tabu move’s performance despite its Tabu classification. While short-term memory is associated with a Tabu List structure, it does contain a list of temporary forbidden moves such that there is avoidance of visit to an already explored solution.

The following points form the basis [19] for the TS:

•   Utilization of the flexible memory structures (short, medium, and long term) that facilitates the complete exploration of the evaluation criteria as well as the search history.

•   A control mechanism that is reliant on alternation between the search process’s conditions, which constrict (restriction Tabu), and the conditions which liberate (aspiration criterion).

•   Incorporation of the search’s strategies of intensification and diversification:

• The medium-term memory’s utilization and strengthening of the search in the regions of the newly found best solutions are done by the intensification strategy.

• The long-term memory’s utilization and searching of the new regions are done by the diversification strategy.

3.3 General Algorithm of TS

TS’s general algorithm is presented below:

1) Acquisition of an initial solution (initialization).

2) Creation of a list of candidates’ movements.

3) The best candidate’s selection. Tabu restrictions and the aspiration criteria form the basis of this selection.

This will offer an alternative that would not be registered only if it is found to be better in comparison to the earlier solution.

4) The stopping criterion’s application.

2.png

Figure 2. Flowchart for Tabu search method

Continue: Modification of the candidates of eligibility (Tabu restriction and aspiration criterion). Move back to 2.

Stop: Proceed towards the strategies of intensification and diversification.

Figure 2 illustrates the TS method’s flowchart.