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; K0; 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) 2 K0.
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

98 trang |

Chia sẻ: tueminh09 | Ngày: 25/01/2022 | Lượt xem: 115 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu **Research on development of methods of graph theory and automata in steganography and searchable encryption**, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

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