Vinh University Journal of Science Vol. 53, No. 3A/2024
73
LƯỢC ĐỒ THỦY VÂN DỰA VÀO BIT Ý NGHĨA NHẤT
ĐỂ BẢO VỆ BẢN QUYỀN CÔNG KHAI
CHO CÁC CƠ SỞ DỮ LIỆU QUAN HỆ
Lưu Thị Bích Hương
Viện Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội 2, Việt Nam
ARTICLE INFORMATION
TÓM TẮT
Journal: Vinh University
Journal of Science
Natural Science, Engineering
and Technology
p-ISSN: 3030-4563
e-ISSN: 3030-4180
Bài báo trình bày một lược đồ thủy vân dựa vào bit ý nghĩa
nhất để bảo vệ bản quyền công khai cho các cơ sở dữ liệu quan
hệ. Lược đồ thủy vân đề xuất có thể chứng minh một cách công
khai bản quyền của dữ liệu bao nhiêu lần tùy ý. Lược đồ thủy
vân bền vững trước các các tấn công điển hình như: Thêm, sửa,
xóa giá trị dữ liệu một cách ngẫu nhiên hoặc có lựa chọn.
Từ khóa: Bản quyền công khai; thủy vân; cơ sở dữ liệu.
1.Mở đầu
Cho đến nay, các lược đồ thủy vân dùng để bảo vệ bản
quyền cho các cơ sở dữ liệu quan hệ đều phải dựa vào
một khóa bí mật nào đó khi chứng minh quyền sở hữu đối
với các cơ sở dữ liệu đã thủy vân [1]-[4]. Tuy nhiên, khóa
bí mật này coi như đã bị lộ và vì vậy thủy vân đã nhúng
sẽ dễ dàng bị phá hủy bởi những kẻ tò mò. Hơn nữa, hầu
hết các lược đồ thủy vân hiện có đều làm sai lệch dữ liệu
trong quy trình nhúng thủy vân. Trong đó, có một số lược
đồ thay đổi các giá trị thuộc tính [2]-[3] và một số lược
đồ khác lại hoán vị các giá trị dữ liệu [6]. Những sai lệch
này chỉ được thực hiện trong giới hạn cho phép sao cho
giá trị sử dụng của dữ liệu đối với các ứng dụng nhất định
không bị ảnh hưởng và thủy vân vẫn có thể tìm lại được
ngay cả khi có những tấn công làm thay đổi giá trị thuộc
tính hay thêm hoặc xóa một số bộ.
Volume: 53
Issue: 3A
*Correspondence:
luuthibichhuong@hpu2.edu.vn
Received: 12 March 2024
Accepted: 28 May 2024
Published: 20 September 2024
Citation:
Luu Thi Bich Huong (2024).
Watermarking scheme based on
most significant bit for public
copyright protection for relational
databases
Vinh Uni. J. Sci.
Vol. 53 (3A), pp. 73-79
doi: 10.56824/vujs.2024a032a
OPEN ACCESS
Hai đặc điểm nêu trên có thể ảnh hưởng tới khả năng ứng
dụng của các kỹ thuật thủy vân cơ sở dữ liệu quan hệ. Thứ
nhất, cách tiếp cận dựa vào khóa thủy vân là không phù
hợp cho việc chứng minh trước công chúng (ví dụ trước
tòa án). Để chứng minh bản quyền của dữ liệu đáng ngờ,
người chủ sở hữu phải tiết lộ khóa thủy vân của mình ra
công chúng để phát hiện thủy vân. Sau khi đã sử dụng
một lần, khóa này không còn bí mật nữa. Với khóa thủy
vân, người sử dụng không bản quyền có thể vô hiệu hóa
việc phát hiện thủy vân gốc bằng cách gỡ bỏ tất cả thủy
vân gốc khỏi dữ liệu được bảo vệ hoặc thêm một thủy vân
giả vào dữ liệu không được thủy vân.
Copyright © 2024. This is an
Open Access article distributed
under the terms of the Creative
Commons Attribution License (CC
BY NC), which permits non-
commercially to share (copy and
redistribute the material in any
medium) or adapt (remix,
transform, and build upon the
material), provided the original
work is properly cited.
L. T. B. Hương / Lược đồ thủy vân dựa vào bit ý nghĩa nhất để bảo vệ bản quyền công khai cho các…
74
Đặc điểm thứ hai là, mọi sai lệch được đưa vào trong quá trình thủy vân có thể ảnh
hưởng đến giá trị sử dụng của dữ liệu. Ngay cả khi có thể ấn định một số kiểu ràng buộc
nhất định để hạn chế sai sót (ví dụ như các phương sai và các giá trị trung bình của những
thuộc tính được thủy vân) trước hoặc trong khi thủy vân thì cũng rất khó, thậm chí không
thể đảm bảo có thể lượng hóa được tất cả các ràng buộc.
Trong bài báo [5], các tác giả đã đưa ra một lược đồ thủy vân cơ sở dữ liệu sử dụng
để bảo vệ bản quyền bằng cách kiểm chứng công khai và không đưa vào bất kỳ một sự sai
lệch nào đối với dữ liệu. Lược đồ thủy vân được áp dụng cho các cơ sở dữ liệu quan hệ và
giả sử lược đồ quan hệ này mọi thay đổi trên bit MSB (bit ý nghĩa nhất - Most Significant
Bit) của giá trị các thuộc tính là không chấp nhận được. Mặc dù các tác giả đã nhận định
có thể áp dụng cho mọi kiểu dữ liệu khác nhau, tuy nhiên không làm rõ bit MSB của các
kiểu dữ liệu là bit nào, điều này là khó khăn khi triển khai. Trong thuật toán 1 và thuật toán
2, các tác giả đã tạo ra quan hệ thủy vân với các kiểu dữ liệu khác nhau nhưng cách thức
lấy các bit MSB của các thuộc tính là giống nhau, trong khi các cơ sở dữ liệu quan hệ luôn
cập nhật dữ liệu [5]. Việc làm này sẽ dẫn đến khi cần chứng minh sẽ làm cho thủy vân
không bền vững. Ý tưởng của kỹ thuật này là xuất phát từ cơ sở dữ liệu quan hệ cần bảo
vệ, sinh ra một quan hệ thủy vân có cùng khóa chính, còn các giá trị của các thuộc tính
khác là bit ý nghĩa nhất (MSB) của giá trị thuộc tính tương ứng của quan hệ gốc. Sau đó,
hai quan hệ này sẽ được đăng ký với một tổ chức có chức năng bảo hộ bản quyền sản
phẩm. Khắc phục nhược điểm đó chúng tôi đề xuất lược đồ thủy vân để bảo vệ bản quyền
công khai”.
Trong bài báo này, trước hết chúng tôi sẽ trình bày lược đồ thủy vân cải tiến với
cách lấy các bit MSB của các kiểu dữ liệu. Quá trình chứng minh bản quyền công khai khi
có tranh chấp bằng bản chứng thực được thực hiện hoàn toàn giống như lược đồ đề xuất
[5]. Phân tích về độ bền vững của lược đồ cải tiến, cân đối giữa tính bền vững và các chi
phí cho việc thực hiện lược đồ được thực hiện thông qua thử nghiệm và đánh giá các kết
quả thu được.
2. Lược đồ
Cho r là một quan hệ thuộc lược đồ R(P, A1,..., A) trong đó P là thuộc tính khóa
chính; có thuộc tính có thể được chọn để thuỷ vân A1 ,..., A, là số các bộ trong quan
hệ r. Với mỗi thuộc tính Aj (j = 1, 2, .., ) của một bộ sẽ được biểu diễn dưới dạng nhị phân
chuẩn, bit MSB của thuộc tính Aj của một bộ có thể được chọn để làm thuỷ vân. Giả sử
lược đồ quan hệ ban đầu không chấp nhận sự thay đổi trên bit MSB của giá trị thuộc tính
đối với giá trị sử dụng của dữ liệu.”
Bảng 1: Các ký hiệu được sử dụng trong lược đồ thủy vân
Ký hiệu
Ý nghĩa
R
Lược đồ quan hệ
r
Quan hệ r thuộc lược đồ R
ri
Bộ thứ i của quan hệ r
ri.Aj
Giá trị của thuộc tính Aj thuộc bộ ri
ω
Số bộ trong quan hệ r
Số thuộc tính không phải khóa chính trong R
K
Khóa thủy vân
Vinh University Journal of Science Vol. 53, No. 3A/2024
75
Ký hiệu
Ý nghĩa
P
Thuộc tính khóa chính
η
Tham biến sinh thuỷ vân
Tham số phát hiện thủy vân
H(Kri.P )
Hàm băm khóa thủy vân K cùng với giá trị thuộc tính khóa chính
P của bộ ti và || là phép ghép nối
Các thuộc tính để thủy vân của cơ sở dữ liệu quan hệ có thể nhận bất kỳ một kiểu
dữ liệu nào. Lược đồ thủy vân cải tiến của chúng tôi sẽ xét đến bốn kiểu dữ liệu thường
dùng đó là: kiểu số, kiểu ký tự, kiểu Boolean và kiểu datetime. Các thuộc tính của cơ sở
dữ liệu đều được thể hiện dưới dạng các xâu bit trong hệ thống máy tính.
Giả sử chủ sở hữu của quan hệ r có một khóa thuỷ vân K. Khóa thủy vân phải thỏa
mãn yêu cầu đủ dài và được sử dụng trong khi sinh thủy vân và phát hiện thuỷ vân trong
lược đồ thủy vân. Kết cấu của thủy vân công khai rw phụ thuộc vào khóa thủy vân K. Thủy
vân rw là một quan hệ với lược đồ Rw(P, W1 , . . . , Wη ), trong đó P là thuộc tính khóa chính,
W1, . . . , Wη là các thuộc tính nhị phân. So sánh quan hệ gốc r với quan hệ thuỷ vân rw thì
hai quan hệ có cùng thuộc tính khóa chính P và cùng số bộ . Số các thuộc tính nhị phân
trong thuỷ vân rw là η và số bit nhị phân của rw là v. Để xác định số lượng các bit nhị phân
v trong quan hệ thủy vân rw dựa vào tham biến điều khiển η với v = ω.η và η . Khi đó,
ta gọi η là tham biến sinh thuỷ vân.
Trong lược đồ, khóa thuỷ vân là công khai và có thể nhận bất kỳ giá trị nào (số
nguyên hoặc số nhị phân) do chủ sở hữu dữ liệu lựa chọn. Không có bất cứ một ràng buộc
nào về việc hình thành khóa. Để giảm bớt những nhầm lẫn không cần thiết, khóa thuỷ vân
nên là duy nhất đối với chủ sở hữu của cơ sở dữ liệu quan hệ cần thủy vân. Khóa thuỷ vân
tạo ra dưới dạng như sau: K = H(ID  tên CSDL  phiên bản ...), trong đó, ID là định
danh của chủ nhân cơ sở dữ liệu, “” là phép ghép nối, H() là hàm băm mật mã.
Trong thuật toán sinh thuỷ vân rw, bit MSB của các giá trị đã chọn dựa vào khóa
thủy vân và khóa chính của bộ, được sử dụng để tạo thuỷ vân. Quá trình sinh thủy vân
không làm thay đổi bất kỳ một giá trị thuộc tính nào của dữ liệu gốc. Việc sử dụng các bit
MSB sẽ giúp ngăn chặn những tấn công thay đổi giá trị dữ liệu. Vì khóa thủy vân K, thủy
vân rw và thuật toán nhúng thủy vân đều công khai nên bất kỳ ai cũng có thể tìm được các
bit MSB trong r để sinh rw. Tuy nhiên, kẻ tấn công không thể thay đổi các bit MSB này
mà không sinh ra các sai lệch không thể chấp nhận được đối với dữ liệu.
Từ các thuộc tính khác nhau, trong mỗi bộ trong quan hệ r, được chọn một cách
tựa ngẫu nhiên dựa trên khóa thủy vân K và khóa chính của bộ để xây dựng thủy vân rw.
Một kẻ tấn công muốn gỡ bỏ tất cả các bit thủy vân thì sẽ phải xóa tất cả các bộ và/hoặc
các thuộc tính từ dữ liệu đã thủy vân. Lược đồ thủy vân bền vững trước các tấn công gỡ
bỏ hoặc xóa tất cả các bit thủy vân khi η tham số sinh thủy vân càng lớn.
Máy tính hiện nay thường biểu diễn và xử lý bốn kiểu dữ liệu cơ bản tại các địa chỉ
bộ nhớ: số, datetime, ký tự và Boolean. Các kiểu dữ liệu này khi biểu diễn trong máy tính
đều có dạng là một chuỗi các bit. Bit MSB của một chuỗi bit thông thường là bit trái nhất
và có trọng số lớn nhất. Tuy nhiên, khi ta xét đến các kiểu dữ liệu cụ thể thì việc xác định
các bit MSB lại phụ thuộc vào các kiểu. Đối với dữ liệu kiểu số (nguyên hoặc thực) có dấu
thì có thể quay trái một bit để tránh bit dấu và bit trái nhất là bit MSB. Đối với dữ liệu kiểu
ký tự, giả sử l là độ dài xâu ký tự, khi đó ta chọn ký tự thứ (j mod l), với j là thuộc tính
được chọn để lấy bit MSB bằng cách lấy bit trái nhất của ký tự này. Giả sử có một thuộc
L. T. B. Hương / Lược đồ thủy vân dựa vào bit ý nghĩa nhất để bảo vệ bản quyền công khai cho các…
76
tính có kiểu là ký tự với giá trị là “Trường Đại học Sư phạm Hà Nội 2 Nhân văn - Khai
phóng - Hội nhập”. Đầu tiên, chọn ký tự thứ (j mod l) với j =13, l =60. Đây là kí tự “ọ” và
có mã unicode là 7885. Dạng nhị phân của kí tự là 1111011001101, nên bit trái nhất có giá
trị là 1. Vậy bit MSB của giá trị thuộc tính thủy vân cần tìm là 1.
Đầu vào của thuật toán phát hiện thủy vân là các tham số r’, K, η, rw, để phát hiện
thủy vân đối với quan hệ đáng ngờ r’, tham số sinh thủy vân η được sử dụng trong lược đồ
thủy vân, là tham số phát hiện thủy vân và bằng tỷ lệ thấp nhất các bit thủy vân được
phát hiện đúng. Để điều khiển độ tin cậy của thuật toán phát hiện thủy vân và độ bền vững
của thủy vân đã nhúng dựa vào hai tham số η, , trong đó tham số nằm trong khoảng (0.5,
1). Do đó, khi chứng minh bản quyền công khai cho các cơ sở dữ liệu quan hệ và để tăng
độ bền vững của thủy vân thì tất cả các bit MSB đã tìm được trong quan hệ thủy vân r’
không cần phải trùng với các bit tương ứng trong rw, mà chỉ cần tỷ lệ phần trăm trùng khớp
lớn hơn là được. Tức là trong Thuật toán 2 thỏa mãn match_count / total_count >
”.
Thuật toán 1: Nhúng thủy vân
Input: Quan hệ r, khóa thủy vân K và tham số tạo thủy vân η (η ≤ )
Output: Quan hệ thủy vân rw
1. For i = 1 to do
2. Xây dựng một bộ ti trong rw có cùng khóa chính với ri, ti.P = ri.P
3. for k = 1 to η do // sinh giá trị cho η thuộc tính của rw
4. j = H(Kri.P ) mod // chọn thuộc tính
5. if (ri.Aj có kiểu dữ liệu là kiểu số) then
6. q = ri.Aj quay trái 1 bit // tránh bit dấu
7. ti.Wk = MSB của q
8. end if
9. if (ri.Aj có kiểu dữ liệu là datetime) then
10. q = year(ri.Aj )
11. ti.Wk = MSB của q
12. end if
13. if (ri.Aj có kiểu dữ liệu là xâu ký tự) then
14. q = charAt(ri.Aj, j mod length(ri.Aj)) // charAt(ri.Aj, p): ký tự thứ p trong ri.Aj
15. ti.Wk = MSB của q
16. end if
17. if (ri.Aj có kiểu dữ liệu là Boolean) then
18. ti.Wk = ri.Aj
19. end if
20. xóa thuộc tính thứ j trong ri
21. end for
22. end for
Thuật toán 2: Phát hiện thủy vân
Input: Quan hệ nghi ngờ r’, K, η (η ≤ ), thủy vân rw và (0.5 < < 1)
Output: {true, false}
1. match_count = 0
2. total_count = 0
3. for i = 1 to do
4. tìm một bộ ti trong rw có cùng khóa chính với r’i, ti.P = r’i.P
Vinh University Journal of Science Vol. 53, No. 3A/2024
77
5. for k = 1 to η do // sinh giá trị cho η thuộc tính của r’w
6. total_count = total_count + 1
7. j = H(Kr’i.P ) mod
8. if (r’i.Aj có kiểu dữ liệu là kiểu số) then
9. q = r’i.Aj quay trái 1 bit
10. w = MSB của q
11. End if
12. if (r’i.Aj có kiểu dữ liệu là datetime) then
13. q = year(r’i.Aj)
14. w = MSB của q
15. End if
16. if (r’i.Aj có kiểu dữ liệu là xâu ký tự) then
17. q = charAt(r’i.Aj, j mod length(r’i.Aj))
18. w = MSB của q
19. End if
20. if (r’i.Aj có kiểu dữ liệu là Boolean) then
21. w = r’i.Aj
22. End if
23. if (ti.Wk == w) then // so sánh rw và r’w
24. match_count = match_count + 1
25. End if
26. xóa thuộc tính thứ j của r’i
27. end for
28. end for
29. if match_count/total_count > then
30. return true
31. else
32. return false
33. End if
3. Đánh giá thử nghiệm
Để kiểm định tính bền vững và chi phí đối với lược đồ thủy vân cải tiến, chúng tôi
đã tiến hành thử nghiệm đối với cơ sở dữ liệu quan hệ về dân số của huyện Đông Anh,
thành phố Hà Nội. Dữ liệu thử nghiệm là một quan hệ gồm 2000 bộ, có một thuộc tính
khóa chính là căn cước công dân và 9 thuộc tính có các kiểu dữ liệu khác nhau: họ và tên,
năm sinh, giới tính, nơi sinh, địa chỉ, chủ hộ, tổng thu nhập, nghề nghiệp, trình độ chuyên
môn. Thử nghiệm với các cập nhật thông thường: thêm, xóa và sửa. Các tấn công này là
hoàn toàn ngẫu nhiên, giả sử không tấn công trên thuộc tính khóa chính và mỗi tấn công
thử nghiệm 20 lần.
Kết quả của tấn công thêm bộ được thể hiện trong Hình 1. Nếu chọn tham số
trong trường hợp xấu nhất là 50% và 100% bộ được thêm thì vẫn khẳng định được bản
quyền của dữ liệu, do mỗi bộ được xử lý độc lập với các bộ khác dựa vào khóa chính.
Kết quả của tấn công sửa được thể hiện trong Hình 2. Theo kết quả thử nghiệm,
ngay cả khi quan hệ bị sửa 50% và chọn lớn hơn hoặc bằng 75% thì bản quyền dữ liệu
vẫn khẳng định được, do kẻ tấn công có thể không sửa vào các bit MSB.