BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
——————————

Nguyễn Huy Trường

NGHIÊN CỨU PHÁT TRIỂN CÁC PHƯƠNG PHÁP
CỦA LÝ THUYẾT ĐỒ THỊ VÀ OTOMAT
TRONG GIẤU TIN MẬT VÀ MÃ HÓA TÌM KIẾM
Ngành: Toán Tin
Mã số: 9460117

TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN TIN

Hà Nội - 2020


Công trình được hoàn thành tại:
Trường Đại học Bách khoa Hà Nội

Người hướng dẫn khoa học:
1. PGS. TSKH. Phan Thị Hà Dương
2. TS. Vũ Thành Nam

Phản biện 1:
Phản biện 2:
Phản biện 3:
Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Trường
họp tại Trường Đại học Bách khoa Hà Nội

Vào hồi ....... giờ, ngày ....... tháng ....... năm .......

bảo vệ dữ liệu được nhúng) và thủy vân (bảo vệ sở hữu quyền tác giả
và xác thực phương tiện số mang dữ liệu được nhúng).
Giấu tin mật có thể được sử dụng như một cách thay thế mật mã.
Tuy nhiên, giấu tin mật sẽ trở nên yếu nếu các kẻ tấn công phát hiện
sự tồn tại của dữ liệu được giấu. Do đó tích hợp mật mã và giấu tin
mật như là một lựa chọn thứ ba cho an toàn dữ liệu.
Với sự phát triển nhanh chóng của các ứng dụng dựa trên nền tảng
Internet, tính toán đám mây trở thành một trong những chủ đề nóng
nhất trong lĩnh vực công nghệ thông tin. Thực ra, nó là một hệ thống
tính toán dựa trên Internet (cung cấp các dịch vụ theo yêu cầu từ các
ứng dụng và phần mềm hệ thống, lưu trữ cho đến xử lý dữ liệu). Ví
dụ, khi các người dùng đám mây sử dụng dịch vụ lưu trữ, họ có thể
gửi thông tin lên các máy chủ và sau đó truy cập nó trực tuyến trên
Internet. Trong khi đó, các doanh nghiệp có thể không trả số tiền lớn
cho bảo trì và sở hữu một hệ thống bao gồm phần cứng và phần mềm.
Mặc dù tính toán đám mây mang lại nhiều lợi ích cho các cá nhân và
tổ chức, song an toàn đám mây vẫn là một vấn đề mở khi các nhà cung
cấp đám mây có thể lạm dụng thông tin của khách hàng và các người
dùng đám mây mất quyền kiểm soát thông tin của họ. Do đó, đảm bảo
sự riêng tư thông tin của người thuê dịch vụ mà không phủ nhận lợi
ích của tính toán đám mây được xem là cần thiết. Để bảo vệ sự riêng
tư của người dùng đám mây, các dữ liệu nhạy cảm cần được mã hóa
trước khi gửi chúng lên các máy chủ. Thật không may mắn, mã hóa
làm cho các máy chủ thực hiện tìm kiếm trên dữ liệu mã hóa khó hơn
nhiều so với văn bản rõ. Để giải quyết vấn đề này, nhiều kỹ thuật mã
1


hóa tìm kiếm đã được trình bày từ năm 2000. Mã hóa tìm kiếm không
chỉ lưu trữ dữ liệu mã hóa của các người dùng mà còn cho phép tìm

đầu ở đầu và Kết luận ở cuối luận án, nội dung chính của luận án
được chia thành năm chương.
Chương 1. Kiến thức cơ sở.
Chương 2. Giấu tin mật trong ảnh số dựa trên trường Galois sử
dụng lý thuyết đồ thị và otomat.
2


Chương 3. Một cách tiếp cận otomat cho so mẫu chính xác.
Chương 4. Kỹ thuật otomat cho bài toán dãy con chung dài nhất.
Chương 5. Mật mã dựa trên giấu tin mật và các phương pháp
otomat cho mã hóa tìm kiếm.
Các nội dung của luận án được viết dựa trên bài báo được xuất
bản [T1] ở, bản thảo sửa đổi [T4] được gửi tới KSII Transactions on
Internet and Information Systems (ISI), và các bài báo [T2, T3] được
xuất bản ở Journal of Computer Science and Cybernetics trong năm
2019. Các kết quả chính của luận án đã được trình bày ở: Seminar Cơ
sở Toán của Tin học ở Viện Toán học, Viện Hàn lâm Khoa học và Công
nghệ Việt Nam; Đại hội Toán học Việt Nam lần thứ 9, Nha Trang, 1418/08/2018; Seminar ở Viện Toán ứng dụng và Tin học, Trường Đại
học Bách khoa Hà Nội.
CHƯƠNG 1
KIẾN THỨC CƠ SỞ
1.1 Cấu trúc cơ bản
1.1.1 Xâu
Trong luận án, các dữ liệu mật được coi là các xâu. Vì vậy, một số
thuật ngữ liên quan đến xâu sẽ được nhắc lại ở đây.
1.1.2 Đồ thị
Bên cạnh một số khái niệm cơ bản trong lý thuyết đồ thị, mục này
nhắc lại cách biểu diễn đồ thị bằng danh sách kề và tìm kiếm theo
chiều rộng. Chúng được sử dụng trong Chương 2.

1.4.
Dữ liệu mật

Ảnh
gốc

Nhúng

Dữ liệu mật

Ảnh
chứa
tin

Kênh truyền
thông
Gửi đến

Ảnh
chứa
tin

Trích

Khóa bí mật

Khóa bí mật

Người gửi


1
2
2
k
k
MSDR k (N ) = log2 (1+qcolour CN
+qcolour
CN
+· · ·+qcolour
CN
) . (1.3)

1.3 So mẫu chính xác
Mục này sẽ phát biểu lại bài toán so mẫu đơn chính xác, và nhắc
lại khái niệm độ mờ (xuất hiện) sẽ được sử dụng trong Chương 3.

4

5


Định nghĩa 1.5. Cho p là một mẫu có độ dài m và x là một văn bản
có độ dài n trên bảng chữ cái Σ. Khi đó bài toán so mẫu đơn chính xác
là tìm tất cả các xuất hiện của mẫu p trong x.
Định nghĩa 1.6 (P. T. Huy và cộng sự, 2002). Cho p là một mẫu
và x là một văn bản có độ dài n trên bảng chữ cái Σ. Khi đó với mỗi
1 ≤ i ≤ n, độ xuất hiện của p trong x ở vị trí i bằng độ dài của xâu
con dài nhất của x sao cho xâu con này là khúc đầu của p, trong đó kí
tự tận cùng bên phải của xâu con này là x[i].
1.4 Dãy con chung dài nhất

GALOIS SỬ DỤNG LÝ THUYẾT ĐỒ THỊ VÀ OTOMAT
Chương này trước tiên đề xuất các khái niệm các lược đồ giấu tin
tối ưu và gần tối ưu. Tiếp theo chương đề xuất một cách tiếp cận giấu
tin mật trong ảnh mới dựa trên trường Galois GF (pm ) sử dụng đồ thị
và otomat để thiết kế lược đồ giấu tin dạng tổng quát (k, N, log2 pmn )
cho các ảnh nhị phân, xám và chỉ số với một số giả thiết cho trước,
trong đó k, m, n, N là các số nguyên dương và p là nguyên tố, và chỉ ra
các điều kiện đủ cho sự tồn tại và chứng minh sự tồn tại của một số
lược đồ giấu tin mật tối ưu và gần tối ưu. Những kết quả này được phát
triển từ khái niệm tỷ lệ giấu tin tối đa của các bít được nhúng, phương
pháp mô đun và phương pháp FOPA được đề xuất bởi P. T. Huy và
cộng sự trong các năm 2011, 2012 and 2013, được nhắc lại trong Mục
1.2 của Chương 1. Một ứng dụng của các lược đồ cho quá trình giấu
một dãy hữu hạn dữ liệu mật trong một ảnh được xem xét. Các phân
tích an toàn và kết quả thực nghiệm khẳng định rằng cách tiếp cận
được đề xuất có thể tạo ra các lược đồ giấu tin mật đạt được hiệu quả
cao về khả năng nhúng, chất lượng ảnh, tốc độ cũng như độ an toàn,
chúng là những thuộc tính quan trọng nhất của giấu tin mật.
Các kết quả của Chương 2 đã được công bố trong [T1].
2.1 Giới thiệu
2.2 Bài toán giấu tin mật trong ảnh số
Định nghĩa 2.1. Một lược đồ giấu tin mật theo khối trong các ảnh
số (cho ngắn, gọi là một lược đồ giấu tin) là một bộ năm
(I, M, K, Em, Ex), trong đó các điều kiện sau được thỏa mãn.
1. I là một tập tất cả các khối ảnh cùng kích thước và loại ảnh,
2. M là một tập hữu hạn các phần tử mật,
3. K là một tập hữu hạn các khóa bí mật,
4. Em là một hàm nhúng để nhúng một phần tử mật vào trong một
khối ảnh, Em : I × M × K → I,
5. Ex là một hàm trích để trích một phần tử mật được nhúng từ

cho bởi
[x] = {ax|a ∈ GF (pm )\{0}}.
Cho một lớp [x], x được xem là phần tử đại diện của [x]. Cho đơn
giản, kí hiệu lớp [0] là 0.
Kí hiệu tập tất cả các lớp là [GF n (pm )]. Tập này được biểu diễn
bởi [GF n (pm )] = {[x]|x ∈ GF n (pm )}. Số lượng các phần tử của một
tập S được kí hiệu là |S|.
7


Mệnh đề 2.2. |[GF n (pm )]\{0}| =

pmn −1
pm −1 .

Định nghĩa 2.6. Giả sử S ⊂ [GF n (pm )]\{0}. Khi đó S được gọi là
k-[Các phần tử sinh] của tập [GF n (pm )], trong đó k là một số nguyên
dương, nếu ∀[v] ∈ [GF n (pm )]\{0}, [v] ∈ {[ ti=1 ai vi ]|ai ∈ GF (pm )\{0},
[vi ] ∈ S, i = 1, t, t ≤ k}.
Định nghĩa 2.7. Cho V là một không gian véc tơ trên trường K,
S ⊂ V . Khi đó S được gọi là k-Các phần tử sinh của V , trong đó k là
một số nguyên dương, nếu hai điều kiện sau thỏa mãn.
a) ∀v, v ∈ S, a ∈ K, v = av,
b) ∀v ∈ V \{0}, ∃t, t ≤ k, v1 , v2 , . . . , vt ∈ S, a1 , a2 , . . . , at ∈ K\{0},
v = ti=1 ai vi .
Định lý 2.1. Tồn tại S là một k-Các phần tử sinh của không gian véc
tơ GF n (pm ) với |S| = N nếu và chỉ nếu tồn tại S là một k-[Các phần
tử sinh] của tập [GF n (pm )] với |S | = N .
Mệnh đề 2.4. Cho c là số lượng k-[Các phần tử sinh] gồm N phần tử
của tập [GF n (pm )]. Khi đó số lượng k-Các phần tử sinh gồm N phần

Giả thiết rằng xây dựng được một đồ thị lật G = (V, E).
Từ cách xác định tập cung E trong Định nghĩa 2.8, giả thiết rằng
|C| ≥ pm và qcolour = pm − 1.

(2.1)

Cho một khối ảnh I ∈ I, một phần tử mật M ∈ M, một khóa
K ∈ K. Bằng cách sử dụng otomat A(I, M, K) và đồ thị lật G, hai
hàm Em and Ex trong lược đồ giấu tin (I, M, K, Em, Ex) được định
nghĩa như sau.
Hàm Em (nhúng M vào trong I):
q = q0 ;
For i = 1 to N Do q = δ(q, Ii );
q = δ(q, M );
For each (it , at ) in q Do Iit = Adjacent(Iit , at );
I = I;
Hàm Ex (trích M từ I ):
q = q0 ;
For i = 1 to N Do q = δ(q, Ii );
M = q;
Định lý 2.2. Giả sử rằng tìm được một k-Các phần tử sinh S của
không gian véc tơ GF n (pm ) và xây dựng được một đồ thị lật G. Khi đó
tồn tại lược đồ giấu tin (k, N, log2 pmn ), trong đó N = |S|.
Phân tích an toàn của lược đồ giấu tin được đề xuất
(k, N, log2 pmn ): Giả thiết rằng công khai các tham số k, N , Em, Ex,
9


không gian véc tơ GF n (pm ) và đồ thị lật G trong lược đồ giấu tin
(k, N, log2 pmn ).

2

mn
(pm −3)2
+2(2 log2 p
4
m
p −1

−1)

và xây dựng được một đồ thị lật G. Khi đó tồn tại lược đồ giấu tin tối
ưu (2, |S|, log2 pmn ) với qcolour = pm − 1.
2.4 Các lược đồ giấu tin gần tối ưu và tối ưu cho các ảnh xám
và chỉ số
Ở đây xét trường hợp k = p = m = 2 và n = 4, lược đồ giấu
tin (2, N, 8) tồn tại nếu giả thiết của Định lý 2.2 được thỏa mãn,
nghĩa là tìm được một 2-Các phần tử sinh S của không gian véc tơ
GF 4 (22 ), |S| = N và xây dựng được một đồ thị lật G trên trường
Galois GF (22 ).
Định lý 2.5. Tồn tại lược đồ giấu tin gần tối ưu (2, 9, 8) cho các ảnh
xám và chỉ số với qcolour = 3.
Phân tích an toàn của lược đồ giấu tin gần tối ưu (2, 9, 8):
c39 9!218 28 !.
10

(2.45)


Hệ quả 2.1. Tồn tại lược đồ tối ưu (1, 5, 4) cho các ảnh xám và chỉ

Chương này chỉ giải quyết bài toán so mẫu chính xác, được nhắc
lại trong Mục 1.3 của Chương 1. Nghiên cứu ứng dụng đề xuất của
chương giải bài toán này cho SE sẽ được giới thiệu trong Chương 5.
11


3.2 Thuật toán mới - Thuật toán MRc
Cho trước một số nguyên dương c, một xâu có độ dài c được gọi là
một c_block. Một c_block được (tương ứng không được) gọi là trong
p, kí hiệu c_block ∈ p (tương ứng c_block ∈
/ p), nếu c_block là (tương
ứng không là) một xâu con của p. Với một số nguyên dương cho trước
c, 1 ≤ c ≤ m and c ≤ i ≤ m, xâu con p[i − c + 1..i] được gọi là một
c_block của p ở vị trí i, kí hiệu c_blockip . Đặc biệt, c = 1, khi đó
c_block chỉ là một kí tự.
Định nghĩa 3.3. Cho p là một mẫu và z là một c_block của p, trong đó
c là một số nguyên dương với 1 ≤ c ≤ |p|. Cho i là vị trí nào đó trong p
với c ≤ i ≤ |p|. Khi đó i được gọi là vị trí xuất hiện cuối cùng của z trong
p, kí hiệu Pos p (z), nếu z = c_blockip và ∀j > i, j ≤ |x|, z = c_blockjp .
Dựa vào otomat Mp và hai khái niệm điểm gãy và Posp , ý tưởng cơ
bản của cách tiếp cận được đề xuất cho so mẫu chính xác được chỉ ra
trong Hình 3.2.
c_block

p, trượt cửa sổ và thực hiện bước nhảy kiểm tra

Đặt q = 0

Điểm gãy xảy ra, thực hiện bước nhảy kiểm tra


độ dài n trên bảng chữ cái Σ. Cho T (n) là số lượng tất cả các kí tự của
x được truy cập bởi thuật toán MRc . Nếu |Σ| ≥ 4, 16 ≤ m ≤ 2048 hoặc
|Σ| ≥ 32, 8 ≤ m ≤ 2048, khi đó tồn tại c, 1 ≤ c ≤ 8 sao cho các điều
kiện sau được thỏa mãn với phân phối đều trên bảng chữ cái Σ.
(a) T (n) < n,
(b) P (z ∈ x) ≤ 2−5 , trong đó z là một c_block bất kì trên bảng chữ
cái Σ.
3.4 Kết quả thực nghiệm
Mục này thực hiện một số thực nghiệm để so sánh thuật toán MRc
với các thuật toán khác.
3.5 Kết luận
Xuất hiện của một phần của mẫu được phản ánh và cập nhật tức
thì tại vị trí bất kì đang được duyệt trên văn bản, vì vậy cách tiếp cận
của chương có thể được ứng dụng cho SE. Chủ đề quan trọng này sẽ
được trình bày trong Chương 5.
CHƯƠNG 4
KỸ THUẬT OTOMAT CHO BÀI TOÁN DÃY CON
CHUNG DÀI NHẤT
Chương này đề xuất hai thuật toán hiệu quả trong thực hành để
tính độ dài của một dãy con chung dài nhất của hai xâu, sử dụng kỹ
thuật otomat, trong các cách tuần tự và song song. Với hai xâu đầu
vào có độ dài m và n với m ≤ n, thuật toán song song sử dụng k vi
xử lý (k ≤ m) và có độ phức tạp thời gian O(n) trong trường hợp xấu
13


nhất, trong đó k là một ước lượng trên của độ dài của một dãy con
chung dài nhất của hai xâu. Các kết quả này dựa trên cách tiếp cận lắc
ba lô được giới thiệu bởi P. T. Huy và cộng sự trong năm 2002, được
nhắc lại trong Mục 1.4 của Chương 1. Các kết quả thực nghiệm chỉ ra

Giả sử Cf = {x1 , x2 , . . . , xt } là một trạng thái kết với 1 ≤ t ≤ m. Khi
đó tồn tại xâu con u của x sao cho một LCS(p, u) là xt .
Định lý 4.2. Cho p là một xâu có độ dài m trên bảng chữ cái Σ,
C ∈ Config(p) và s ∈ Σ∗ . Khi đó δ(Wp (C), s) = Wp (ϕ(C, s)), trong đó
δ và ϕ được cho lần lượt như trong các Định nghĩa 4.5 and 1.12.
14


4.3 Các mô hình otomat giải bài toán LCS
Định lý 4.3. Cho p và x là hai xâu có độ dài m và n trên bảng chữ
cái Σ, m ≤ n. Cho c là một hằng số nguyên dương, 1 ≤ c ≤ m và
ASc
p = (Σ, Q, q0 , δStep , F ) tương ứng với p là một otomat trên bảng chữ
cái Σ, trong đó
• Tập các trạng thái Q = WConfig(p),
• Trạng thái khởi đầu q0 = W0 ,
• Hàm chuyển δStep được cho như trong Định nghĩa 4.8,
• Tập các trạng thái kết F = {Wf |Wf ∈ WConfig(p), |Wf | =
c hoặc Wf = δStep (W0 , x)}.
Giả sử Wf là một trạng thái kết. Khi đó tồn tại xâu con u của x sao
cho lcs(p, u) = |Wf |.
Định lý 4.4. Cho p và x là hai xâu có độ dài m và n trên bảng chữ
cái Σ, m ≤ n. Cho c là một hằng số nguyên dương, 1 ≤ c ≤ m và
APp c = (Σ, Qp , q0 , δp , Fp ) tương ứng với p là một otomat trên bảng chữ
cái Σ, trong đó
• Tập các trạng thái Qp = WConfig(p),
• Trạng thái khởi đầu q0 = W0 ,
• Hàm chuyển δp được cho như trong Định nghĩa 4.9.
• Tập các trạng thái kết Fp = {Wf |Wf ∈ WConfig(p), |Wf | =
c hoặc Wf = δp (W0 , x)}.

CHƯƠNG 5
MẬT MÃ DỰA TRÊN GIẤU TIN MẬT VÀ CÁC
PHƯƠNG PHÁP OTOMAT CHO MÃ HÓA TÌM KIẾM
Chương này đề xuất một hệ mật mã mới dựa trên lược đồ giấu tin
(2, 9, 8), một kết quả mới được trình bày trong Mục 2.4 của Chương 2,
với độ an toàn cao, trong đó mã hóa và giấu tin được thực hiện cùng
một lúc, bản mã không phụ thuộc vào kích thước ảnh đầu vào như các
kỹ thuật kết hợp mật mã và giấu tin mật hiện đang tồn tại. Tiếp theo
các kết quả của Chương 3 và 4, sử dụng kỹ thuật otomat, được ứng
dụng để thiết kế hai thuật toán cho so mẫu chính xác và xấp xỉ trên dữ
liệu mật được mã hóa bởi hệ mật mã được đề xuất. Các phân tích lý
thuyết nói rằng các thuật toán này đều có độ phức tạp thời gian O(n)
trong trường hợp xấu nhất, trong đó với thuật toán xấp xỉ, giả thiết
rằng nó sử dụng (1 − )m vi xử lý, trong đó , m và n lần lượt là sai
số của độ đo tương tự xâu được định nghĩa mới trong Công thức (5.11)
và các độ dài của mẫu và dữ liệu mật. Trong mã hóa tìm kiếm, hệ mật
mã có thể được ứng dụng để mã hóa và giải mã dữ liệu mật bởi các

16


người dùng và các thuật toán so mẫu được sử dụng bởi các máy chủ
để thực hiện tìm kiếm mẫu.
Các kết quả của Chương 5 đã được công bố trong [T4].
5.1 Giới thiệu
Mục tiêu của chương này là đề xuất một hệ mật mã đối xứng mới
được sử dụng bên phía các người dùng, và các thuật toán cho so mẫu
chính xác và xấp xỉ trên các bản mã được sử dụng bên phía các máy
chủ đám mây. Chúng là những thành phần rất quan trọng trong SSE.
5.2 Một hệ mật mã mới dựa trên lược đồ giấu tin (2, 9, 8)

1. ek : P → C, ek (x) = h(Em (I, f (x), K)) với x ∈ P.
2. dk : C → P, dk (y) = f −1 (Ex (h−1 (y), I, K)) với y ∈ C.
Đặt E = {ek |k ∈ K }, D = {dk |k ∈ K }. Từ Định nghĩa 1.13, tính
đúng đắn của hệ mật mã (P, C, K , E, D) được đảm bảo bằng định lý
sau.
Định lý 5.1. Cho ∀x ∈ P, ∀k ∈ K , ek ∈ E và dk ∈ D. Khi đó
dk (ek (x)) = x.
Phân tích an toàn của hệ mật mã (P, C, K , E, D): Giả thiết rằng
công khai các tham số đồ thị lật G, Em , Ex , GF 4 (22 ) và h trong hệ
mật mã (P, C, K , E, D).
c39 9!218 28 !2569 = c39 9!290 28 ! với các ảnh xám,

(5.3)

c39 9!218 29t 28 ! = c39 9!218+9t 28 ! với các ảnh chỉ số.

(5.4)

hoặc
Nhận xét 5.2. Với Nhận xét 5.1, tất cả các cặp của các hàm (ek , dk )
trong hệ mật mã (P, C, K , E, D) không làm các khối ảnh I thay đổi với
∀k ∈ K , k = (f, K, I). Hơn nữa, chúng ta có thể thấy rằng mã hóa và
giấu tin được thực hiện cùng một lúc.
Xem một tập con các khối ảnh F là một ảnh đầu vào, F ⊂ I,
F = {F1 , F2 , . . . , Ft2 }, t2 là số lượng các khối ảnh. Tiếp theo, Mục 5.2
đưa ra cách ứng dụng hệ mật mã (P, C, K , E, D) vào quá trình mã
hóa và giải mã dữ liệu mật qua kênh không an toàn. Với Nhận xét
5.2, chúng ta có thể sử dụng một tập con các khóa bí mật K thay
cho một khóa bí mật k, K = {(f, K, I)|K ∈ K, I ∈ F } ⊂ K với
f ∈ F, K = {K 1 , K 2 , . . . , K t1 }.

đầu vào cho trước F , dữ liệu mật được mã hóa không bị giới hạn bởi
kích thước ảnh đầu vào F .
5.3 Kỹ thuật otomat cho so mẫu chính xác trên dữ liệu mã
hóa
Giả sử rằng Alice có một dữ liệu mật và thích thuê ngoài dữ liệu
này lên nhà cung cấp đám mây Bob. Vì nhà cung cấp là bán đáng tin
19


cậy, Alice cần mã hóa bản rõ của chị ta và chỉ muốn lưu trữ bản mã
trên đám mây. Giả thiết rằng Alice sử dụng hệ mật mã (P, C, K , E, D)
được đề xuất ở trong Mục 5.2 để mã hóa dữ liệu với một cặp của hai
tham số bí mật (S, k) trong hệ mật mã, trong đó S là một 2-Các phần
tử sinh của GF 4 (22 ) với 9 phần tử và k = (f, K, I) ∈ K .
Vì không gian và khả năng tính toán hạn chế, thay vì tải bản mã
xuống, giả mã nó và tìm kiếm cục bộ, Alice có thể yêu cầu Bob thực
hiện công việc so mẫu trên trực tiếp bản mã với một cửa sập của mẫu
được nhận từ chị ta.
Xem Σ là bảng chữ cái có kích thước 256. Giả sử rằng dữ liệu mật
là một xâu trên Σ, x = x1 x2 ..xt3 với xi ∈ P, ∀i = 1, t3 , t3 ≥ 1 và t3
thường là một số tự nhiên lớn, trong đó P = Σ.
Trước khi tải dữ liệu mật x lên cho Bob, Alice sử dụng hàm mã
hóa ek ∈ E để mã từng xi . Khi đó Alice tính yi = ek (xi ), ∀i = 1, t3 , và
dữ liệu mật được mã hóa là một xâu trên Σ , y = y1 y2 ..yt3 được gửi tới
Bob, trong đó Σ là một bảng chữ cái, Σ = {a |a = ek (a), a ∈ Σ}.
Trong trường hợp tổng quát, với x là xâu bất kì trên bảng chữ cái
Σ và xâu y thu được từ x bằng cách ở trên. Khi đó chúng ta có thể
viết y = ek (x) cho ngắn và y là một xâu trên bảng chữ cái Σ .
Nhận xét 5.4. Với sử dụng chỉ một cặp của hai tham số bí mật (S, k),
khi đó độ an toàn của quá trình mã hóa và giải mã dữ liệu mật x tương

{
q = 0;
i = jump − P osp (yjump ) + 1;
Do
{
q = δp (q, yi );
If (q == |p|) Mark an occurrence of p at i − |p| + 1 in x;
i + +;
} While (q = 0 and i ≤ |y|);
jump = i − 1;
}
jump = jump + |p|;
}
Nhận xét 5.6. Trong trường hợp xấu nhất, độ phức tạp thời gian của
thuật toán này là O(n).
5.4 Kỹ thuật otomat cho so mẫu xấp xỉ trên dữ liệu mã hóa
Giả sử rằng Bob muốn thực hiện so mẫu xấp xỉ của mẫu bất kì p
trên bản mã y. Từ các kết quả được đề xuất trong Chương 4, kỹ thuật
otomat vẫn được ứng dụng cho giải quyết yêu cầu này.
21


Định lý 5.3. Cho trước một mẫu p trên Σ và một hằng số nguyên
dương c với 1 ≤ c ≤ |p|. Cho hai otomat APp c = (Σ, Qp , q0 , δp , Fp ) và
APp c = (Σ , Qp , q0 , δp , Fp ) được xác định như trong Định lý 4.4. Khi đó
Qp = Qp , Fp = Fp , ∀q ∈ Qp , ∀a ∈ Σ , a = dk (a ), δp (q, a ) = δp (q, a),
trong đó p = ek (p).
Nhận xét 5.7. Ý nghĩa của Định lý 5.3 trong thực hành là để tính
δp từ δp .
Định nghĩa 5.1. Cho trước hai xâu p và x trên Σ, và một độ đo tương