Authentication Based on the Image Encryption using Delaunay Triangulation and Catalan Objects

This paper presents the authentication method using the Delaunay triangulation incremental algorithm and the Catalan objects. The proposed method is a combination of computational geometry and cryptography. This method presents a new step towards encoding the triangle coordinates using the Catalan-key. We provided specific suggestions for the application of this method in the authentication for bank clients by the image encryption. Client authentication verification is performed by asking the client to enter the (x,y) coordinate values of randomly selected indices of an array. If the entered coordinates match the index values in the banking system array, then the transaction or other operation is approved. If the matching fails, it means that we have an unidentified person who has followed the whole process and wants to break into the banking system. There are many advantages arising from a scenario for the user authentication by the assigned Catalan object and the stack permutation method. Also, we provided concrete examples for the Delaunay encryption of image with an authentication scenario and experimental results for the proposed method.


Introduction
The modern electronic age and the devices that accompany it, bring many opportunities. One of their main capabilities is to store data and protect them from unauthorized access. The science behind data protection methods is called cryptography. Along with cryptography, cryptanalysis is also being developed and always strives to find out the secret message received by one of the cryptographic methods. At its core, cryptography is based on mathematical models of algorithms.
In these days of the modern technology, there is a growing need to create secure, i.e., reliable user authentication systems. Special emphasis is placed on banking transactions and systems that are often the target of hacker attacks. This paper will deal with Delaunay triangulation and image encryption using the Catalan object as the basic method of authentication. A scenario that includes a potential attacker will be presented. Implementation of operations of such models of algorithms over valuable (publicly available) information is called encryption. Through this process, we obtain modified information that is not understandable. The reverse process, when the ciphered text again receives intelligible information, is called decryption. One of the indispensable input parameters in the chosen encryption algorithm is a Cryptographic key. It is a binary string of 0 and 1 whose length depends on the cryptographic algorithm used.
The main contribution of this paper is a novel encryption method, stated using the Delaunay Triangulation incremental algorithm and the Catalan objects. The proposed method is a combination of computational geometry and cryptography. This method presents a new step towards encoding the triangle coordinates using the Catalan-key. We provided specific suggestions for the application of this method in the authentication for bank clients by the image encryption. There are many advantages arising from a scenario for the user authentication by the assigned Catalan object and the stack permutation method.
The rest of the paper is organized as follows. Similar research from the field of computational geometry application in cryptography is discussed and surveyed in the second section. A special focus is given to some applications of the combinatorial problems based on the Catalan objects (such as Lattice Path combinatorics, Stack permutations, Balanced Parentheses, and Ballot problem) in the file encryption and decryption. The third section discusses the basic properties of the Voronoi -Delaunay triangulation of the image. Examples for the encryption by Delaunay triangulation of image and authentication scenario are given in the fourth section. The fifth section contains experimental results and a detailed analysis of the encryption method. Concluding remarks and suggestions for further research are given in the sixth section.

Review of Related Research
Authenticating through the means of encrypted images is not a new idea. In [1], Luan Guangyu proposed a new encryption scheme and authentication of asymmetric images based on equal decay modules in the Fresnel transform domain. The benefits of this scheme are multiple; first, the open-spectrum Fresnel is rarely sampled. Then, the rare presentation of the Fresnel spectrum is divided into two complexly valuable masks with the same decay modulus, both of which are required for decryption and authentication. Lin Yuan in [2] developed an authentication scheme through image, based on the encryption of double images and partial phase decryption in the fractional Fourier transform domain. Only part of the information of the encrypted result phase is stored for the decryption, while the rest of the phase and all other amplitude information is discarded. In [3], Huaqian Yang proposed fast encryption of image authentication. In particular, a key hash function was introduced to generate a 128-bit hash value from an ordinary image and secret keys. The hash value plays a role of encryption and decryption keys, while the secret hash keys are used to authenticate decrypted images.
When it comes to the Delaunay triangulation application, there are many ideas of authentication by fingerprint image triangulation. In this regard, in the paper [4], Zanobya N. Khan developed the idea of separation of palm lines. Then, the endpoints of these lines are determined and a link between them is created using Delaunay triangulation to generate a distinct topological structure for each palm imprint. After that, different geometric and quantitative characteristics are distinguished from the triangles of Delaunay triangulation that aids the identification of different individuals. In [5], a Delaunay triangulation technique for fingerprint-based image was developed on the grounds of matching to avoid authentication mistake, caused by incorrect entries and OTP (One-Time Password) submissions to ensure maximum security in authentication verification. This triangulation method allows unobstructed access to authorized users at the ATMs even with modified fingerprints and also improves security.
We will state some applications of the combinatorial problems based on the Catalan objects (such as Lattice Path combinatorics, Stack permutations, Balanced Parentheses, and Ballot problem) in the file encryption and decryption. The paper [6] analyzes the properties of the Catalan numbers and their relation to the Lattice Path combinatorial problem in cryptography, i.e., in the files and plain text encryption and decryption. A procedure for the application of one computational geometry algorithm in the process of generating hidden cryptographic keys from the 3D image segment was presented in [7]. In this paper, a combination of polygon triangulations, Catalan numbers and cryptography is made. The paper [8] examines the possibilities of applying appropriate combinatorial problems (Ballot Problem, Stack permutations, and Balanced Parentheses) in the files and plain text encryption and decryption. Catalan numbers play an important role in data hiding and steganography. The purpose of paper [9] is related to investigating the properties of the Catalan numbers and their possible application in the procedure of data hiding in a text, more specifically in the area of steganography. The authors of [10] provided some straightforward information, such as how much spurious and missing minutiae can influence on a Delaunay triangulation. Their research is supported by the results of experiments carried out on two common variants of the Delaunay triangulation in four different cases. The experimental results show that Delaunay triangulation based structures are more sensitive to missing minutiae than spurious minutiae. In the paper [11] authors proposed a 3D Delaunay triangulation based fingerprint authentication system as an improvement to the authentication performance without adding extra sensor data. From the experimental results, it is observed that the 3D Delaunay triangulation based fingerprint authentication system outperforms the 2D based system in terms of matching performance by using the same feature representation.

Voronoi -Delaunay Triangulation of Images
The authentication can be based on the Delaunay triangulation of a selected image and coloring of triangles through the process of triangulation. Thus triangulated and colored image should be triangulated again in such a manner that the coordinates of the triangle vertices are coded by the Catalan key. Definition 3.1. By Catalan key we assume a Catalan object having balanced parenthesis property, i.e., it is a bit string with exactly n 1 bits and n 0 bits where, in every prefix, the number of 1's is greater or equal to the number of 0's.
We will state some properties of the Delaunay triangulation: uniqueness and independence from the starting point, the formed triangles are in the shape of equilateral triangles, there is no other point in the circle of triangles (circle property), the convex hull is triangulated, the segment obtained from the closest pair of points is in triangulation, the segment derived from the point and its closest points is the side of the triangle in the triangulation.
Let P ={p 1 , p 2 ,…, p n } be a set of points in the plane. These points are called centers or sites. Delaunay triangulation of set P is a unique triangulation where no triangle circumscribed circle contains sites in its interior. On the other hand, the dual of Delaunay triangulation is Voronoi diagram. Voronoi diagram for some set of sites also partitions a plane into the regions, where every region consists of all points closer to a site than to any other site. Now, let us explain the term of the edges of a Delaunay diagram. For the edge ̅̅̅̅̅̅ we say it belongs to the Delaunay diagram if there is a circle C ij to which p i and p j belong and no other site lies inside the circle, and the center of the circle C ij lies on the edge of the Voronoi diagram defined with V(p i ) and V(p j ). The three points p i , p j ,p k are vertices of the Delaunay diagram of the set P if and only if the circle through the points p i , p j and p k does not contain other points from P within the circle. The following definition of Delaunay triangulation arises from this statement.

Definition 3.2. For a triangulation of a set of points in the plane P, we say it is a Delaunay triangulation if and only if the circumscribed circle of any triangle in does not contain the points from P inside the circle.
Thus defined triangulation is also called Legal Delaunay triangulation. Figure 1 presents Delaunay triangulation. It can be noticed that the legal triangulations ∆p i p j p m and ∆p i p j p k are formed inside the circles C(p i p j p m ) and C(p i p j p k ). If it happens that some point (vertex) suddenly appears, as in our case the vertex p l , then these triangulations would be illegal Delaunay triangulations.  Figure 2 gives an example of a Delaunay triangulated image with colored triangles. The coding scenario will be explained later. In order to more clearly describe the process of Delaunay image triangulation, let us first explain the process of obtaining Delaunay triangulation.  If we want to legalize them it is necessary to remove the closed line segment ̅̅̅̅̅̅̅ and to form a new one, i.e. ̅̅̅̅̅̅. The process of legalization of the edges is defined by the Algorithm 3.1 [12]. In our method, we randomly select a set of points P within the given image, providing that their coordinates contained in vectors (X,Y) are within the given image resolution.
In general, locating the points begins by forming a large triangle ∆p -1 p -2 p -3 containing all points of the set P. It is necessary that these points are far enough away so they do not interfere with the Delaunay triangulation of set P. These points are chosen on the principle p -1 = (3M,0), p -2 = (0,3M) and p -3 = (-3M,-3M), where M is the maximal absolute value among the coordinates of points in P. This ensures that P is contained within the triangle ∆p -1 p -2 p -3 .
The number of triangles created by the Delaunay triangulation algorithm is at most 9n + 1, and the time complexity of this algorithm is O(n log n) using O(n) memory locations. This legalization process best describes the incremental Delaunay triangulation construction algorithm [12] which is also the basis of our presented image encryption model. Suppose now that the set of sites P is given within the image of the desired resolution. It is necessary to determine for each image point which site is closest to it.
The area of the point p i is called the Voronoi cell of p i and denoted by V(p i ). In Figure 3, we present the Voronoi diagram that is dual to the Delaunay diagram (triangulation). It is important to note that the nodes of the Voronoi diagram are in fact the centers of the circles at which the mentioned Delaunay triangles already lie.

The Encryption by Delaunay Triangulation of Image and Authentication Scenario
Our image encryption method is based on the application of the Delaunay triangulation incremental algorithm on encrypting the (x,y) coordinates of points in P. The vertex coordinates encryption process is based on the use of Stack permutation method for binary representations of Catalan objects. As known, Catalan numbers C n appear in many combinatorial problems counting so called Catalan objects, and they are given by formula [13]: Particularly, for chosen n, C n is the total number of bit strings containing exactly n '1' bits and n '0' bits and satisfying balanced parenthesis property. Such a bit string, as presented in Definition 3.1, is termed as Catalan key. A simple example of generating C 3 = 5 Catalan keys for n = 3 is shown in Figure 4.  In the process of encryption of the site coordinates in the Delaunay triangles, we use the Stack permutation method of chosen Catalan key.
1) If the current bit in the Catalan key is '1', then push the current bit of string, which is about to be encoded.
2) If the current bit in the Catalan key is '0', then pop one bit from the stack and send it to the output.   In Example 4.1, the coordinate x has an integer value. Generally, its value can also be a real number. In that case, we encode integer and fraction part separately. Let us, now, explain the image encryption algorithm. The input elements are randomly selected sites, that is, their (x,y) coordinates. We start with initial triangulation containing the triangle ∆p -1 p -2 p -3 . This is, in fact, an auxiliary triangle from which we begin and later it loses on its importance because we do not need it. In other words, its vertices are removed as well as all the sides of the triangles contained therein.
In the next step, the initial triangle of the image ∆p i p j p k is formed. It should be emphasized that the (x,y) coordinates of each vertex of this triangle, as well as all the subsequent ones that will be created, are in the range of the image resolution. This is a pre-condition needed in order to assure a correct triangulation of the image. The process of forming of this triangle ends after 3 count loops.
In each count, the coordinates of the vertices p r are added to the array K which we need in the further (x,y) coordinates encryption process. After forming an initial triangle in the process of triangulation, the function size() is called to find a pixel with (x,y) coordinates located at the gravity center of the triangle (the center pixel of the triangle).
The way this function finds the pixel mentioned is represented by the following standard formula for calculating coordinates of the gravity center of a triangle: It should be noted that function size() is called for each newly created triangle. Then, the RGB function, coloring the triangle with the color of the center pixel, is called. It should be emphasized that for the 4th and every subsequent entry of a random vertex p r , one can expect two cases about its positions with respect to the triangle ∆p i p j p k and within the "large" triangle ∆p -1 p -2 p -3 . In the first case, p r is inside the triangle ∆p i p j p k . In the other case, p r is on the edge of ∆p i p j p k .
In the first case, three lines will be drawn from the vertex p r to the adjacent sites, while in the second case two lines will be drawn from p r to the opposite vertices p l and p k (it is supposed here vertex p l occurred outside the triangle ∆p i p j p k ). In case that a vertex p r appears outside the triangle ∆p i p j p k , then a triangle is formed by drawing lines towards all vertices visible from the vertex p r . In each of these steps, Algorithm 3.1 is called to verify each edge of an adjacent triangle with respect to p r , taking care that the Delaunay triangulation condition is satisfied.  After the edges have been legalized, that is, the process of input of the triangle vertices is completed; the vertices and edges of the large triangle ∆p -1 p -2 p -3 are removed because they were needed only to create the initial image triangulation. In the following step, as a return value, we get triangulated image , that is, is the set of all triangles obtained by the triangulation process. Now, it should be emphasized that (triangulated image) is in fact a set of triangles that is a subset of the set, where ∆p -1 p -2 p -3 and incident edges are removed. In this way, the portions of the image outside the convex hull (i.e., outside the boundary edges of ) are removed. Now, the elements of the array K, that is, the (x,y) coordinate values of the vertices, are converted into their binary equivalents. This is the operating condition of the Stack Permutation) method. Then, we choose corresponding Catalan key and, using Stack Permutation method, encrypt the coordinates and put them into the array K s .
From now on, the image triangulation process is repeated as in the previous steps, except that the tags are changed ("s" added) due to clarity. The decryption process, i.e., returning the image to its original triangulated form, is obtained so that the encrypted coordinates of the vertices change place with the original (originally chosen at random) in methods called due to decryption. In this way, the originally triangulated image is obtained.
In Figure 7, one can clearly see the difference between the original and the encrypted image. For the purpose of the authentication, for each user, in addition to username and password, the original image, the Delaunay triangulated image, and the Delaunay triangulated-encrypted image are kept in Table 1.  Figure 7(a). After triangulating the image, we launch the second algorithm. The result of Algorithm 4.2 is presented in Figure 7     Step 1: When the user requests the authentication, the banking system firstly identifies the user by the randomly assigned Catalan key. This is the numerical part of the password. For example, if the username is: "pera" and the password is "peric2816098", the Catalan key is 2816098 in decimal. In binary, it is 1010101111100001100010. Then, the system randomly selects an image and a number of sites. The incremental algorithm for Delaunay image triangulation is performed and the vertex coordinates are stored in an array. For example, if an image is selected and triangulated with 10 random points, the vertex coordinates  (469, 471). This image and array are kept in the database because they are later very important in the user authentication process. Now, the originally triangulated image, with the original array of 10 vertices, is sent by the banking system to the user. At this point, a potential attacker has the opportunity to capture a file with a triangulated image and 10 vertices coordinates array. Since no confirmation is being sought at this point, the attacker simply passes the file to reach the user.
Step 3: In this step, the user accepts the file with a triangulated image, 10 vertices of the coordinates array and by the same Catalan key (because only he and the Bank know that the numeric part of the password or Catalan key) encrypts the resulting image and gets the same Delaunay encrypted image and encrypted vertex coordinates as in Step 2. At this point, the user sends the encrypted image to the banking system but does not send the array with encrypted coordinates. Again, the attacker captures the submitted image and forwards it to the Banking system. It should be emphasized that the attacker has no information about the encrypted coordinates of the vertices.
Step 4: This step is reserved for verifying the authenticity of a Delaunay triangulated image sent by the user and the one that has been encrypted and stored by the banking system. Since the images are the same, there is user authentication verification.
Step 5: Given the fact that the attacker, even if he had captured and forwarded the encrypted image to the banking system, does not have information on the value of the encrypted coordinates, the banking system sends an input request for 3 random index coordinates of the encrypted Delaunay array, e.g., values for (x,y) coordinates with indices 4,7 and 2. In this case, the attacker should enter the values p s4 = (66,510), p s7 = (280,140), and p s2 = (391,120), which is almost impossible. If the system does not receive feedback on the correct coordinates, it understands that the attacker is involved in the process of authentication and suspends further actions. Yet, if it receives the correct values of the requested coordinates, then the transaction is approved and that means that the attacker did not participate in the authentication process.

Experimental Results
The time of the Delaunay image triangulation and its encryption was tested on the triangle vertices for n = {20,40,80,160,320,640}. Our Delaunay incremental algorithm, which is modified by the Stack permutation method, is implemented in Java NetBeans environment (see encryption time for proposed method in Table 2). If we present the tabular results in a graph, we will notice that the encryption time is not directly proportional to the number of triangle vertices. We may also notice that the encryption time to a large extent is not much different from the needed time for sole Delaunay triangulation, which points to the efficiency of the stack permutation method (see Figure 9).

Conclusion and Further Research
The main contribution of this proposed method is novel encryption using the Delaunay Triangulation incremental algorithm and the Catalan objects. The proposed method is a combination of computational geometry, authentication, and cryptography. This method presents a new step towards encoding the triangle coordinates using the Catalan-key. The presented method consists of several stages. Catalan object is assigned to the user by a random selection from the corresponding database. Afterward, a random 2D image is selected and triangulated by the Delaunay Triangulation Incremental algorithm. During the triangulation process, we enter n randomly selected triangle vertices whose (x,y) coordinates are stored in an array. The proposed method belongs to both computational geometry and cryptography. It presents a new step towards encoding the triangle coordinates using the Catalan key.
From testing the proposed method, it can be concluded that the best authentication is performed by asking the client to enter the (x,y) coordinate values of randomly selected 3 indices of an array. If the entered coordinates match the index values in the banking system array, then the transaction or other operation is approved. If the matching fails, it means that we have an unidentified person who has followed the whole process and wants to break into the banking system. The triangulated image is encrypted by the assigned Catalan object and the Stack Permutation method. For encryption purposes, in our cryptosystem, we use n>256. Considering given computational and memory limits, it is virtually impossible to generate a complete set of all Catalan keys (or objects). In fact, creating a large space of Catalan keys ensures the security of the described cryptosystem.
Directions for further development of our method can be related to personal authentication using hand vein triangulation, modeled on the work of Kumar and Prathyusha [14,15]. Their method is a novel approach to authenticate individuals using triangulation of hand vein images and simultaneous extraction of knuckle shape information. Also, this approach is fully automated and employs palm dorsal hand vein images acquired from the low-cost, near-infrared, contactless imaging.
Furthermore, some issues in applying 3D Delaunay triangulation in fingerprint authentication can be discussed. From our previous research, according to the model [16] where we have shown the possibilities of applying the triangulation method in the biometric identification process, 3D Delaunay triangulation in fingerprint and face print authentication research can be used in further work.