Tổng quan luận án

Trong kỷ nguyên số hóa và sự phát triển của mạng Internet, dữ liệu số đối mặt với nguy cơ bị sao chép và truy cập trái phép, khiến vấn đề an toàn thông tin trở nên cấp thiết. Hai giải pháp kỹ thuật phổ biến để bảo vệ dữ liệu là mật mã học (cryptography) và giấu dữ liệu (data hiding). Trong khi mật mã học biến đổi dữ liệu thành dạng không thể đọc được nhằm ngăn chặn bên thứ ba, giấu dữ liệu nhúng thông tin vào các phương tiện số. Giấu dữ liệu gồm hai nhánh chính: giấu tin (steganography) nhằm che giấu sự tồn tại của thông điệp bí mật và thủy vân số (watermarking) nhằm bảo vệ bản quyền, xác thực quyền sở hữu phương tiện số. Khi các kỹ thuật phát hiện giấu tin ngày càng hoàn thiện, việc tích hợp mật mã học và giấu tin trở thành giải pháp gia tăng mức độ an toàn.

Bên cạnh đó, sự bùng nổ của điện toán đám mây cho phép người dùng cá nhân và doanh nghiệp thuê ngoài hạ tầng lưu trữ và tính toán. Tuy nhiên, tính riêng tư của dữ liệu bị đe dọa khi máy chủ đám mây không hoàn toàn đáng tin cậy. Để bảo vệ dữ liệu nhạy cảm, người dùng mã hóa dữ liệu trước khi tải lên máy chủ. Việc mã hóa gây trở ngại lớn cho việc tìm kiếm trực tiếp trên dữ liệu mã hóa. Mã hóa tìm kiếm được (Searchable Encryption - SE) ra đời nhằm giải quyết bài toán lưu trữ an toàn kết hợp khả năng tìm kiếm thông tin trực tiếp trên bản mã mà không cần giải mã trước.

Luận án tiến sĩ toán học và tin học của tác giả Nguyễn Huy Trương với tiêu đề "Research on Development of Methods of Graph Theory and Automata in Steganography and Searchable Encryption" (Nghiên cứu phát triển phương pháp lý thuyết đồ thị và tự động trong giấu tin và mã hóa tìm kiếm được), mã ngành 9460117, được hoàn thành năm 2020 tại Trường Đại học Bách khoa Hà Nội dưới sự hướng dẫn khoa học của PGS. Phan Thị Hà Dương và TS. Vũ Thành Nam. Luận án kế thừa, phát triển các phương pháp lý thuyết đồ thị và mô hình tự động hữu hạn từ các công trình trước đó của Phan Trung Huy và cộng sự (2002, 2011, 2012, 2013) để giải quyết bốn bài toán trọng tâm:

  1. Bài toán giấu tin trong ảnh số (Digital image steganography).
  2. Bài toán khớp mẫu chính xác (Exact pattern matching).
  3. Bài toán dãy con chung dài nhất (Longest common subsequence - LCS).
  4. Bài toán mã hóa tìm kiếm được (Searchable encryption).

Mục tiêu nghiên cứu của luận án được xác định cụ thể:

  • Mục tiêu 1: Xây dựng cơ sở toán học dựa trên trường Galois $GF(p^m)$, kết hợp lý thuyết đồ thị và tự động hữu hạn để thiết kế các lược đồ giấu tin tối ưu và gần tối ưu trên ảnh nhị phân, ảnh xám và ảnh palette.
  • Mục tiêu 2: Phát triển thuật toán khớp mẫu chính xác sử dụng kỹ thuật tự động nhằm tối ưu hóa cơ chế dịch chuyển cửa sổ trượt và cập nhật mức xuất hiện của mẫu trong văn bản.
  • Mục tiêu 3: Xây dựng các thuật toán tuần tự và song song tính độ dài dãy con chung dài nhất ($lcs$) dựa trên mô hình tự động.
  • Mục tiêu 4: Thiết kế hệ mật mã mới dựa trên lược đồ giấu tin và tích hợp các thuật toán tự động để thực hiện tìm kiếm chính xác và tìm kiếm xấp xỉ trên dữ liệu mã hóa phục vụ mã hóa tìm kiếm được trong môi trường điện toán đám mây.

Đối tượng và phạm vi nghiên cứu của luận án:

  • Đối tượng nghiên cứu: Cấu trúc đại số trường Galois $GF(p^m)$, không gian vectơ $GF^n(p^m)$, đồ thị lật (flip graph), tự động hữu hạn đơn định (Deterministic Finite Automata - DFA), các định dạng ảnh số (ảnh nhị phân, ảnh xám 8-bit, ảnh palette 8-bit), xâu ký tự, chuỗi sinh học và hệ thống mật mã tìm kiếm được đối xứng (SSE).
  • Phạm vi nghiên cứu: Nghiên cứu tập trung vào kỹ thuật giấu tin trong miền không gian (spatial domain); khớp mẫu đơn chính xác; tính độ dài dãy con chung dài nhất của hai chuỗi; và xây dựng mô hình mã hóa tìm kiếm được đối xứng trong đó việc mã hóa được thực hiện ở phía người dùng (user) và việc tìm kiếm trên bản mã được thực hiện ở phía máy chủ đám mây (cloud provider).

Tổng quan tài liệu và vị trí của luận án

Luận án tiến hành tổng quan các công trình nghiên cứu trong các lĩnh vực liên quan:

Trong lĩnh vực giấu tin trên ảnh số miền không gian, phương pháp thay thế bit có trọng số thấp nhất (LSB) là phương pháp phổ biến cho ảnh màu RGB 24-bit và ảnh xám 8-bit nhưng dễ bị tổn thương trước các tấn công bảo mật. Đối với ảnh palette, phương pháp EZ Stego gặp hạn chế về chất lượng ảnh stego. Để khắc phục, Fridrich (1999) đề xuất phương pháp gán tính chẵn lẻ (Parity Assignment - PA), sau đó Fridrich và cộng sự (2000) cải tiến thành phương pháp gán tính chẵn lẻ tối ưu (Optimal Parity Assignment - OPA). Đến năm 2013, Phan Trung Huy và cộng sự đề xuất phương pháp gán tính chẵn lẻ tối ưu nhanh nhất (Fastest Optimal Parity Assignment - FOPA) dựa trên cấu trúc rừng rho (rho forest) để kiểm soát chất lượng ảnh. Đối với ảnh nhị phân, các lược đồ dựa trên khối như lược đồ WL (Wu và cộng sự, 1998), PCT (Pan và cộng sự, 2000), modified PCT (Tseng và cộng sự, 2001) và CTL (Chang, Tseng, Lin, 2005) được sử dụng để duy trì chất lượng ảnh. Năm 2011 và 2012, Phan Trung Huy và cộng sự đề xuất phương pháp mô-đun (module method) và khái niệm tỷ lệ dữ liệu bí mật cực đại (Maximal Secret Data Ratio - MSDR).

Trong lĩnh vực khớp mẫu chính xác, từ hai công trình nền tảng của Boyer - Moore (1977) và Knuth - Morris - Pratt (1977), bài toán đã thu hút nhiều nghiên cứu. Lecroq đã khảo sát 85 thuật toán trong giai đoạn 2000 - 2010 và xác định 10 thuật toán tuần tự hiệu quả trong thực nghiệm: AOSO, EBOM, FJS, FSBNDM, $\text{HASH}q$, LBNDM, SA, BMH-SBNDM, $\text{SBNDM}q$, TVSBS. Các thuật toán này chủ yếu vận hành dựa trên cơ chế cửa sổ trượt (sliding window). Năm 2002, Phan Trung Huy và cộng sự đề xuất khái niệm mức độ mờ (degree of fuzziness), trong luận án này được chuẩn hóa lại thành mức xuất hiện (degree of appearance).

Trong bài toán dãy con chung dài nhất (LCS), thuật toán quy hoạch động kinh điển của Wagner và Fischer (1974) sử dụng ma trận $L(m,n)$. Năm 2002, Phan Trung Huy và cộng sự giới thiệu cách tiếp cận rung ba lô (Knapsack Shaking approach) dựa trên tự động hữu hạn để xác định cấu hình và tìm kiếm LCS.

Trong lĩnh vực mã hóa tìm kiếm được (SE), các nghiên cứu phát triển từ năm 2000 chia thành hai hướng: mã hóa tìm kiếm được đối xứng (SSE) và mã hóa tìm kiếm được bất đối xứng (SAE). Stinson (2006) chuẩn hóa định nghĩa hệ mật mã 5 thành phần $(P, C, K, E, D)$.

Khoảng trống nghiên cứu được luận án xác định:

  1. Thiếu một khung lý thuyết tổng quát kết hợp cấu trúc đại số trường Galois $GF(p^m)$, lý thuyết đồ thị và mô hình tự động để thiết kế các lược đồ giấu tin đạt mức tối ưu hoặc gần tối ưu cho nhiều loại ảnh số khác nhau (nhị phân, xám, palette).
  2. Các thuật toán khớp mẫu hiện có chưa tận dụng linh hoạt mối quan hệ giữa kích thước mẫu và kích thước bảng chữ cái, chưa cập nhật tức thời mức xuất hiện của tiền tố mẫu tại vị trí duyệt, dẫn đến việc quét lặp lại các ký tự khi các cửa sổ trượt gối lên nhau.
  3. Cần các thuật toán tuần tự và song song tối ưu hóa thời gian tính độ dài LCS trên chuỗi kích thước lớn thông qua kỹ thuật tự động.
  4. Trong các kỹ thuật lai giữa mật mã và giấu tin cho SE, kích thước bản mã thường phụ thuộc vào kích thước ảnh đầu vào, các bước mã hóa và nhúng thực hiện tách rời, đồng thời thiếu các giải pháp tìm kiếm mẫu chính xác và xấp xỉ có độ phức tạp thời gian tuyến tính $O(n)$ trên dữ liệu mã hóa.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án sử dụng các hệ thống lý thuyết, khái niệm và công cụ phân tích toán học - tin học chuẩn xác:

  • Lý thuyết xâu ký tự và tự động hữu hạn: Bảng chữ cái $\Sigma$, tập tất cả các xâu $\Sigma^$, xâu rỗng $\epsilon$, độ dài xâu $|x|$. Tự động hữu hạn đơn định $A = (\Sigma, Q, q_0, \delta, F)$ với tập trạng thái $Q$, trạng thái ban đầu $q_0$, tập trạng thái kết thúc $F$, hàm chuyển trạng thái $\delta: Q \times \Sigma \to Q$ và hàm chuyển mở rộng $\delta: Q \times \Sigma^ \to Q$.
  • Lý thuyết đồ thị: Đồ thị vô hướng $G = (V, E)$, danh sách kề, thuật toán tìm kiếm theo chiều rộng (BFS) để xây dựng cây khung, đồ thị có hướng (digraph), đồ thị lật (flip graph) trên trường Galois.
  • Đại số trừu tượng và Trường Galois: Trường hữu hạn $GF(p^m)$ xây dựng từ vành đa thức $\mathbb{Z}_p[x]$ rút gọn theo đa thức bất khả quy bậc $m$, không gian vectơ $n$ chiều $GF^n(p^m)$ trên trường $GF(p^m)$. Khái niệm lớp phần tử $[x] = {ax \mid a \in GF(p^m)\setminus{0}}$, tập các lớp $[GF^n(p^m)]$, tập sinh $k$-Generators và $k$-[Generators].
  • Các tham số và mô hình giấu tin: Lược đồ giấu tin dạng khối $(I, M, K, Em, Ex)$; sai số toàn phương trung bình ($MSE$); tỉ số tín hiệu trên tạp âm đỉnh ($PSNR = 10 \log_{10}(255^2 / MSE)$ dB); tỉ lệ nhúng $ER = \text{Payload} / (W \times H)$ (bit trên pixel - bpp); số cách thay đổi màu sắc pixel $q_{\text{colour}}$; tỷ lệ dữ liệu bí mật cực đại $MSDR_k(N)$.
  • Hệ mật mã học: Bộ 5 thành phần $(P, C, K, E, D)$ thỏa mãn điều kiện giải mã đúng $d_k(e_k(x)) = x$ với mọi bản rõ $x \in P$ và khóa $k \in K$.

Phương pháp nghiên cứu thực nghiệm và công cụ:

  • Các thuật toán giấu tin, khớp mẫu và LCS được cài đặt bằng ngôn ngữ lập trình C# trên môi trường Microsoft Visual Studio 2010.
  • Cấu hình phần cứng thử nghiệm: Hệ điều hành Windows 7 64-bit, bộ vi xử lý Intel Core i3 2.20GHz, bộ nhớ trong 4 GB RAM.
  • Dữ liệu thử nghiệm bao gồm: 9 ảnh xám chuẩn kích thước $512 \times 512$ pixel và 9 ảnh palette chuẩn kích thước $512 \times 512$ pixel (Airplane, Baboon, Barbara, Boats, Goldhill, Lenna, Peppers, Tiffany, Zelda); 1 ảnh nhị phân kích thước $2592 \times 1456$ pixel; các tập chuỗi ngẫu nhiên rand4, rand8, rand16, rand32, rand64, rand128, rand256; chuỗi sinh học thực tế gồm chuỗi hệ gen ($|\Sigma| = 4$) và chuỗi protein ($|\Sigma| = 20$); dữ liệu tính LCS với độ dài chuỗi $n = 50666$ và $n = 102398$.

Nội dung chính theo từng chương

CHAPTER 1 PRELIMINARIES

Chương 1 hệ thống hóa các khái niệm, ký hiệu và kết quả lý thuyết nền tảng được sử dụng xuyên suốt luận án:

  • Định nghĩa xâu ký tự, ghép xâu, tiền tố, hậu tố, xâu con.
  • Biểu diễn đồ thị bằng danh sách kề và thuật toán tìm kiếm theo chiều rộng (BFS) để tìm cây khung.
  • Mô hình tự động hữu hạn đơn định DFA $A = (\Sigma, Q, q_0, \delta, F)$ và biểu đồ chuyển trạng thái.
  • Cấu trúc trường Galois $GF(p^m)$ được xây dựng từ vành đa thức $\mathbb{Z}_p[x]$ modulo đa thức bất khả quy $f(x)$.
  • Mô hình giấu tin ảnh số: Định nghĩa các loại ảnh (nhị phân, xám 8-bit, RGB 24-bit, palette 8-bit); sơ đồ cơ bản của giấu tin ảnh; các tham số đánh giá chất lượng gồm Payload, ER, MSE và PSNR (ngưỡng phân biệt của mắt người là 30 dB). Trình bày thuật toán FOPA xây dựng rừng rho trên đồ thị màu palette và phương pháp mô-đun trên vành $\mathbb{Z}_2$ của Phan Trung Huy và cộng sự cùng khái niệm $MSDR_k(N)$.
  • Bài toán khớp mẫu chính xác: Phân tích thuật toán Brute Force (BF) và định nghĩa mức xuất hiện (degree of appearance) của mẫu $p$ tại vị trí $i$ trong văn bản $x$.
  • Bài toán dãy con chung dài nhất (LCS): Thuật toán Wagner - Fischer (WF) với bảng quy hoạch động ma trận $L(m,n)$; định nghĩa vị trí ngoài cùng bên trái $LeftID(u)$, thành phần cuối $Rm_p(u)$, cấu hình $Config(p)$, hàm chuyển $\phi$ và phương pháp Knapsack Shaking của Phan Trung Huy và cộng sự (2002).
  • Khái niệm mã hóa tìm kiếm được (SE), phân loại SSE/SAE và định nghĩa toán học chuẩn của hệ mật mã $(P, C, K, E, D)$.

CHAPTER 2 DIGITAL IMAGE STEGANOGRAPHY BASED ON THE GALOIS FIELD USING GRAPH THEORY AND AUTOMATA

Chương 2 trình bày phương pháp tiếp cận mới trong giấu tin ảnh số dựa trên trường Galois $GF(p^m)$, lý thuyết đồ thị và tự động:

  • Xây dựng cơ sở toán học: Không gian vectơ $GF^n(p^m)$, phân hoạch thành các lớp $[GF^n(p^m)]$ với số lượng phần tử $|[GF^n(p^m)]\setminus{0}| = \frac{p^{mn}-1}{p^m-1}$. Định nghĩa $k$-Generators và $k$-[Generators]. Chứng minh nếu có $c$ tập $k$-[Generators] gồm $N$ phần tử thì số tập $k$-Generators gồm $N$ phần tử là $c(p^m-1)^N$.
  • Mô hình đồ thị lật và tự động: Định nghĩa đồ thị lật $G=(V,E)$ trên trường $GF(p^m)$ với hàm gán trọng số đỉnh $Val: V \to GF(p^m)$ và cung $(c_p, c'_p)$ có trọng số $a$ thỏa mãn $Val(c'_p) = Val(c_p) + a$. Xây dựng tự động $A(I,M,K)$ với hàm nhúng $Em$ và hàm trích xuất $Ex$.
  • Thiết kế lược đồ tổng quát và chứng minh sự tồn tại:
    • Chứng minh sự tồn tại của lược đồ giấu tin tổng quát $(k, N, \lfloor\log_2 p^{mn}\rfloor)$.
    • Chứng minh sự tồn tại của lược đồ tối ưu $(1, \frac{p^{mn}-1}{p^m-1}, \lfloor\log_2 p^{mn}\rfloor)$ với $q_{\text{colour}} = p^m - 1$.
    • Chứng minh sự tồn tại của lược đồ tối ưu $(1, 2^n-1, n)$ với $q_{\text{colour}} = 1$ cho ảnh nhị phân, ảnh xám và ảnh palette (khẳng định lược đồ CTL của Chang và cộng sự đạt tối ưu khi $N = 2^n - 1$).
    • Chứng minh điều kiện tồn tại của lược đồ tối ưu bậc hai: $$N_{\text{optimum}} = \left\lceil \frac{\frac{p^m-3}{2} + \sqrt{\frac{(p^m-3)^2}{4} + 2(2^{\lfloor\log_2 p^{mn}\rfloor}-1)}}{p^m-1} \right\rceil$$
  • Quy trình giấu chuỗi dữ liệu: Đề xuất thuật toán nhúng $EmDF$ và trích xuất $ExDF$ cho chuỗi dữ liệu bí mật $D$ vào ảnh $F$ thông qua hàm song ánh $Jump$, hàm song ánh $f$ và tập khóa $K = {K^1, K^2, \dots, K^{t_1}}$. Phân tích an toàn chống tấn công vét cạn với số tổ hợp khóa và hàm là: $$c(p^m-1)^N N! , p^{m t_1 N} , t_2! , C_{p^{mn}}^{2^r} (2^r)!$$
  • Các lược đồ cụ thể cho ảnh xám và palette với $q_{\text{colour}} = 3$: Xét trường hữu hạn $GF(2^2)$ xây dựng từ đa thức $g(x) = x^2 + x + 1$ trên $\mathbb{Z}_2[x]$, biểu diễn dưới dạng nhị phân và thập phân ${0, 1, 2, 3}$. Với $n=4$, không gian vectơ $GF^4(2^2)$ có 256 phần tử. Luận án kiểm chứng không tồn tại 2-[Generators] với $N=8$, nhưng với $N=9$ tìm được $c \approx 2^{20}$ tập sinh, từ đó xây dựng lược đồ gần tối ưu $(2, 9, 8)$ và lược đồ tối ưu $(1, 5, 4)$.
  • Kết quả thực nghiệm:
Lược đồ / Loại ảnh Thông số Payload (bit) Tỉ lệ nhúng ER (bpp) PSNR trung bình (dB)
Lược đồ $(2, 9, 8)$ trên ảnh xám ($q_{\text{colour}} = 3$) 225.408 0,86 55,84
Lược đồ $(1, 2^n-1, n)$ trên ảnh palette ($q_{\text{colour}} = 1$) Biến thiên Chọn phù hợp > 30,00
Lược đồ $(2, 9, 8)$ trên ảnh palette ($q_{\text{colour}} = 3$) Biến thiên (5.576 – 9.144) 0,02 – 0,09 > 30,00

Thực nghiệm so sánh trên ảnh nhị phân kích thước $2592 \times 1456$ pixel cho thấy thời gian nhúng và trích xuất của phương pháp đề xuất (BOO) nhanh hơn phương pháp CTL của Chang và cộng sự khoảng 3,24 lần. So với lược đồ HCIH trên ảnh xám (ER = 0,75 bpp, PSNR = 46,33 dB), lược đồ gần tối ưu $(2, 9, 8)$ đạt hiệu năng cao hơn cả về tỉ lệ nhúng (0,86 bpp) lẫn chất lượng ảnh (55,84 dB).

CHAPTER 3 AN AUTOMATA APPROACH TO EXACT PATTERN MATCHING

Chương 3 tập trung vào bài toán khớp mẫu đơn chính xác:

  • Phân tích 10 thuật toán đối sánh: Khảo sát cơ chế cửa sổ trượt của AOSO, EBOM, FJS, FSBNDM, $\text{HASH}q$, LBNDM, SA, BMH-SBNDM, $\text{SBNDM}q$, TVSBS. Luận án chỉ ra hai hạn chế chung: không tận dụng mối tương quan giữa độ dài mẫu và bảng chữ cái để dịch chuyển cửa sổ cực đại, và không cập nhật ngay mức xuất hiện của mẫu tại vị trí duyệt dẫn đến việc quét lặp ký tự.
  • Đề xuất thuật toán $MRc$ (bao gồm $MR1$): Sử dụng cấu trúc tự động $M_p$ kết hợp biểu đồ chuyển trạng thái và khái niệm mức xuất hiện (degree of appearance) để theo dõi tiền tố dài nhất của mẫu xuất hiện tại vị trí đang quét trong văn bản đích $x$.
  • Đánh giá thực nghiệm: Thực hiện so sánh trên các bộ dữ liệu chuỗi ngẫu nhiên (rand4 đến rand256) và dữ liệu chuỗi sinh học thực tế (hệ gen $|\Sigma|=4$, protein $|\Sigma|=20$). Kết quả thực nghiệm xác nhận thuật toán $MRc$ có tốc độ thực thi nhanh hơn các thuật toán đối sánh trong phần lớn các trường hợp thử nghiệm.

CHAPTER 4 AUTOMATA TECHNIQUE FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM

Chương 4 nghiên cứu giải pháp cho bài toán tính độ dài dãy con chung dài nhất ($lcs(p, x)$):

  • Cơ sở tự động cho LCS: Kế thừa mô hình Knapsack Shaking của Phan Trung Huy và cộng sự (2002), xây dựng bảng tham chiếu $Ref_p$ cho mẫu $p$ (minh họa với xâu $p = \text{bacdabcad}$) và tự động $A_p = (\Sigma, Q, q_0, \phi, F)$.
  • Thiết kế thuật toán: Đề xuất hai thuật toán gồm thuật toán tuần tự và thuật toán song song để tính $lcs(p, x)$.
  • Phân tích và thực nghiệm: Phân tích lý thuyết thuật toán song song và tiến hành đo đạc thời gian tính toán thực tế trên các chuỗi có kích thước lớn ($n = 50666$ và $n = 102398$). Kết quả thực nghiệm khẳng định kỹ thuật tự động mang lại hiệu quả vượt trội trong việc giảm thời gian tính toán $lcs(p, x)$.

CHAPTER 5 CRYPTOGRAPHY BASED ON STEGANOGRAPHY AND AUTOMATA METHODS FOR SEARCHABLE ENCRYPTION

Chương 5 tích hợp các kết quả từ các chương trước để xây dựng hệ thống mã hóa tìm kiếm được (SE):

  • Hệ mật mã mới dựa trên lược đồ giấu tin $(2, 9, 8)$: Đề xuất hệ mật mã có tính bảo mật cao, thực hiện mã hóa và nhúng dữ liệu đồng thời trong một bước. Kích thước bản mã hoàn toàn không phụ thuộc vào kích thước ảnh đầu vào.
  • Thuật toán tìm kiếm trên dữ liệu mã hóa: Ứng dụng kỹ thuật tự động từ Chương 3 và Chương 4 để xây dựng hai thuật toán:
    1. Thuật toán khớp mẫu chính xác trên dữ liệu mã hóa.
    2. Thuật toán khớp mẫu xấp xỉ trên dữ liệu mã hóa.
  • Độ phức tạp tính toán: Cả hai thuật toán đều đạt độ phức tạp thời gian trong trường hợp xấu nhất là $O(n)$, trong đó thuật toán xấp xỉ giả định sử dụng $\lceil(1-\epsilon)m\rceil$ bộ xử lý ($\epsilon$ là sai số của độ đo tương tự chuỗi, $m$ là độ dài mẫu, $n$ là độ dài dữ liệu bí mật).
  • Ứng dụng trong SE: Hệ mật mã được dùng để mã hóa/giải mã ở phía người dùng, các thuật toán khớp mẫu tự động được triển khai trên máy chủ đám mây để tìm kiếm trực tiếp trên dữ liệu mã hóa.

Kết quả và những đóng góp mới

Luận án đã đạt được các đóng góp khoa học chính sau:

  1. Đóng góp lý thuyết về giấu tin trên trường Galois: Xây dựng khung lý thuyết tổng quát dựa trên trường Galois $GF(p^m)$, đồ thị lật và mô hình tự động để thiết kế các lược đồ giấu tin dạng khối $(k, N, \lfloor\log_2 p^{mn}\rfloor)$; chứng minh điều kiện đủ cho sự tồn tại của các lược đồ tối ưu và gần tối ưu trên ảnh nhị phân, ảnh xám và ảnh palette.
  2. Xác lập các lược đồ giấu tin cụ thể: Chứng minh tính tối ưu của lược đồ CTL $(1, 2^n-1, n)$ với $q_{\text{colour}} = 1$; thiết lập lược đồ gần tối ưu $(2, 9, 8)$ và tối ưu $(1, 5, 4)$ với $q_{\text{colour}} = 3$ cho ảnh xám và palette; xây dựng quy trình giấu chuỗi dữ liệu bí mật sử dụng hàm song ánh và tập khóa với phân tích an toàn chống tấn công vét cạn.
  3. Đóng góp về thuật toán khớp mẫu chính xác: Đề xuất thuật toán $MRc$ dựa trên mô hình tự động và mức xuất hiện, tối ưu hóa độ dịch chuyển cửa sổ trượt, đạt tốc độ thực thi nhanh hơn các thuật toán đối sánh hàng đầu trên dữ liệu ngẫu nhiên và dữ liệu sinh học.
  4. Đóng góp về bài toán LCS: Phát triển hai thuật toán tuần tự và song song dựa trên kỹ thuật tự động để tính độ dài LCS, chứng minh tính hiệu quả qua thực nghiệm trên chuỗi độ dài lớn.
  5. Đóng góp về mã hóa tìm kiếm được (SE): Đề xuất hệ mật mã mới dựa trên lược đồ $(2, 9, 8)$ thực hiện mã hóa và nhúng đồng thời, bản mã không phụ thuộc kích thước ảnh; xây dựng hai thuật toán khớp mẫu chính xác và xấp xỉ trên bản mã đạt độ phức tạp thời gian $O(n)$ trong trường hợp xấu nhất.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế được chỉ ra trong văn bản:

  • Phân tích an toàn cho các lược đồ giấu tin mới dừng lại ở phân tích mù trước tấn công vét cạn (brute-force attacks), chưa hoàn tất đánh giá thực nghiệm trước các tấn công phân tích giấu tin chuyên biệt (steganalysis attacks) như phân tích trực quan (visual attacks) hay kiểm định Chi-bình phương (chi-square attacks).
  • Đối với ảnh palette, giá trị tỉ lệ nhúng $ER$ thực nghiệm để duy trì chất lượng ảnh trên ngưỡng 30 dB vẫn thấp hơn nhiều so với $ER_{\max}$.
  • Chưa xác định được về mặt lý thuyết sự tồn tại của lược đồ tối ưu $(2, 8, 8)$ cho ảnh xám 8-bit với $q_{\text{colour}} = 3$ ngoài việc duyệt không tìm thấy tập sinh trên $GF^4(2^2)$.

Hướng nghiên cứu tiếp theo:

  • Hoàn thiện nghiên cứu và thử nghiệm khả năng chống các dạng tấn công steganalysis (visual attack, chi-square attack) cho các lược đồ đề xuất.
  • Cải thiện chất lượng ảnh stego trên ảnh palette nhằm nâng cao tỉ lệ nhúng tiệm cận $ER_{\max}$.
  • Tiếp tục giải quyết bài toán mở về sự tồn tại của lược đồ tối ưu $(2, 8, 8)$ cho ảnh xám 8-bit với $q_{\text{colour}} = 3$.

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học ngành Toán học, Toán tin, Khoa học máy tính và An toàn thông tin: Tham khảo phương pháp ứng dụng cấu trúc đại số trừu tượng (trường Galois) và mô hình lý thuyết tính toán (DFA, đồ thị lật) vào các bài toán thực tế của công nghệ thông tin.
  • Giảng viên và nhà nghiên cứu trong lĩnh vực Xử lý chuỗi và Mật mã học: Tham khảo các thuật toán khớp mẫu $MRc$, thuật toán tính LCS song song và kiến trúc hệ mật mã tìm kiếm được có độ phức tạp tuyến tính $O(n)$.
  • Kỹ sư phát triển hệ thống an toàn dữ liệu đám mây: Tham khảo mô hình phân chia chức năng mã hóa phía người dùng và tìm kiếm trực tiếp trên bản mã phía máy chủ đám mây.

Câu hỏi thường gặp

1. Lược đồ giấu tin gần tối ưu $(2, 9, 8)$ trên ảnh xám 8-bit đạt hiệu năng như thế nào so với lược đồ HCIH?
Trong thực nghiệm trên 9 ảnh xám chuẩn kích thước $512 \times 512$ pixel với $q_{\text{colour}} = 3$, lược đồ $(2, 9, 8)$ đạt tỉ lệ nhúng $ER = 0,86$ bpp và chỉ số $PSNR$ trung bình là 55,84 dB, cao hơn so với lược đồ HCIH ($ER = 0,75$ bpp và $PSNR = 46,33$ dB).

2. Công thức xác định số lượng tổ hợp cần duyệt trong tấn công vét cạn đối với quy trình giấu chuỗi dữ liệu $D$ vào ảnh $F$ là gì?
Số tổ hợp cần thử trong tấn công vét cạn bao gồm các lựa chọn tập sinh $S$, tập khóa $K$, hàm song ánh $Jump$ và hàm song ánh $f$, được tính theo công thức: $$c(p^m-1)^N N! , p^{m t_1 N} , t_2! , C_{p^{mn}}^{2^{\lfloor\log_2 p^{mn}\rfloor}} (2^{\lfloor\log_2 p^{mn}\rfloor})!$$

3. Tại sao lược đồ giấu tin tối ưu $(2, 8, 8)$ không được xây dựng trên không gian $GF^4(2^2)$ trong luận án?
Qua chương trình máy tính kiểm tra toàn bộ các tập con $N=8$ phần tử của $[GF^4(2^2)]$, tác giả xác định không tồn tại tập 2-[Generators] nào với $N=8$. Ngược lại, với $N=9$, chương trình tìm được $c \approx 2^{20}$ tập sinh, do đó luận án xây dựng lược đồ gần tối ưu $(2, 9, 8)$.

4. Hai thuật toán tìm kiếm trên dữ liệu mã hóa trong Chương 5 có độ phức tạp thời gian là bao nhiêu?
Cả hai thuật toán khớp mẫu chính xác và khớp mẫu xấp xỉ trên dữ liệu mã hóa đều có độ phức tạp thời gian trong trường hợp xấu nhất là $O(n)$, trong đó thuật toán xấp xỉ giả định sử dụng $\lceil(1-\epsilon)m\rceil$ bộ xử lý với $\epsilon$ là sai số độ đo tương tự chuỗi, $m$ là độ dài mẫu và $n$ là độ dài dữ liệu bí mật.

5. Điểm khác biệt của hệ mật mã đề xuất trong Chương 5 so với các kỹ thuật lai mật mã - giấu tin trước đây là gì?
Hệ mật mã đề xuất thực hiện việc mã hóa dữ liệu bí mật và nhúng vào phương tiện mang đồng thời trong một bước, đồng thời kích thước bản mã thu được hoàn toàn không bị phụ thuộc vào kích thước của ảnh đầu vào.

Kết luận

Luận án của tác giả Nguyễn Huy Trương đã phát triển một hệ thống phương pháp toán học và thuật toán dựa trên trường Galois $GF(p^m)$, lý thuyết đồ thị và tự động hữu hạn để giải quyết đồng bộ các bài toán giấu tin ảnh số, khớp mẫu chính xác, tính độ dài dãy con chung dài nhất và mã hóa tìm kiếm được. Công trình đã chứng minh sự tồn tại của nhiều lớp lược đồ giấu tin tối ưu và gần tối ưu, đồng thời đề xuất thuật toán khớp mẫu $MRc$ và thuật toán LCS có hiệu năng thực nghiệm cao. Các kết quả này được tích hợp thành công vào một hệ mật mã tìm kiếm được đối xứng với khả năng tìm kiếm tuyến tính $O(n)$ trên máy chủ đám mây, mở ra hướng ứng dụng trong bảo mật và xử lý dữ liệu số.