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
2. Dr. Vu Thanh Nam
Hanoi - 2020
DECLARATION OF AUTHORSHIP
I hereby certify that I am the author of this dissertation, and that I have completed it
under the supervision of Assoc. Prof. Dr. Sc. Phan Thi Ha Duong and Dr. Vu Thanh
Nam. I also certify that the dissertation’s results have not been published by other authors.
Hanoi, February 03, 2020
PhD. Student
Nguyen Huy Truong
Supervisors
Assoc. Prof. Dr. Sc. Phan Thi Ha Duong Dr. Vu Thanh Nam
ACKNOWLEDGMENTS
I am extremely grateful to Assoc. Prof. Dr. Sc. Phan Thi Ha Duong.
I want to thank Dr. Vu Thanh Nam.
I would also like to extend my deepest gratitude to Late Assoc. Prof. Dr. Phan Trung
Huy.
I would like to thank my co-workers from School of Applied Mathematics and
Informatics, Hanoi University of Science and Technology for all their help.
I also wish to thank members of Seminar on Mathematical Foundations for Computer
Science at Institute of Mathematics, Vietnam Academy of Science and Technology for their
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
1.1.4 The Galois Field GF (pm) . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Digital Image Steganography . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Exact Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Longest Common Subsequence . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Searchable Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
CHAPTER 2 DIGITAL IMAGE STEGANOGRAPHY BASED ON THE
GALOIS FIELD USING GRAPH THEORY AND AUTOMATA ..... 16
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 The Digital Image Steganography Problem . . . . . . . . . . . . . . . . . . 18
2.3 A New Digital Image Steganography Approach . . . . . . . . . . . . . . . . 19
2.3.1 Mathematical Basis based on The Galois Field . . . . . . . . . . . . 19
2.3.2 Digital Image Steganography Based on The Galois Field GF (pm)
Using Graph Theory and Automata . . . . . . . . . . . . . . . . . . 21
2.4 The Near Optimal and Optimal Data Hiding Schemes for Gray and Palette
Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
CHAPTER 3 AN AUTOMATA APPROACH TO EXACT PATTERN
MATCHING .................................. 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 The New Algorithm - The MRcAlgorithm . . . . . . . . . . . . . . . . . . 41
3.3 Analysis of The MRcAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
CHAPTER 4 AUTOMATA TECHNIQUE FOR THE LONGEST
COMMON SUBSEQUENCE PROBLEM . . . . . . . . . . . . . . . . . . 56
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
i
