Research on development of methods of graph theory and automata in steganography and searchable encryption

ver, the keyword based SE faces a problem. Keywords must be determined and also encrypted in a form, and then all files encrypted will be uploaded to the cloud. Then searching for new keywords can follow false results, even if the user data contains these keywords but not mentioned in the set of defined keywords. Furthermore, for the index base SE, very large indexes would make the efficiency of keyword search low [26, 40, 41, 71]. To deal with the above problem, there are some SE techniques proposed such as supporting file update functionality [29, 40, 60, 102], creating index file small [71] and providing pattern matching for search pattern is only asked at search time [26, 41, 89]. As we know that pattern matching is applied to search for information and analyze data every day, for example find and replace in text editing systems, in the search engine 68 Google, database queries, searching on genomic data, etc [26, 90]. Here, the chapter’s work takes an interest in the problem of pattern matching on encrypted data, which is an important research direction in SE. In spite of the considered problem’s importance, it has not been invested properly. To the best of author’s knowledge, there have only existed a few SE methods for exact pattern matching, but not for approximate pattern matching. Haynberg et al. [41] introduced SSE for exact pattern matching by using directed acyclic word graphs in the encryption algorithm (for more details about this data structure, see [14]). However, their technique needs the partial decryption of the ciphertext, it follows that the plaintext would be leaked to the attackers. Further, the searching is performed on users. Strizhov et al. [89] allowed pattern search on ciphertexts using the position heap tree data structure (see [31] for more details about the position heap). For this method, server does not perform search on encrypted data directly but only on index constructed from secret data. Desmoulins et al. [26] proposed SE for exact pattern matching, where the search phase Test is a pattern matching algorithm whose time complexity is O(mn) in the worst case for m,n are lengths of the pattern and the secret data. The goal of this chapter is to propose a novel symmetric cryptosystem that is used on users side, and algorithms for exact and approximate pattern matching on ciphertexts which are used on cloud servers side. These are essential components in SSE. Note that cryptography and data hiding are two branches of information security. Cryptography is used to distort data such that the data is not understood by attackers, it includes symmetric and asymmetric cryptography. While data hiding is used to hide data in digital media such as image, audio, video files, etc. It can be classified into steganography that protects secret data by hiding the existence of them and watermarking that prevents digital media by embedding watermarks in them [22, 103]. Although cryptography and steganography are both capable of protecting secret data separately, different combinations of them are being developed to create systems with better security. The well studied hybrid technique of cryptography and steganography is to encode secret data using cryptography and then embed the ciphertext using steganography [12, 19, 93]. For gray images, Song et al. [86] introduced the first method which encrypts and embeds at once. However, since these methods must all guarantee acceptable imperceptibility of the digital media, the total number of secret data hidden is limited by the size of them. To address this limitation of the existing hybrid methods, the chapter proposes a novel approach to construct a new cryptosystem based on spatial domain image steganography. In the new approach, the chapter uses the data hiding scheme (2, 9, 8) that is block based method in spatial domain, where 9 is the number of pixels in any image block, 8 is the number of secret bits which can be embedded in a block by changing colours of at most 2 pixels in the block. This scheme is near optimal for gray and palette images with high efficiency in embedding capacity, speed, security as well as visual quality, proposed in Section 2.4. Since the proposed cryptosystem is designed to solve the problem of pattern matching on encrypted data and for an assumption that secret data is a string over the alphabet of size 256, the cryptosystem allows to encrypt letters of the secret data one by one. For a given letter in the alphabet, corresponding to a 8-bit string, based on the embedding function in the data hiding scheme (2, 9, 8), the information (called the flip 69 information) is computed to change the input image block. This flip information consists of positions of pixels in the block and way changing colour of these pixels. The code word of the letter is a binary string presenting the flip information. The security analyses show that the proposed cryptosystem provides high security with a key space of 220399!29028! for gray images and 220399!218+9t28! for palette images, where t is the number of bits representing colour indexes. Return to the remaining main objective of the chapter which is the problem of pattern matching on encrypted data on cloud providers side. In Chapters 3 and 4, automata techniques are exploited for the problem of exact pattern matching and the longest common subsequence problem on plaintexts. With using these techniques, the chapters have achieved aims which are to design effective algorithms in practice to solve these problems. This chapter applies these results to constructing exact and approximate pattern matching algorithms on ciphertexts performed by severs. The main idea is to encrypt the automaton corresponding to a given pattern, and then consider this encrypted automaton as a part of the trapdoor for search. Some theoretical analyses remarked that the algorithms all have O(n) time complexity in the worst case, where for approximate algorithm uses d(1− )me processors, where ,m and n are the error of the string similarity measure and lengths of the pattern and secret data, respectively. The rest of this chapter is organized as follows. Sections 5.2, 5.3 and 5.4 propose algorithms used by users and servers in SSE. Firstly, Section 5.2 constructs a novel cryptosystem based on the data hiding scheme proposed in Chapter 2, applies this cryptosystem to the process of encrypting and decrypting a secret data sequence and discusses some security analyses. Sections 5.3 and 5.4 then use the automata approach in Chapters 3 and 4 to design exact and approximate pattern matching algorithms on secrete data encrypted by the cryptosystem proposed in Section 5.2. Finally, Section 5.5 provides the chapter’s conclusions. 5.2 A Novel Cryptosystem Based on The Data Hiding Scheme (2, 9, 8) This section 5.2 proposes a new cryptosystem, a major component in SSE, based on the data hiding scheme (2, 9, 8) proposed in Chapter 2 (Theorem 5.1 and Security analyses (5.3), (5.4)) and applies this cryptosystem to the process of encrypting and decrypting a secret data sequence (Proposition 5.1 and Security analyses (5.9), (5.10)). Call Em′ a function which is derived from the function Em by removing two Statements (2.5) and (2.6). As in Definition 2.10, the state q in Statement (2.4) is computed by q = δ(q,M) = δ2(q,M), where q,M ∈ GF 4(22) and δ2(q,M) =  {(it, at)|1 ≤ it ≤ 9, t = 1, k′, k′ ≤ 2, vit ∈ S, at ∈ GF (22)\{0}, M + (−q) = k′∑ t=1 atvit (on GF 4(22)} if v 6= q, ∅ otherwise, where S = {v1, v2, . . . , v9} is a 2-Generators for the vector space GF 4(22). Note that in Chapter 2 the number of S is given by c399!, where c ≈ 220. (5.1) 70 Then it is easy to check that the function Em′ satisfies Em′ : I ×M×K → 2{1,2,...,9}×GF (22)\{0} and the function Em′ is shown as follows. The function Em′ (computing the flip information q): q = q0; For i = 1 to N Do q = δ(q, Ii); q = δ(q,M); Ex′ is a function obtained from Ex by replacing image blocks Iit with image blocks I ′it in Statement (2.5) and then inserting two Statements (2.6) and (2.5) before Statement (2.7) in Ex, then the function Ex′ holds Ex′ : 2{1,2,...,9}×GF (2 2)\{0} × I × K → M, and the function Ex′ is given as follows. The function Ex′ (extracting M from I ′): I ′ = I; For each (it, at) in q Do I ′ it = Adjacent(I ′it , at); q = q0; For i = 1 to N Do q = δ(q, I ′i); M = q; By Proposition 2.5, we have ∀(I,M,K) ∈ I ×M× K,Ex(Em(I,M,K), K) = M and for the construction of two functions Em′ and Ex′, similarly, we also follow ∀(I,M,K) ∈ I ×M×K, Ex′(Em′(I,M,K), I,K) = M. (5.2) Remark 5.1. From defining two functions Em′ and Ex′ as above, all image blocks I used are not changed. Consider Σ to be an alphabet of size 256. Set P = Σ. By the decimal representation of the vector space GF 4(22) over the field GF (22) in Section 2.4, then |P| = |GF 4(22)| = 256, hence there exists a bijective function f from P to GF 4(22), denote the inverse function of f by f−1. Put F to be a set of all f . From the function δ2, the state q of the automaton A(I,M,K) computed by Statement (2.4) is a set. The state q may be one of the following sets: ∅, {(i, a)} for i ∈ {1, 2, . . . , 9}, a ∈ GF (22)\{0} or {(i, a), (j, b)} for i, j ∈ {1, 2, . . . , 9}, a, b ∈ GF (22)\{0}. The index i ∈ {1, 2, . . . , 9} and the coefficient a ∈ GF (22)\{0}) = {1, 2, 3} can be presented by binary strings of lengths 4 and 2, respectively. Hence, use 12 binary bits to present a state q. Suppose B is a binary string of length 12 to present an arbitrary state q, B = B12 . . . B2B1, then the storage structure of q in B is given as follows. 1. If q = ∅, then the value of any bit in B equals 0. 2. If q = {(i, a)}, then the values of 6 bits B7, B8, . . . , B12 are 0; 6 remaining bits present (i, a), where 2-bit string B2B1 presents a, 4-bit string B6B5B4B3 presents i. 71 3. If q = {(i, a), (j, b)}, then the 6-bit string B12B11..B7 presents (i, a) and the remaining 6-bit string B6B5..B1 presents (j, b) in the above mentioned way. Put Q to be a set of all possible states q, C is a set of all 12-bit strings B presenting q, q ∈ Q. Consider a function h, h : Q→ C, h(q) = B, where q is presented by B. Obviously, h is a bijective function. Denote the inverse function of h by h−1. Let K′ = {(f,K, I)|f ∈ F , K ∈ K, I ∈ I} is a finite set of secret keys. For k ∈ K′, k = (f,K, I), ek and dk are defined as follows. 1. ek : P → C, ek(x) = h(Em′(I, f(x), K)) for x ∈ P . 2. dk : C → P , dk(y) = f−1(Ex′(h−1(y), I,K)) for y ∈ C. Set E = {ek|k ∈ K′}, D = {dk|k ∈ K′}. From Definition 1.13, the correctness of the cryptosystem (P , C,K′, E ,D) is guaranteed by the following theorem. Theorem 5.1. Let ∀x ∈ P ,∀k ∈ K′, ek ∈ E and dk ∈ D. Then dk(ek(x)) = x. Proof. Set M = f(x), q = Em′(I,M,K), B = h(q), then ek(x) = B = y. We have h−1(y) = h−1(B) = q, Ex′(q, I,K) = M by Formula (5.2), f−1(M) = x, then dk(y) = x. Security analysis of the cryptosystem (P , C,K′, E ,D): Assume that publish parameters the flip graph G,Em′, Ex′, GF 4(22) and h in the cryptosystem (P , C,K′, E ,D). The plaintext x is obtained from y by the Formula x = dk(y) = f −1(Ex′(h−1(y), I,K)). So, to have accurately x, we need to know S and k = (f,K, I). The number of choices for the image block I is 2569 with gray images, 29t with palette images, where t is the number of bits to represent colour indexes. Furthermore, by Formula (2.45), the security of the cryptosystem (P , C,K′, E ,D) is given by the following formula c399!21828!2569 = c399!29028! for gray images, (5.3) or c399!21829t28! = c399!218+9t28! for palette images. (5.4) Remark 5.2. By Remark 5.1, all pairs of functions (ek, dk) in the cryptosystem (P , C,K′, E ,D) do not make the image blocks I change for ∀k ∈ K′, k = (f,K, I). In addition, we can see that encrypting and hiding are done at the same time. Consider an arbitrary subset of image blocks F as an input image, F ⊂ I, F = {F1, F2, . . . , Ft2}, t2 is the number of image blocks. Next, Section 5.2 gives a way applying the cryptosystem (P , C,K′, E ,D) to the process of encrypting and decrypting secret data over an insecure channel. By Remark 5.2, we can use a secret key subset K′′ instead of one secret key k, K′′ = {(f,K, I)|K ∈ K, I ∈ F} ⊂ K′ for f ∈ F ,K = {K1, K2, . . . , Kt1}. 72 Suppose that secret data is a string x = x1x2..xt3 for xi ∈ P ,∀i = 1, t3, t3 ≥ 1. The encrypting algorithm eK′′ used to encrypt x is given as follows. iK = 1; iF = 1; For i = 1 to t3 Do { ki = (f,K iK , FiF ); (5.5) yi = eki(xi); (5.6) iK = (iK − 1) mod t1 + 1; iF = (iF − 1) mod t2 + 1; } y = y1y2..yt3 ; The decrypting algorithm dK′′ used to decrypt y is given as follows. iK = 1; iF = 1; For i = 1 to t3 Do { ki = (f,K iK , FiF ); (5.7) x′i = dki(yi); (5.8) iK = (iK − 1) mod t1 + 1; iF = (iF − 1) mod t2 + 1; } x′ = x′1x ′ 2..x ′ t3 ; Propostion 5.1. Let F, x,K′′ and the cryptosystem (P , C,K′, E ,D) based on the data hiding (2, 9, 8) as above. Then dK′′(eK′′(x)) = x. Proof. Clearly, ∀i, i = 1, t3, ki determined in Statement (5.5) is the same as in Statement (5.7). In addition, by Theorem 5.1, xi is encrypted by Statement (5.6) and obtained by Statement (5.8) such that x′i = xi. Then x = x ′, hence dK′′(eK′′(x)) = x. Security analysis of process of encrypting and decrypting the secret data x using two algorithms eK′′ and dK′′ : Assume that also publish parameters as in the cryptosystem (P , C,K′, E ,D). Hence, to restore exactly x, we need to know S and K′′. The number of choices for S is c399! by Formula (5.1). The number of choices for K′′ is 28!218t12569t2 (for gray images), 28!218t129tt2 (for palette images, where t is the number of bits to represent colour indexes). Then for a brute force attack, the number of all possible combinations of S and K′′ used in two algorithms eK′′ and dK′′ is c399!28!218t12569t2 = c399!28!218t1+72t2 for gray images, (5.9) 73 or c399!28!218t129tt2 = c399!28!218t1+9tt2 for palette images. (5.10) Remark 5.3. For two algorithms eK′′ and dK′′ given as above, an arbitrary image block I in the input image F can be used many times in process of encrypting and decrypting the secret data. So, for a give input image F , the secret data encrypted is not limited by the size of the input image F . 5.3 Automata Technique for Exact Pattern Matching on Encrypted Data This section applies the automata approach proposed in Chapter 3 to designing an algorithm for exact pattern matching on secret data encrypted by the cryptosystem proposed in Section 5.2 (Theorem 5.2). Suppose that Alice has a secret data and prefers to outsource this data to a cloud provider Bob. As the provider is semi-trusted, Alice needs to encrypted her plaintext and wishes to only store ciphertext in the cloud. Assume that Alice uses the cryptosystem (P , C,K′, E ,D) proposed in Section 5.2 to encrypt data with a pair of two secret parameters (S, k) in the cryptosystem, where S is a 2-Generators for GF 4(22) with 9 elements and k = (f,K, I) ∈ K′. Because of limited storage space and computing ability, instead of downloading ciphertext, decrypting it and searching locally, Alice may ask Bob to perform pattern matching tasks on the ciphertext directly with a trapdoor of the pattern received from her. Consider Σ to be an alphabet of size 256. Suppose that the secret data is a string over Σ x = x1x2..xt3 for xi ∈ P ,∀i = 1, t3, t3 ≥ 1 and t3 is often a large natural number, where P = Σ. Before uploading the secret data x to Bob, Alice use the encrypting function ek ∈ E to encrypt each xi. Then Alice computes yi = ek(xi),∀i = 1, t3, and the encrypted secret data is a string over Σ′ y = y1y2..yt3 which is sent to Bob, where Σ′ is an alphabet Σ′ = {a′|a′ = ek(a), a ∈ Σ}. In general case, for x is any string over the alphabet Σ and a string y is obtained from x by the above way. Then we can write y = ek(x) for short and y is a string over the alphabet Σ′. Remark 5.4. By using only one pair of two secret parameters (S, k), then the security of process of encrypting and decrypting the secret data x is similar to Formulas (5.3) (for gray images) or (5.4) (for palette images). Suppose that Bob needs to perform exact pattern matching task of an arbitrary pattern p on encrypted data y. Based on previously introduced results in Chapter 3, here continues using automata technique to meet the requirement. 74 Propostion 5.2. Let p be a pattern over the alphabet Σ. Then Posp′(a ′) = Posp(a) for ∀a′ ∈ Σ′, a = dk(a′), where p′ = ek(p). Proof. Set i = Posp(a), then a = pi, hence a ′ = p′i. Without loss of generality, suppose Posp′(a ′) > i, then ∃i′ > i, p′i′ = a′ by Definition 3.3, then a = pi′ = dk(p′i′). Then i < Posp(a), a contradiction. So, we complete the proof. Propostion 5.3. Let a pattern p and a text x be two strings over the same alphabet Σ and the function Sign be given by ∀a′ ∈ Σ′, Sign(a′) = { 1 If a ∈ p, 0 Otherwise. Then ∀a′ ∈ Σ′, a′ ∈ p′ if and only if Sign(a′) = 1. Proof. Suppose ∀a′ ∈ Σ′, a′ ∈ p′ if and only if ∃i, i = 1..|p′|, a′ = p′i if and only if a = pi if and only if Sign(a′) = 1. Propostion 5.4. Let a pattern p and a text x be two strings over the same alphabet Σ. Then p occurs at any position i in x if and only if p′ occurs at the position i in y, where y = ek(x). Proof. Suppose that p occurs at any position i in x if and only if p = xixi+1..xi+|p|−1 if and only if yiyi+1..yi+|p|−1 = p′ if and only if p′ occurs at the position i in y. Propostion 5.5. Let p be a pattern over the alphabet Σ. Then ∀l, 1 ≤ l ≤ |p|, Nextp′(l) = Nextp(l), where p ′ = ek(p). Proof. Without loss of generality, suppose that lm = Nextp(l) < Nextp′(l) for ∀l, 1 ≤ l ≤ |p|. Since p′i = ek(pi),∀i = 1..|p|, then p′1p′2..p′lm +1 is both a proper prefix and suffix of p′[1..l] by Definition 3.1. Hence, p1p2..plm +1 is also both a proper prefix and suffix of p[1..l] by Definition 3.1. Then Nextp(l) > lm. This is a contradiction to the supposition. So, the proof is complete. Propostion 5.6. Let p be a pattern over the alphabet Σ. Then for ∀l, 0 ≤ l ≤ |p| and ∀a′ ∈ Σ′, a = dk(a′), Appearancep′(l, a′) = Appearancep(l, a), where p′ = ek(p). Proof. Clearly, |p| = |p′| and for ∀i, 1 ≤ i ≤ |p′|,∀a′, a′ ∈ Σ′, a′ = p′i if and only if a = pi. By Lemma 3.1 and Proposition 5.5, Appearancep′(l, a ′) = Appearancep(l, a). Theorem 5.2. Let p be a pattern over the alphabet Σ. Let two automata Mp = (Σ, Qp, q0, δp, Fp) and Mp′ = (Σ ′, Qp′ , q0, δp′ , Fp′) be determined as in Theorem 3.2. Then Qp′ = Qp, Fp′ = Fp,∀q ∈ Qp′ ,∀a′ ∈ Σ′, a = dk(a′), δp′(q, a′) = δp(q, a), where p′ = ek(p). Proof. It is easy to verify that |p| = |p′|. In addition, by Theorem 3.2 and Proposition 5.6, then Qp′ = Qp, Fp′ = Fp and δp′(q, a ′) = δp(q, a). Remark 5.5. The meaning of Theorem 5.2 in practice is to compute δp′ from δp. 75 Let a pattern p and a text (secret data) x be two strings over the same alphabet Σ and assume |p|  |x|. For assuming that we have only the encrypted secret data y which is not decrypted to the secret data x, from Propositions 5.2, 5.3 and 5.4, Theorem 5.2, based on the MRc algorithm for c = 1 and using the type a breaking point and the concept of Posp in Chapter 3, and by using the automaton Mp′ given as in Theorem 3.2, we have an exact pattern matching algorithm immediately that finds all occurrences of the pattern p in x as follows. Note that the trapdoor according to the search pattern p is computed based on p, which includes the length of p, the functions Sign, Posp′ and the automaton Mp′ . jump = |p|; While (jump ≤ |y|) { If (sign(yjump) == 1) { q = 0; i = jump− Posp′(yjump) + 1; Do { q = δp′(q, yi); If (q == |p|) Mark an occurrence of p at i− |p|+ 1 in x; i+ +; } While (q 6= 0 and i ≤ |y|); jump = i− 1; } jump = jump+ |p|; } Remark 5.6. Obviously, the above algorithm is the same as the MRc algorithm in Chapter 3 for c = 1, using the type a breaking point and concepts of Posp′ , and where Posp and δp of the MRc algorithm are replaced with Posp′ and δp′ . Furthermore, by Propositions 3.2 and 5.2, and Theorem 5.2, clearly in the worst case, this algorithm’s time complexity is O(n). 5.4 Automata Technique for Approximate Pattern Matching on Encrypted Data Suppose that Bob wants to do approximate pattern matching of any pattern p on the ciphertext y. From results proposed in Chapter 4, automata technique is still applied to meeting the requirement (Theorem 5.3). Propostion 5.7. Let p be a pattern over the alphabet Σ. Then WConfig(p′) = WConfig(p), where p′ = ek(p). Proof. Obviously, W0 belongs to WConfig(p ′) and WConfig(p). Consider any W ′ ∈ WConfig(p′)\{W0}, then we can set W ′ = {w′1, w′2, . . . , w′l} for 1 ≤ l ≤ |p′|. Then 76 ∃C ′ = {u′1, u′2, . . . , u′l} ∈ Config(p′) by Definition 4.2, where Wp′(u′i) = w′i for 1 ≤ i ≤ l. Then ∃!C = {u1, u2, . . . , ul} ∈ Config(p), where ui = dk(u′i) for 1 ≤ i ≤ l. Set W = Wp(C), then W ∈ WConfig(p) by Definition 4.2. It easy to verify that Rmp′(u ′ i) = Rmp(ui) for 1 ≤ i ≤ l by Definition 1.10, then Wp′(u′i) = Wp(ui) for 1 ≤ i ≤ l by Definition 4.1. Hence, W ′ = W , then WConfig(p′) ⊂ WConfig(p). Similarly, we have WConfig(p) ⊂WConfig(p′). So, the proof is complete. Propostion 5.8. Let p be a pattern over the alphabet Σ. Then Refp′(i, a ′) = Refp(i, a) for ∀i, 0 ≤ i ≤ |p′| and ∀a′ ∈ Σ′, a = dk(a′), where p′ = ek(p). Proof. Clearly, W ip′(a ′) = W ip(a) by Definition 4.3. So, Refp′(i, a′) = Refp(i, a) by Definition 4.4. Hence, we complete the proof. Theorem 5.3. Given a pattern p on Σ and a positive integer constant c with 1 ≤ c ≤ |p|. Let two automata APcp = (Σ, Qp, q0, δp, Fp) and APcp′ = (Σ′, Qp′ , q0, δp′ , Fp′) be determined as in Theorem 4.4. Then Qp′ = Qp, Fp′ = Fp,∀q ∈ Qp′ , ∀a′ ∈ Σ′, a = dk(a′), δp′(q, a ′) = δp(q, a), where p′ = ek(p). Proof. By Proposition 5.7, Qp′ = Qp. Evidently, ∀a′ ∈ Σ′, a = dk(a′), a′ ∈ p′ if and only if a ∈ p. Furthermore, by Definition 4.9 and Proposition 5.8, δp′(W,a′) = δp(W,a). Then Fp′ = Fp. So, the proof is complete. Remark 5.7. The meaning of Theorem 5.3 in practice is to compute δp′ from δp. Based on the approximate pattern matching problems considered in [66, 67, 73], the section introduces a new concept of the appearance of the pattern p in x with a given error. This is a basis for giving requirements for the approximate pattern matching algorithm. Definition 5.1. Given two strings p and x over Σ, and a string similarity measure d. Let an error ,  > 0,  ∈ <. Then p appears in x with the error  if there exists a substring u of x such that d(p, u) ≤ . To construct the approximate pattern matching algorithm, we need a function to measure the string similarity. The most commonly used similarities are recalled in [71, 73, 77]. Bakkelund [8] proposed a well known string similarity measure which is based on the longest commonly subsequence. Similarly, here this section defines a new measure of similarity between two strings d(p, u) = 1− lcs(p, u) min{|p|, |u|} , (5.11) where p is a pattern and u is a substring of x. Clearly, d given above is positive definite and symmetric. Propostion 5.9. Given two strings p and x over the same alphabet Σ. Then ∀u′, u′ is an arbitrary substring of y, d(p′, u′) = d(p, u), where p′ = ek(p), y = ek(x), u = dk(u′). Proof. Clearly, |p′| = |p|, |u′| = |u| and lcs(p, u) = lcs(p′, u′). By Formula (5.11), d(p′, u′) = d(p, u). So, we complete the proof. 77 By using the string similarity measure given in Formula (5.11), the automata technique proposed in Chapter 4 for computing lcs(p′, u′) will make an approximate pattern matching algorithm fast, and especially efficient for one pattern and a set of a large number of encrypted texts. Given a pattern p and a text (secret data) x over the same alphabet Σ, and an arbitrary substring u of x. Let , 0 <  < 1 and d(p, u) be given as in Formula (5.11) such that d(p, u) ≤ . Then by Proposition 5.9, d(p′, u′) ≤ . By Formula (5.11), we have lcs(p′, u′) ≥ (1− )min{|p′|, |u′|}. (5.12) If there is u′ which is a substring of y such that lcs(p′, u′) ≥ (1 − )|p|, then Formula (5.12) holds that means d(p′, u′) ≤ . Hence, ∃u, u is a substring of x, d(p, u) ≤ . So, the constant c in Theorem 4.4 is determined by c = d(1− )|p|e. Without decrypting y, based on Theorem 5.3, Definition 5.1 and Formula (5.11), use the automaton APcp′ given as in Theorem 4.4, we immediately have an approximate pattern matching algorithm which determines whether p appears in x with the error  or not as follows, where the trapdoor responding to the pattern p is determined from p and , which consists of the constant c and the automaton APcp′ . app = 0; q = W0; //The initial state of the automaton APcp′ is started from W0 For i = 1 to |y| Do { q = δp′(q, yi); If (|q| = c) {app=1; Break;} } If (app = 1) Announce the appearance of the pattern p in x with the error ; Else Announce that p does not appear in x with the error . Remark 5.8. Since we can compute δp′ from δp, the above proposed algorithm is similar to the Algorithm 2 (the parallel algorithm) in Chapter 4. In addition, according to Theorem 4.4, δp is computed in parallel way and the Algorithm 2 costs the worst case time complexity O(n) with the supposition that the Algorithm 2 uses k processors for k is an upper estimate of the lcs(p, x). As an immediately consequence, in the worst case, time complexity of the algorithm is O(n) when it uses d(1− )|p|e processors. 5.5 Conclusions From results of steganography, pattern matching and some suggestions in the next works in Chapters 2, 3 and 4, this chapter has completed some parts of those works. Based on the data hiding scheme (2, 9, 8) in Chapter 2, the chapter constructs a novel cryptosystem with high security. This method allows both of encrypting and hiding to be done at once, ciphertexts not to depend on the input image size as existing hybrid techniques of cryptography and steganography. In addition, this cryptosystem can be used to encrypt and decrypt secret data by users in SSE. For the ciphertext made by the cryptosystem on users side, the chapter designs two pattern matching algorithms to search for any pattern 78 in it directly on cloud servers side. The outstanding feature of the algorithms is that, they can be applied well to all cryptosystems that support encrypting letters of the secret data one by one. The idea of the design is to apply the automata approach for the exact pattern matching and the longest common subsequence problems in Chapters 3 and 4. For the assumption that the approximate algorithm uses d(1− )me processors, the time complexities of these algorithms are both O(n) in the worst case, where ,m and n are the error of a measure of similarity between two strings proposed in Section 5.4 and lengths of the pattern and secret data, respectively. With the proposed automata approach to pattern matching algorithms, the automata constructed are only based on search patterns. Then the algorithms will have lots of advantages in case of a given pattern and a very large set of ciphertexts stored in the cloud. So, future work continues studying this technique to apply in SE. 79 CONCLUSION Based on the supervision of Assoc. Prof. Dr. Sc. Phan Thi Ha Duong and Dr. Vu Thanh Nam, and study on results using graph theory and automata technique proposed by P. T. Huy et al. in steganography and searchable encryption, new contributions of the dissertation in these fields can be summarized as follows: 1. A general approach based on the Galois field GF (pm) using graph theory and automata to designing optimal and near optimal secret data hiding schemes for binary, gray and palette images (Chapter 2); 2. Based on the approach, Chapter 2 shows that the data hiding scheme CTL [18] reaches an optimal data hiding scheme with N = 2n − 1, where n is a positive integer; 3. From the approach, Chapter 2 proposes data hiding schemes consisting of the optimal data hiding scheme (1, 2n−1, n) for binary, gray and palette images with qcolour = 1, where n is a positive integer, the near optimal data hiding scheme (2, 9, 8) and the optimal data hiding scheme (1, 5, 4) for gray and palette images with qcolour = 3; 4. A flexible automata approach to constructing an efficient algorithm for the exact pattern matching problem in practice (Chapter 3); 5. Mathematical basis for the development of automata technique for computing the lcs(p, x) (Chapter 4); 6. By the above basis, Chapter 4 proposes two efficient sequential and parallel algorithms computing the lcs(p, x) in practice. The parallel algorithm takes O(n) time in the worst case if it uses k processors, where k is an upper estimate of the length of a longest common subsequence of the two strings p and x; 7. Based on results proposed in Chapters 2, 3 and 4, Chapter 5 proposes two major components of SSE: a) A novel cryptosystem based on the data hiding scheme (2, 9, 8) with high security, used by users. This method allows both of encrypting and hiding to be done at once, the ciphertext not to depend on the input image size as existing hybrid techniques of cryptography and steganography; b) Two exact and approximate pattern matching algorithms, using automata technique, search for any pattern in ciphertexts directly, performed by cloud servers. For the assumption that the approximate algorithm uses d(1− )me processors, the time complexities of these algorithms are both O(n) in the worst case, where ,m and n are the error of the proposed measure of similarity between two strings and lengths of the pattern and secret data, respectively. Because the problem of development of methods of graph theory and automata in steganography and searchable encryption is topical, some following interest problems can be considered in the future: 1. Whether there exists the optimal data hiding scheme (2, 8, 8) for 8-bit gray image with qcolour = 3; 2. Improving the quality of stego image generated by proposed data hiding schemes for palette images; 3. The problem of steganalysis attacks; 4. Development of automata technique in SE. 80 BIBLIOGRAPHY [1] A. V. Aho, D. S. Hirschberg, J. D. Ullman (1976), “Bounds on The Complexity of The Longest Common Subsequence Problem”, Journal of the Association for Computing Machinery, 23(1), pp. 1-12. [2] O. I. I. Al-Farraji (2016), “Combination between Steganography and Cryptography in Information Hiding by Using Same Key”, International Journal of Engineering Research and General Science, 4(6), pp. 201-208. [3] C. Allauzen, M. Crochemore, M. Raffinot (1999), “Factor Oracle: A New Structure for Pattern Matching”, In: J. Pavelka, G. Tel, M. Bartosˇek (Eds.) Theory and Practice of Informatics, 26th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 27 - December 4, 1999. Proceedings. LNCS-1725, Springer, pp. 295-310. [4] S. AL-Mansoori, A. Kunhu (2013), “Discrete Cosine Transform and Hash Functions toward Implementing a (Robust-Fragile) Watermarking Scheme”, Proc. SPIE 8895, High-Performance Computing in Remote Sensing III, 889504. [5] V. S. Babu, K. J. Helen (2015), “A Study on Combined Cryptography and Steganography”, International Journal of Research Studies in Computer Science and Engineering, 2(5), pp. 45-49. [6] A. Baby, H. Krishnan (2017), “Combined Strength of Steganography and Cryptography - A Literature Survey”, International Journal of Advanced Research in Computer Science, 8(3), pp. 1007-1010. [7] R. Baeza-Yates, G. H. Gonnet (1992), “A New Approach to Text Searching”, Communications of the ACM, 35(10), pp. 74-82. [8] D. Bakkelund (2009), “An LCS-based String Metric”, University of Oslo (Norway), September 23. [9] A. Begum (2008), “A Greedy Approach for Computing Longest Common Subsequences”, Journal of Prime Research in Mathematics, Vol. 4, pp. 165-170. [10] T. Berry, S. Ravindran (2001), “Fast String Matching Algorithm and Experimental Results”, A Proceedings of the Prague Stringology Club Workshop 99, Collaborative Report DC-99-05, Czech Technical University, Prague, pp. 16-26. [11] J. Berstel, D. Perrin (1985), “Theory of Codes”, Academic Press. [12] P. Bharti, R. Soni (2012), “A New Approach of Data Hiding in Images using Cryptography and Steganography”, International Journal of Computer Applications, 58(18), pp. 1-5. [13] G. Birkhoff, S. M. Lane (1969), “A Survey of Modern Algebra” (Third edition), Macmillan Company. 81 [14] A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, J. Seiferas (1985), “The Smallest Automation Recognizing The Subwords of A Text”, Theoretical Computer Science, Vol. 40, pp. 31-55. [15] R. S. Boyer, J. S. Moore (1977), “A Fast String Searching Algorithm”, Communications of the ACM, 20(10), pp. 762-772. [16] D. Cantone, S. Faro (2005), “Fast-Search Algorithms: New Efficient Variants of the Boyer-Moore Pattern-Matching Algorithm”, J. Autom. Lang. Comb., 10(5/6), pp. 589-608. [17] S. Chakraborty, S. K. Bandyopadhyay (2013), “Steganography Method Based On Data Embedding By Sudoku Solution Matrix”, International Journal of Engineering Science Invention, 2(7), pp. 2319-6726. [18] C. C. Chang, C. S. Tseng, C. C. Lin (2005), “Hiding Data in Binary Images”, In: Robert H. Deng, Feng Bao, HweeHwa Pang, Jianying Zhou (Eds.) Information Security Practice and Experience, 1st International Conference, ISPEC 2005, Singapore, April 11-14, 2005. Proceedings. LNCS-3439, Springer, 2005, pp. 338-349. [19] A. Chatterjee, A.K. Das (2018), “Secret Communication Combining Cryptography and Steganography”, In: K. Saeed, N. Chaki, B. Pati, S. Bakshi, D. Mohapatra (Eds.) Progress in Advanced Computing and Intelligent Engineering. Advances in Intelligent Systems and Computing, Vol. 563. Springer, Singapore, pp. 281-291. [20] A. Cheddad, J. Condell, K. Curran, P. M. Kevitt (2010), “Digital Image Steganography: Survey and Analysis of Current Methods”, Signal Processing, 90(3), pp. 727-752. [21] J. Chen, T. S. Chen, M. W. Cheng (2003), “A New Data Hiding Method in Binary Image”, Proceedings of the IEEE Fifth International Symposium on Multimedia Software Engineering, pp. 88-93. [22] G. Chugh (2013), “Information Hiding - Steganography & Watermarking: A Comparative Study”, International Journal of Advanced Research in Computer Science, 4(4), pp. 165-171. [23] V. Chvatal, D. A. Klarner, D. E. Knuth (1972), “Selected Combinatorial Research Problems”, Stan-CS-TR-72-292, pp. 26. [24] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2001), “Introduction to Algorithms (Second edition)”, MIT Press, Chapter 32. [25] M. Crochemore, W. Rytter (1994), “Text Algorithms”, Oxford University Press. [26] N. Desmoulins, P. A. Fouque, C. Onete, O. Sanders (2018), “Pattern Matching on Encrypted Streams”, In: T. Peyrin, S. Galbraith (Eds.) Advances in Cryptology - ASIACRYPT 2018. LNCS-11272, Springer, pp. 121-148. [27] A. Dhraief, R. Issaoui, A. Belghith (2011), “Parallel Computing The Longest Common Subsequence (LCS) on GPUs: Efficiency and Language Suitability”, Proceedings of the 1st International Conference on Advanced Communications and Computation, Spain, October 23-28, 2011, pp. 143-148. [28] Q. Dong, Z. Guan, L. Wu, Z. Chen (2013), “Fuzzy Keyword Search over Encrypted Data in the Public Key Setting”, In: J. Wang, H. Xiong, Y. Ishikawa, J. Xu, J. Zhou (Eds.) Web-Age Information Management. LNCS-7923, Springer, pp. 729-740. 82 [29] R. Dowsley, A. Michalas, M. Nagel, N. Paladi (2017), “A Survey on Design and Implementation of Protected Searchable Data in The Cloud”, Computer Science Review, Vol. 26, pp. 17-30. [30] B. Durian, J. Holub, H. Peltola, J. Tarhio (2009), “Tuning BNDM with q-Grams”, In: I. Finocchi, J. Hershberger (Eds.) Algorithm Engineering and Experiments, 10th Workshop, ALENEX 2009, New York, January 3, 2009. Proceedings., pp. 29-37. [31] A. Ehrenfeucht, R, M. McConnell, N. Osheim, S. W. Woo (2011), “Position Heaps: A Simple and Dynamic Text Indexing Data Structure”, Journal of Discrete Algorithms, Vol. 9, pp. 100-121. [32] S. Faro, T. Lecroq (2009), “Efficient Variants of The Backward-Oracle-Matching Algorithm”, International Journal of Foundations of Computer Science, 20(6), pp. 967-984. [33] S. Faro, T. Lecroq (2013), “The Exact Online String Matching Problem: A Review of the Most Recent Results”, ACM Computing Surveys, 45(2), Article 13. [34] F. Franek, C. G. Jennings, W. F. Smyth (2007), “A Simple Fast Hybrid Pattern- Matching Algorithm”, Journal of Discrete Algorithms, 5(4), pp. 682-695. [35] K. Fredriksson, S. Grabowski (2005), “Practical and Optimal String Matching”, In: M. P. Consens, G. Navarro (Eds.) String Processing and Information Retrieval, 12th International Conference, SPIRE 2005, Buenos Aires, Argentina, November 2-4, 2005. Proceedings, LNCS-3772, Springer, pp. 376-387. [36] J. Fridrich (1999), “A New Steganographic Method for Palette-Based Images”, Proceedings of The IS&T PICS Conference, pp. 285-289. [37] J. Fridrich, R. Du (2000), “Secure Steganographic Methods for Palette Images”, Proceedings of The IS&T PICS Conference, pp. 47-60. [38] Y. K. Gedam, J.N. Varshapriya (2014), “Fuzzy Keyword Search Over Encrypted Data in Cloud Computing”, Journal of Engineering Research and Applications, 4(7), pp. 197-202. [39] R. C. Gonzalez, R. E. Woods (2008), “Digital Image Processing”, Pearson Prentice Hall. [40] F. Han, J. Qin, J. Hu (2016), “Secure Searches in The Cloud: A Survey”, Future Generation Computer Systems, Vol. 62, pp. 66-75. [41] R. Haynberg, J. Rill, D. Achenbach, J. Mu¨ller-Quade (2013), “Symmetric Searchable Encryption for Exact Pattern Matching using Directed Acyclic Word Graphs”, In: Samarati, Pierangela (Eds.) Security and Cryptography, the 10th International Conference on Security and Cryptography, SECRYPT 2013, Reykjavk, Iceland, July 29-31, 2013. Proceedings. SciTePress, pp. 403-410. [42] D. S. Hirschberg (1975), “A Linear Space Algorithm for Computing Maximal Common Subsequences”, Comm. ACM, 18(6), pp. 341-343. [43] J. Holub, B. Durian (2005), “Talk: Fast Variants of Bit Parallel Approach to Suffix Automata”, In: The Second Haifa Annual International Stringology Research Workshop of the Israeli Science Foundation. 83 [44] J. E. Hopscoft, R. Motwani, J. D. Ullman (2001), “Introduction to Automata Theory, Languages, and Computation” (Second Edition), Addison-Wesley. [45] R. N. Horspool (1980), “Practical Fast Searching in Strings”, Software Practice and Experience, 10(6), pp. 501-506. [46] C. L. Hou, C. Lu, S. C. Tsai, W. G. Tzeng (2011), “An Optimal Data Hiding Scheme with Tree-Based Parity Check”, IEEE Transactions on Image Processing, 20 (3), pp. 880-886. [47] P. T. Huy, N. Q. Khang (2002), “A New Algorithm for LCS Problem”, Proceedings of the 6th Vietnam Conference of Mathematics, Hue, September 7-10, 2002, pp. 145-157. [48] P. T. Huy, C. Kim, N. H. Thanh (2013), “Modules over Rings of Small Characteristics and Maximality of Data Hiding Ratio in CPTE Schemes”, American Journal of Applied Sciences, 10 (9), pp. 1102-1108. [49] P. T. Huy, N. H. Thanh (2011), “On the Maximality of Secret Data Ratio in CPTE Schemes”, In: N. T. Nguyen, C. G. Kim, A. Janiak (Eds.) Intelligent Information and Database Systems, Third International Conference, ACIIDS 2011, Korea, April 20-22, 2011, Proceedings, Part I. LNCS-6591, Springer, pp. 88-99. [50] P. T. Huy, N. H. Thanh, N. T. Dat, C. Kim (2013), “Improving Optimal Parity Assignments in Palette Images”, Journal INFORMATION, 16 (4), pp. 2661-2668. [51] P. T. Huy, N. H. Thanh, C. Kim (2012), “Relationship between Correcting Code and Module Technique in Hiding Secret Data”, In: J. J. Park, A. Zomaya, S. S. Yeo, S. Sahni (Eds.) Network and Parallel Computing, Ninth International Conference, NPC 2012, Korea, September 6-8, 2012, Proceedings. LNCS-7513, Springer, pp. 297-307. [52] N. T. T. Huyen, P. T. Huy (2002), “Fuzzy Approach in Some Pattern Matching Algorithms”, Vietnam J. of Computer Science and Cybernetics, 18(3), pp. 201-210. [53] S. Ijeri, S. Pujeri, B. Shrikant, B. A. Usha (2012), “Image Steganography Using Sudoku Puzzle for Secured Data Transmission”, International Journal of Computer Applications, 48(17), pp. 31-35. [54] C. S. Iliopoulos, M. S. Rahman (2009), “A New Efficient Algorithm for Computing The Longest Common Subsequence”, Theory Comput Syst, Vol. 45, pp. 355-371. [55] Indu, Prena (2016), “Comparative Study of Different Longest Common Subsequence Algorithms”, International Journal of Recent Research Aspects, 3(2), pp. 65-69. [56] J, Irvine, D. Harle (2002), “Data Communications and Networks: An Engineering Approach”, John Wiley & Sons, Ltd. [57] M. Jain, S. K. Lenka (2016), “A Review of Digital Image Steganography using LSB and LSB Array”, International Journal of Applied Engineering Research, 11(3), pp. 1820-1824. [58] N. S. Jho, D. Hong (2013), “Symmetric Searchable Encryption with Efficient Conjunctive Keyword Search”, KSII Transactions on Internet and Information Systems, 7(5), pp. 1328-1342. [59] T. Jiang, M. Li (1995), “On The Approximation of Shortest Common Supersequences and Longest Common Subsequences”, SIAM J. Comput, 24(5), pp. 1122-1139. 84 [60] M. S. John, P. SumaLatha, M. Joshuva (2015), “A Comparative Study of Index-Based Searchable Encryption Techniques”, International Journal of Advanced Research in Computer Science, 6(3), pp. 13-15. [61] N. Khan, K. S. Gorde, M. E. Student (2015), “Data Security by Video Steganography and Cryptography Techniques”, International Journal of Emerging Trends in Electrical and Electronics, 11(5), pp. 58-64. [62] I. Khan, S. Gupta, S. Singh (2016), “A New Data Hiding Approach in Images for Secret Data Communication with Steganography”, International Journal of Computer Applications, 135(13), pp. 9-14. [63] A. Khan, A. Siddiqa, S. Munib, S. A. Malik (2014), “A Recent Survey of Reversible Watermarking Techniques”, Information Sciences, Vol. 279, pp. 251-272. [64] D. E. Knuth, J. H. Morris, Jr., V. R. Pratt (1977), “Fast Pattern Matching in Strings”, SIAM J. Comput., 6(2), pp. 323-350. [65] W. C. Kuo, S. H. Kuo, C. C. Wang, L. C. Wuu (2016), “High Capacity Data Hiding Scheme Based on Multi-bit Encoding Function”, Optik, Vol. 127, pp. 1762-1769. [66] G. M. Landau, U. Vishkin (1986), “Efficient String Matching with k Mismatches”, Theoretical Computer Science, Vol. 43, pp. 239-249. [67] J. V. Leeuwen (1990), “Handbook Of Theoretical Computer Science”, Vol. A, Elsevier MIT Press. [68] T. Lecroq (2007), “Fast Exact String Matching Algorithms”, Information Processing Letters, 102(6), pp. 229-235. [69] X. Li, S. Cai, W. Zhang, B. Yang (2015), A “Further Study of Large Payloads Matrix Embedding”, Information Sciences, Vol. 324, pp. 257-269. [70] D. Maier (1978), “The Complexity of Some Problems on Subsequences and Supersequences”, Journal of the ACM, 25(2), pp. 322-336. [71] Z. Mei, B. Wu, S. Tian, Y. Ruan, Z. Cui (2017), “Fuzzy Keyword Search Method over Ciphertexts Supporting Access Control”, KSII Transactions on Internet and Information Systems, 11(11), pp. 5671-5693. [72] M. H. Mohamed, L. M. Mohamed (2016), “High Capacity Image Steganography Technique Based on LSB Substitution Method”, Applied Mathematics & Information Sciences, 10(1), pp. 259-266. [73] G. Navarro (2001), “A Guided Tour to Approximate String Matching”, ACM Computing Surveys, 33 (1), pp. 3188. [74] G. Navarro, M. Raffinot (2000), “Fast and Flexible String Matching by Combining Bit-Parallelism and Suffix Automata”, ACM Journal of Experimental Algorithmics (JEA), 5(4), Article 4. [75] H. K. Pan, Y. Y. Chen, Y. C. Tseng (2000), “A Secret of Data Hiding Scheme for Two- Color Images”, In: Proceedings ISCC 2000. Fifth IEEE Symposium on Computers and Communications, pp. 750-755. [76] K. J. Panchal, F. N. Patel (2014), “Steganography: A Brief Survey”, International Journal of Modern Trends in Engineering and Research, 2(2), pp. 747-750. 85 [77] P. H. Paris, N. Abadie, C. Brando (2017), Linking Spatial Named Entities to The Web of Data for Geographical Analysis of Historical Texts”, Journal of Map & Geography Libraries, 13 (1), pp. 82-110. [78] B. Park, R. Lu (2015), “Hyperspectral Imaging Technology in Food and Agriculture”, Springer. [79] H. Peltola, J. Tarhio (2003), “Alternative Algorithms for Bit-Parallel String Matching”, In: M. A. Nascimento, E. S. de Moura, A. L. Oliveira (Eds.) String Processing and Information Retrieval, 10th International Symposium, SPIRE 2003, Manaus, Brazil, October 8-10, 2003. Proceedings. LNCS-2857, Springer, pp. 80-93. [80] M. V. Ramakrishnan, S. Eswaran (2013), “A Comparative Study of Various Parallel Longest Common Subsequence (LCS) Algorithms”, International Journal of Computer Trends and Technology, 4(2), pp. 183-186. [81] M. I. S. Reddy, A. P. S. Kumar (2016), “Secured Data Transmission Using Wavelet Based Steganography and Cryptography by Using AES Algorithm”, Procedia Computer Science, Vol. 85, pp. 62-69. [82] K. H. Rosen (2012), “Discrete Mathematics and Its Applications” (Seventh Edition), McGraw-Hill. [83] K. Ruohonen (2009), “Formal Languages”, Tampere University of Technology, pp. 1-3. [84] S. S. Sheik, S. K. Aggarwal, A. Poddar, N. Balakrishnan, K. Sekar (2004), “A Fast Pattern Matching Algorithm”, J. Chem. Inf. Comput. Sci., 44 (4), pp. 1251-1256. [85] D. X. Song, D. Wagner, A. Perrig (2000), “Practical Techniques for Searches on Encrypted Data”, In: Proceeding 2000 IEEE Symposium on Security and Privacy, pp. 44. [86] S. Song, J. Zhang, X. Liao, J. Du, Q. Wen (2011), “A Novel Secure Communication Protocol Combining Steganography and Cryptography”, Procedia Engineering, Vol. 15, pp. 2767-2772. [87] C. A. Stanley (2005), “Pairs of Values and The Chi-squared Attack”, Department of Mathematics, Iowa State University, May 1, 2005. [88] D. R. Stinson (1995), “Cryptography: Theory and Practice (CRC Press Series on Discrete Mathematics and Its Application)”, CRC Press. [89] M. Strizhov, Z. Osman, I. Ray (2016), “Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup”, Future Internet, 8(3), 28. [90] D. M. Sunday (1990), “A Very Fast Substring Search Algorithm”, Communications of the ACM, 33(8), pp. 132-142. [91] R. Thathoo, A. Virmani, S. S. Lakshmi, N. Balakrishnan, K. Sekar (2006), “TVSBS: A Fast Exact Pattern Matching Algorithm for Biological Sequences”, Current Sci., 91(1), pp. 47-53. [92] Y. C. Tsengy, H. K. Pan (2001), “Secure and Invisible Data Hiding in 2-Color Images”, Proceedings IEEE INFOCOM, Vol. 2, pp. 887-896. [93] Varsha, R. S. Chhillar (2015), “Data Hiding Using Steganography and Cryptography”, International Journal of Computer Science and Mobile Computing, 4(4), pp. 802-805. 86 [94] R. A. Wagner, M. J. Fischer (1974), “The String-to-String Correction Problem”, J. ACM, 21(1), pp. 168-173. [95] L. Wei, H. Zhu, Z. Cao, X. Dong, W. Jia, Y. Chen, A. Vasilakos (2014), “Security and Privacy for Storage and Computation in Cloud Computing”, Information Sciences, Vol. 258, pp. 371386. [96] R. B. Wolfgang, E. J. Delp (1999), “Fragile Watermarking Using The VW2D Watermark”, Proc. SPIE 3657, Security and Watermarking of Multimedia Contents, pp. 204-213. [97] M. Y. Wu, Y. K. Ho, J. H. Lee (2014), “An Iterative Method of Palette Based Image Steganography”, Pattern Recognition Letters, 25(3), pp. 301-309. [98] S. Wu, U. Manber (1994), “A Fast Algorithm for Multi-Pattern Searching”, Technical Report TR-94-17, University of Arizona, Tucson. [99] X. Xu, L. Chen, Y. Pan, P. He (2005), “Fast Parallel Algorithms for The Longest Common Subsequence Problem Using an Optical Bus”, Computational Science and Its Applications, ICCSA 2005, Proceedings, Part III, Singapore, May 9-12, 2005, pp. 338-348. [100] R.M. Yadav, D. S. Tomar, R. K. Baghel (2014), “A Study on Image Steganography Approaches in Digital Images”, Engineering Universe for Scientific Research and Management, 6(5). [101] J. Yang, Y. Xu, Y. Shang (2010), “An Efficient Parallel Algorithm for Longest Common Subsequence Problem on GPUs”, Proceedings of the World Congress on Engineering, Vol. 1, London, June 30 - July 2, 2010, pp. 499-504. [102] W. Yunling, W. Jianfeng, C. Xiaofeng (2016), “Secure Searchable Encryption: A Survey”, Journal of Communications and Information Networks, 1(4), pp. 52-65. [103] B.B. Zaidan, A. A. Zaidan, A. K. Al-Frajat, H. A. Jalab (2010), “On the Differences between Hiding Information and Cryptography Techniques: An Overview”, Journal of Applied Science, 10(15), pp. 1650-1655. [104] Y. Zhang, J. Jiang, Y. Zha, H. Zhang, S. Zhao (2013), “Research on Embedding Capacity and Efficiency of Information Hiding Based on Digital Images”, International Journal of Intelligence Science, 3(2), pp. 77-85. 87 LIST OF PUBLICATIONS [T1] N. H. Truong (2019), “A New Digital Image Steganography Approach Based on The Galois Field GF (pm) Using Graph and Automata”, KSII Transactions on Internet and Information Systems, 13(9), pp. 4788-4813. (ISI) [T2] N. H. Truong (2019), “A New Approach to Exact Pattern Matching”, Journal of Computer Science and Cybernetics, 35(3), pp. 197-216. [T3] N. H. Truong (2019), “Automata Technique for The LCS Problem”, Journal of Computer Science and Cybernetics, 35(1), pp. 21-37. [T4] N. H. Truong (2019), “A Novel Cryptosystem Based on Steganography and Automata Technique for Searchable Encryption”, KSII Transactions on Internet and Information Systems (revised). (ISI) 88