MINISTRY OF EDUCATION AND TRAINING
HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY
——————————

Nguyen Huy Truong

RESEARCH ON DEVELOPMENT OF METHODS
OF GRAPH THEORY AND AUTOMATA
IN STEGANOGRAPHY AND SEARCHABLE ENCRYPTION

DOCTORAL DISSERTATION IN MATHEMATICS AND INFORMATICS

Hanoi - 2020


MINISTRY OF EDUCATION AND TRAINING
HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY
——————————

Nguyen Huy Truong

RESEARCH ON DEVELOPMENT OF METHODS
OF GRAPH THEORY AND AUTOMATA
IN STEGANOGRAPHY AND SEARCHABLE ENCRYPTION
Major: Mathematics and Informatics
Major code: 9460117

DOCTORAL DISSERTATION IN MATHEMATICS AND INFORMATICS

SUPERVISORS:
1. Assoc. Prof. Dr. Sc. Phan Thi Ha Duong

valuable comments and helpful advice.
I give thanks to PhD students of Late Assoc. Prof. Dr. Phan Trung Huy for sharing
and exchanging information in steganography and searchable encryption.
Finally, I must also thank my family for supporting all my work.


CONTENTS

Page
LIST OF SYMBOLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
LIST OF ABBREVIATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
v
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
CHAPTER 1 PRELIMINARIES . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Basic Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.2 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.3 Deterministic Finite Automata . . . . . . . . . . . . . . . . . . . .
6
m
1.1.4 The Galois Field GF (p ) . . . . . . . . . . . . . . . . . . . . . . .
7

4.2
4.3
4.4
4.5

Mathematical Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Automata Models for Solving The LCS Problem . . . . . . . . . . . . . . .
Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CHAPTER 5 CRYPTOGRAPHY BASED ON STEGANOGRAPHY
AND AUTOMATA METHODS FOR SEARCHABLE ENCRYPTION . .
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 A Novel Cryptosystem Based on The Data Hiding Scheme (2, 9, 8) . . . . .
5.3 Automata Technique for Exact Pattern Matching on Encrypted Data . . .
5.4 Automata Technique for Approximate Pattern Matching on Encrypted Data
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
LIST OF PUBLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

57
61
66
67
68
68
70
74

lcs(p, x)
The length of a LCS(p, x)
LeftID(u)
The least element the leftmost location of u
Rmp (u)
The last component of LeftID(u) in p
(I, M, K, Em, Ex) A data hiding scheme
I
A set of all image blocks with the same size and image format
M
A finite set of secret elements
K
A finite set of secret keys
Em
An embedding function embeds a secret element in an image
block
Ex
An extracting function extracts an embedded secret element
from an image block
qcolour
The number of different ways to change the colour of each
pixel in an arbitrary image block
I
An image block
M
A secret element
K
A secret key
Adjacent(cp , a)
An adjacent vertex of cp

BNDM
CTL
EBOM
ER
FJS
FOPA
FSBNDM
HASH
HCIH
LBNDM
LCS
LSB
MSDR
MSE
NP
OPA
PA
PCT
PSNR
RGB
SA
SAE
SBNDM
SE
SSE
TVSBS
WF
WL

Average Optimal Shift Or

Wu Lee

iv


LIST OF FIGURES

Figure
Figure
Figure
Figure
Figure

1.1.
1.2.
1.3.
1.4.
1.5.

A simple graph . . . . . . . . . . . . . . . . . . .
A spanning tree of the graph given in Figure 1.1
The transition diagram of A in Example 1.3 . .
The basic diagram of digital image steganography
The degree of appearance of the pattern p . . . .

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

Table 2.3. The representation of E and the arc weights of G for the gray image .
Table 2.4. The payload, ER and PSNR for the optimal data hiding scheme
(1, 2n − 1, n) for palette images with qcolour = 1 . . . . . . . . . . . . .
Table 2.5. The payload, ER and PSNR for the near optimal data hiding scheme
(2, 9, 8) for gray images with qcolour = 3 . . . . . . . . . . . . . . . . . .
Table 2.6. The payload, ER and PSNR for the near optimal data hiding scheme
(2, 9, 8) for palette images with qcolour = 3 . . . . . . . . . . . . . . . .
Table 2.7. The comparisons of embedding and extracting time between the
chapter’s and Chang et al.’s approach for the same optimal data hiding
scheme (1, N, ⌊log2 (N + 1)⌋), where N = 2n − 1, for the binary image
with qcolour = 1. Time is given in second unit . . . . . . . . . . . . . .
Table
Table
Table
Table
Table
Table
Table
Table
Table
Table

3.1. The performing steps of the MR1 algorithm . . . . . . . . .
3.2. Experimental results on rand4 problem . . . . . . . . . . .
3.3. Experimental results on rand8 problem . . . . . . . . . . .
3.4. Experimental results on rand16 problem . . . . . . . . . . .
3.5. Experimental results on rand32 problem . . . . . . . . . . .
3.6. Experimental results on rand64 problem . . . . . . . . . . .
3.7. Experimental results on rand128 problem . . . . . . . . . .
3.8. Experimental results on rand256 problem . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

36
37
37

37

.
.
.
.
.
.
.

.
.
.
.
.

30
30
31


INTRODUCTION
In the modern life, when the use of computer and Internet is more and more essential,
digital data (information) can be copied as well as accessed illegally. As a result,
information security becomes increasingly important. There are two popular methods to
provide security, which are cryptography and data hiding [2, 5, 6, 20, 56, 62, 81].
Cryptography is used to encrypt data in order to make the data unreadable by a third
party [5]. Data hiding is used to embed data in digital media. Based on the purpose of
the application, data hiding is generally divided into steganography that hides the
existence of data to protect the embedded data and watermarking that protects the
copyright ownership and authentication of the digital media carrying the embedded data.
Steganography can be used as an alternative way to cryptography.
However,
steganography will become weak if attackers detect existence of hidden data. Hence
integrating cryptography with steganography is as a third choice for data security
[2, 5, 6, 12, 19, 61, 62, 81, 86, 93].
With the rapid development of applications based on Internet infrastructure, cloud
computing becomes one of the hottest topics in the information technology area. Indeed, it
is a computing system based on Internet that provides on-demand services from application
and system software, storage to processing data. For example, when cloud users use the

them to steganography and searchable encryption.
Based on the results and suggestions introduced by P. T. Huy et al., the dissertation
will focus on following four problems in steganography and searchable encryption:
- Digital image steganography;
- Exact pattern matching;
- Longest common subsequence;
- Searchable encryption.
The first problem is stated newly in Chapter 2, the three remaining problems are recalled
and clarified in Chapter 1.
For the first three problems, the dissertation’s work is to find new and efficient solutions
using graph theory and automata. Then they will be used and applied to solve the last
problem.
The dissertation has been completed with structure as follows.
Apart from
Introduction at the beginning and Conclusion at the end of the dissertation, the main
content of it is divided into five chapters.
Chapter 1.
Preliminaries. This chapter recalls basic knowledge indicated
throughout the dissertation (strings, graph, deterministic finite automata, digital images,
the basic model of digital image steganography, some parameters to determine the
quality of digital image steganography, the exact pattern matching problem, the longest
common subsequence problem, and searchable encryption), re-presents important
concepts and results used and researched on development in remaining chapters of the
dissertation (adjacency list, breadth first search, Galois field, the fastest optimal parity
assignment method, the module method and the concept of the maximal secret data
ratio, the concept of the degree of fuzziness (appearance), the Knapsack Shaking
approach, and the definition of a cryptosystem).
Chapter 2. Digital image steganography based on the Galois field using
graph theory and automata. Firstly, from some proposed concepts of optimal and
near optimal secret data hiding schemes, this chapter states the interest problem in digital

secret data, respectively. In searchable encryption, the cryptosystem can be used to encode
and decode secret data on users side and pattern matching algorithms can be used to
perform pattern search on cloud providers side.
The contents of the dissertation are written based on the paper [T1] published in,
the revised manuscript [T4] submitted to KSII Transactions on Internet and Information
Systems (ISI), and the papers [T2, T3] published in Journal of Computer Science and
Cybernetics in 2019. The main results of the dissertation have been presented at:
- Seminar on Mathematical Foundations for Computer Science at Institute of
Mathematics, Vietnam Academy of Science and Technology,
- The 9th Vietnam Mathematical Congress, Nha Trang, August 14-18, 2018,
- Seminar at School of Applied Mathematics and Informatics, Hanoi University of
Science and Technology.

3


CHAPTER 1

PRELIMINARIES
This chapter will attempt to recall terminologies, concepts, algorithms and results which
are really needed in order to present the dissertation’s new results clearly and logically,
as well as help readers follow the content of the dissertation easily. The background
knowledge re-presented here consists of basic structures (Section 1.1: strings (Subsection
1.1.1), graph (Subsection 1.1.2), deterministic finite automata (Subsection 1.1.3), and the
Galois field GF (pm ) (Subsection 1.1.4)), digital image steganography (Section 1.2), exact
pattern matching (Section 1.3 ), longest common subsequence (Section 1.4) and searchable
encryption (Section 1.5).

1.1 Basic Structures
1.1.1 Strings

edge {i, j}.
Two vertices i and j in a graph G are called adjacent if they are vertices of an edge of
G.
A graph without multiple edges can be described by using adjacency lists, which specify
adjacent vertices of any vertex of the graph.
Example 1.1. Using adjacency lists, the simple graph given in Figure 1.1 can be
represented as in Table 1.1.

2

4

1
5

3
Figure 1.1. A simple graph

Table 1.1. An adjacency list representation of the simple graph given in Figure 1.1

Vertex

Adjacent vertices

1

2, 3

2


If (j is not in L and T )
{
Add j to the end of L;
Add j and the edge {i, j} to T ;
}
}
Return T ;
End.
Example 1.2. For a graph given in Figure 1.1, a spanning tree of this graph is found by
using BFS as in Figure 1.2.

1

2

3

4

5

Figure 1.2. A spanning tree of the graph given in Figure 1.1

A graph with directed edges (or arcs) is called a directed graph. Each arc is associated
with the ordered pair of vertices. In a simple directed graph, the arc associated with the
ordered pair (i, j) called the arc (i, j). And the vertex i is said to be adjacent to the vertex
j and the vertex j is said to be adjacent from the vertex i.
1.1.3 Deterministic Finite Automata
Study on the problem of the construction and the use of deterministic finite automata
is one of objectives of the dissertation. Hence, this subsection will clarify this model of


a

b

q0

q0

q1

q1

q2

q1

q2

q2

q2

a

q0

a, b

b

and multiplication in Zp [x]/(f (x)) are given as in Zp [x], followed by a reduction modulo
f (x). Then Zp [x]/(f (x)) with these operations is a field having pm elements, called the
Galois field GF (pm ). Note that for p is prime and m ≥ 1, the Galois field GF (pm ) is
unique.

1.2 Digital Image Steganography
The interest problem in Chapter 2 is digital image steganography. This section will
recall the concept of digital images, the basic model of digital image steganography, some
parameters to determine the efficiency of digital image steganography and lastly re-present
results researched on development and used in Chapter 2 such as the fastest optimal parity
assignment (FOPA) method, the module method and the concept of the maximal secret
data ratio (MSDR) [18, 20, 21, 39, 49, 50, 51, 53, 61, 63, 65, 76, 78, 104].
A digital image is a matrix of pixels. Each pixel is represented by a non negative integer
number in the form of a string of binary bits. This value indicates the colour of the pixel
[39].
Note that based on the way representing of colours of pixels, digital images can be
divided into following different types [78].
1. Binary image: Each pixel is represented by one bit. In this image type, the colour of
a pixel is white, “1” value, or black, “0” value.
2. Gray image: Each pixel is typically represented by eight bits (called 8-bit gray image).
Then the colour of any pixel is a shade of gray, from black corresponding to colour value
“0” to white corresponding to colour value “255”.
3. Red green blue image: Each pixel is usually represented by a string of 24 bits (called
24-bit RGB image), where the first 8 bits, the next 8 bits and the last 8 bits corresponds
to shades of red, green and blue, specifying the red, green and blue colour components
of the pixel, respectively. Then the colour of the pixel is a combination of these three
components.
4. Palette image: The colour of each pixel is not shown directly by the number
representing the pixel as for RGB images. Instead, this number is a colour index of the
colour of the pixel existed in the colour table (the palette), an ordered set of values (strings

Secret Data
Communication
Channel

Cover
Image

Embed

Stego
Image

Stego
Image

Extract

Send to

Secret Key

Secret Key

Sender

Receiver

Figure 1.4. The basic diagram of digital image steganography

The peak signal to noise ratio (PSNR) is used to evaluate quality of stego image. Based

of a pixel of G corresponding to the colour index i. Each colour c in P is considered as a
vector consisting of red, green and blue components. Suppose d is a distance function on P .
The FOPA method [50] tries to get functions Next, Next: P → P , and Val, Val: P → Z2 ,
where two conditions are satisfied for all c ∈ P as follows.
9


1. d(c, Next(c)) = minv=c∈P d(c, v),
2. Val(c) =Val(Next(c)) + 1 on the field Z2 .
Call GP = (VP , EP ) a weighted complete undirected graph of the palette image G, where
VP = P and the weight of the edge {c, c′ } is d(c, c′ ). The function Nearest, Nearest: P → P ,
is given by Nearest(c) = c′ holding d(c, c′ ) = minv=c∈P d(c, v). A rho forest F = (V, E) is
a directed graph with vertices weighted by the functionVal, where V = VP , E is a set of
all arcs (v, Next(v)), the vertex v has the weightVal(v) for all v ∈ V . The construction of
a algorithm determining F is the essence of the FOPA method.
Algorithm for FOPA:
Input: A weighted complete undirected graph GP , the function Nearest.
Output: A rho forest F = (V, E).
Choose a vertext c ∈ P , set V = {c}, and set C = P \{c};
SetVal(c) = 0; // Or 1 randomly
While (C is not empty) // Update F
{
a) Take one element v ∈ C;
b) Initialize v0 = v, setVal(v0 ) = 0 (or 1 randomly), by a finite loop, find a longest
sequence of k + 1 different elements in P consecutively, v0 , v1 , . . . , vk , such that
Nearest(vi ) = vi+1 for ∀i = 0, k − 1, vi ∈ C, vk ∈ C or vk ∈ V , and set
Next(vi ) = vi+1 , i = 0, k − 1;
b1) Case vk ∈ C: SetVal(vi ) = 1+Val(vi−1 ), i = 1, k and Next(vk ) = vk−1 ;
Set V = V ∪ {v0 , v1 , . . . , vk } and C = C\{v0 , v1 , . . . , vk };
b2) Case vk ∈ F : SetVal(vi ) = 1+Val(vi+1 ), i = k − 1, . . . , 1, 0;

The block Extract (extracting d from I ′ ): d = i=1 h(Ii′ )(Val(Ii′ ) + Ki );
Definition 1.4 ([49]). MSDR k (N ) is the largest number of embedded bits of secret data
in an image block of N pixels by changing colours of at most k pixels in the image block,
where k, N are positive integers.
Given a positive integer qcolour , call qcolour the number of different ways to change the
colour of each pixel in an arbitrary image block of N pixels. According to [49]
1
2
2
k
k
MSDR k (N ) = ⌊log2 (1 + qcolour CN
+ qcolour
CN
+ · · · + qcolour
CN
)⌋.

(1.3)

1.3 Exact Pattern Matching
This section will restate the exact pattern matching problem, and recall the concept of
the degree of fuzziness (appearance) used in Chapter 3 [24, 52, 68].
Let x be a string of length n. Denote the substring x[i]x[i + 1]..x[j] of x by x[i..j]
for ∀1 ≤ i ≤ j ≤ n, the ith element of x by x[i] and i is called a position in x. Let
p be a substring of length m of x, where m is a positive integer, then there exists i for
1 ≤ i ≤ n − m + 1 such that p = x[i..i + m − 1]. And say that i is an occurrence of p in x
or p occurs in x at position i.
Definition 1.5 ([68]). Let p be a pattern of length m and x be a text of length n over
the alphabet Σ. Then the exact pattern matching problem is to find all occurrences of the


f

a

h

3

p

f

a

h

4

p

f

a

h

5

p


f

a

11

f

k

f

a

h

a

h


Example 1.4. Given a pattern p = fah and a text x = dfahfkfaha. Then there are two
occurrences of p in x as shown below: dfahfkfaha. The BF algorithm is performed by the
following steps presented in Table 1.2, the bold letters correspond to the mismatches, the
underlined letters represent the matches when comparing the letters of the pattern and
the text. We know that many letters scanned will be scanned again by the BF algorithm
because each time either a mismatch or a match occurs, the pattern is only moved to the
right one position.
Chapter 3 uses the degree of fuzziness in [52] to determine the longest prefix of the

Definition 1.8 ([101]). Let u, p and x be strings over the alphabet Σ. Then u is a common
subsequence of p and x if u is a subsequence of p and a subsequence of x.
Definition 1.9 ([101]). Let u, p and x be strings over the alphabet Σ. Then u is a longest
common subsequence of p and x if two following conditions are satisfied.
(i) u is a common subsequence of p and x,
(ii) There does not exist any common subsequence v of p and x such that |v| > |u|.
12


Denote an arbitrary longest common subsequence of p and x by LCS(p, x). The length
of a LCS(p, x) is denoted by lcs(p, x).
By convention, if two strings p and x does not have any longest common subsequences,
then the lcs(p, x) is considered to equal 0.
Example 1.5. Let p = bgcadb and x = abhcbad. Then string bcad is a LCS(p, x) and
lcs(p, x) = 4.
Let p and x be two strings of lengths m and n over the alphabet Σ, m ≤ n. The longest
common subsequence problem for two strings (LCS problem) can be stated in two following
forms [24, 47].
Problem 1. Find a longest common subsequence of p and x.
Problem 2. Compute the length of a longest common subsequence of p and x.
The simple way to solve the LCS problem is to use the algorithm introduced by
Wagner and Fischer in 1974 (called the Algorithm WF). This algorithm defines a dynamic
programming matrix L(m, n) recursively to find a LCS(p, x) and compute the lcs(p, x) as
follows [94].


i = 0 or j = 0,
0
L(i, j) = L(i − 1, j − 1) + 1
p[i] = x[j],

a
1
0
0
0
0
1
1
1

b
2
0
1
1
1
1
1
2

h
3
0
1
1
1
1
1
2


d
7
0
1
1
2
3
4
4

Definition 1.10 ([47]). Let u = p[j1 ]p[j2 ] . . . p[jt ] be a subsequence of p. Then an element
of the form (j1 , j2 , . . . , jt ) is called a location of u in p.
From Definition 1.10, the subsequence u has at least a location in p. If all the different
locations of u are arranged in the dictionary order, then call the least element the leftmost
location of u, denoted by LeftID(u). Denote the last component of LeftID(u) by Rmp (u)
[47].

13


Example 1.7. Let p = aabcadabcd and u = abd. Then u is a subsequence of p and has
seven different locations in p, in the dictionary order they are
(1, 3, 6), (1, 3, 10), (1, 8, 10), (2, 3, 6), (2, 3, 10), (5, 8, 10), (7, 8, 10).
It follows that LeftID(u) = (1, 3, 6) and Rmp (u) = 6.
Definition 1.11 ([47]). Let p be a string of length m. Then a configuration C of p is
defined as follows.
1. Or C is the empty set. Then C is called the empty configuration of p, denoted by
C0 .
2. Or C = {x1 , x2 , . . . , xt } is an ordered set of t subsequences of p for 1 ≤ t ≤ m such
that the two following conditions are satisfied.

• The set of states Q = Config(p),
14


• The initial state q0 = C0 ,
• The transition function ϕ is given as in Definition 1.12,
• The set of final states F = {Cn }, where Cn = ϕ(q0 , x).
Suppose Cn = {x1 , x2 , . . . , xt } for 1 ≤ t ≤ m. Then
1. For every subsequence u of p and x, there exists xi ∈ Cn , 1 ≤ i ≤ t such that the two
following conditions are satisfied.
(i) |u| = |xi |,
(ii) Rm p (xi ) ≤ Rm p (u).
2. A LCS(p, x) equals xt .

1.5 Searchable Encryption
This section clarifies the term of searchable encryption (SE) and recalls the definition
of a cryptosystem. They will be studied and used in Chapter 5 [26, 40, 60, 85, 88, 102].
Consider a problem to occur in cloud security as follows [60, 85, 102]. Cloud tenants, for
example enterprises and individuals with limited resource including software and hardware,
store data with sensitive information on cloud servers. Assume that these servers cannot
be fully trusted. This means they may not only be curious about the users’ information
but also abuse the data received. Then users wish to encrypt their data before uploading
them to servers. Because of limitations of cloud users’ information technology system,
users also wish that cloud providers can help them perform information search directly
on ciphertexts. However, encryption brings difficulties for servers to do search on the
encrypted data. These lead to a problem that is to find a solution to satisfy the two wishes
of cloud users when they choose cloud storage service.
SE is a way to solve the above problem. It is indeed a system consisting of two
main components, a cryptosystem is used to encode and decode on cloud users side and
algorithms for searching on encrypted data are done on cloud providers side [40, 102].