Một lược đồ thủy vân cơ sở dữ liệu quan hệ với dữ liệu phân loại

Tóm tắt Một lược đồ thủy vân cơ sở dữ liệu quan hệ với dữ liệu phân loại: ...NG, BÙI THẾ HỒNG trên từng nhóm. Mỗi nhóm này có thể được xem như là một nhóm ảo mà không thay đổi vị trí vật lý của các bộ. Sau khi nhóm, tất cả các bộ trong mỗi nhóm được sắp xếp theo khóa chính của nó. Giống như khi chia nhóm, việc sắp xếp này không làm thay đổi vị trí vật lý của các bộ. Mỗi ...ại bỏ khóa chính của bộ rk1 và rkj khỏi cột T và sắp lại thứ tự 24. end for 25. if W ∗ ==W then 26. V = true 27. else 28. V = false 29. end if 30. end for Giải thích Thuật toán 2: Phát hiện thủy vân trong từng nhóm được thực hiện dựa trên việc so sánh 2 chuỗi thủy vân. Chuỗi thứ nhất được t...ệ, cần phải lựa chọn tham số g (số nhóm thủy vân) sao cho phù hợp với số bộ trong quan hệ. Số các bộ của quan hệ và số nhóm phải được chọn như thế nào đó để có thể thỏa mãn đồng thời hai tính chất. Đó là tăng cường tính bền vững của thủy vân và tối đa số các bộ có thể tiếp tục được sử dụng. Có th...

pdf12 trang | Chia sẻ: havih72 | Lượt xem: 322 | Lượt tải: 0download
Nội dung tài liệu Một lược đồ thủy vân cơ sở dữ liệu quan hệ với dữ liệu phân loại, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
hứ tự của các bộ trong quan
hệ.
Trong lược đồ thủy vân đề xuất, tư tưởng chính của các thuật toán dựa vào [11]. Giống
như lược đồ thủy vân [11], quá trình nhúng thủy vân và phát hiện thủy vân được thực hiện
4 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
trên từng nhóm. Mỗi nhóm này có thể được xem như là một nhóm ảo mà không thay đổi vị
trí vật lý của các bộ. Sau khi nhóm, tất cả các bộ trong mỗi nhóm được sắp xếp theo khóa
chính của nó. Giống như khi chia nhóm, việc sắp xếp này không làm thay đổi vị trí vật lý của
các bộ. Mỗi nhóm sau đó sẽ được xử lý một cách độc lập.
Trong thuật toán nhúng thủy vân của [11], việc chọn các cặp bộ để nhúng thủy vân được
thực hiện tuần tự cho nên rất dễ bị phát hiện. Khác với cách chọn này của [11], với mỗi cặp,
chỉ lấy bộ thứ nhất theo thứ tự, còn bộ thứ hai của cặp bộ này được chọn dựa vào khóa nhúng
thủy vân K và số bộ trong nhóm Gk. Quá trình chọn cặp để đổi chỗ này sẽ giúp tăng độ an
toàn cho thủy vân được nhúng trong quan hệ. Đây là điểm mạnh của lược đồ thay cho lược
đồ trong [11] việc đổi chỗ được tiến hành cho các bộ một cách cố định sẽ tạo cơ hội tấn công
cao hơn từ những kẻ muốn sửa đổi quan hệ. Từ đó, việc đổi chỗ hai bộ không phải cố định
thể hiện sự vượt trội hơn so với việc chỉ đổi chỗ cố định. Thêm vào nữa, việc đổi chỗ các cặp
bộ dựa vào khóa bí mật K và tham số g, mà K và g chỉ chủ sở hữu dữ liệu biết sẽ tăng tính
bảo mật cho quan hệ được nhúng. Từ đó, thực sự kẻ tấn công khó có thể tìm ra vị trí các cặp
bộ được đổi chỗ cho nhau.
Giả sử có một quan hệ với một khóa chính là P , γ thuộc tính và có dữ liệu phân loại được
ký hiệu là R(P,A1, A2, ..., Aγ) và K là khóa thủy vân. Bảng 1 là các ký hiệu và tham số sẽ
được sử dụng trong lược đồ thủy vân đề xuất.
Bảng 1. Các ký hiệu và các tham số
Ký hiệu Ý nghĩa của ký hiệu
γ Số thuộc tính của quan hệ
ω Số bộ của quan hệ
g Số nhóm của quan hệ
hi Giá trị hash của bộ thứ i trong quan hệ hoặc trong 1 nhóm
Hi Giá trị hash của khóa thủy vân và khóa chính của bộ thứ i trong quan hệ
hoặc trong 1 nhóm
H Giá trị hash của nhóm
Gk Nhóm thứ k
qk Số bộ trong nhóm thứ k
ri Bộ thứ i trong quan hệ hoặc trong một nhóm
ri.Aj Giá trị thuộc tính thứ j của bộ thứ i trong quan hệ hoặc trong một nhóm
K Khóa nhúng thủy vân
W Chuỗi thủy vân nhúng trong một nhóm
W [i] Bít thủy vân thứ i trong chuỗi thủy vân W
W ∗ Thủy vân được trích ra từ một nhóm
W ∗[i] Bít thủy vân thứ i trong chuỗi thủy vân W ∗
V Kết quả xác minh thủy vân
3.1. Nhúng thủy vân
Quá trình nhúng thủy vân vào quan hệ được thực hiện bằng Thuật toán 1 dưới đây.
MỘT LƯỢC ĐỒ THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ VỚI DỮ LIỆU PHÂN LOẠI 5
Thuật toán 1. Nhúng thủy vân
1. for k = 1 to g do // khởi tạo các chỉ số và các nhóm
2. qk = 0
3. Gk = ∅
4. end for
5. for i = 1 to ω do // chia các bộ thành g nhóm
6. hi = HASH(K, ri.A1, ri.A2, ..., ri.Aγ) // giá trị hash của bộ thứ i
7. Hi = HASH(K, ri.p)
8. k = Hi mod g // xác định nhóm
9. ri → Gk // đưa bộ ri vào nhóm Gk
10. qk ++
11. end for
12. for k = 1 to g do
13. Lưu khóa chính của các bộ trong Gk vào một cột trung gian T và sắp thứ tự
14. H = HASH(K,hk1 , hk2 , ..., hkqk )//hki : giá trị hash của bộ nhóm k sau sắp thứ tự
15. W = ExtractBits(H, bqk/2c) // bxc: phần nguyên của x
16. for i = 1 to bqk/2c do
17. j = HASH(K) mod (qk − 2i+ 1) + 2
18. If (hk1 ≤ hkj and W [i] == 1) or (hk1 > hkj and W [i] == 0) then
19. đổi chỗ bộ rk1 và rkj của quan hệ
20. end if
21. Loại bỏ khóa chính của bộ rk1 và rkj ra khỏi cột T và sắp lại thứ tự
22. end for
23. ExtractBits(H, ` ) {
24. if length(H) > ` then
25. W được gán bằng ` bit đầu tiên của H
26. else
27. m = `− length(H)
28. W được gán bằng H ghép với ExtractBits (H,m)
29. end if
30. return W }
31. end for
Giải thích Thuật toán 1: Đầu tiên, các bộ của quan hệ được chia thành g nhóm theo khóa
chính và khóa nhúng thủy vân K. Việc chia nhóm này chỉ là một hoạt động ảo, không làm
6 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
thay đổi vị trí vật lý của các bộ trong quan hệ. Đồng thời, tính các giá trị hash hi của các
thuộc tính (trừ khóa chính) của bộ ri ghép với khóa thủy vân K, trong đó mỗi giá trị thuộc
tính là một chuỗi bit.
Tiếp theo là việc nhúng thủy vân vào từng nhóm. Thủy vân là một chuỗi W gồm bqk/2c
bit được trích ra bằng hàm ExtractBits(H, bqk/2c) từ chuỗi bít H, trong đó H là giá trị hash
của nhóm được tính từ các giá trị hi ghép với khóa K. Việc nhúng thủy vân thực chất là việc
đổi chỗ hai bộ dựa trên giá trị của chuỗi bit thủy vân W và giá trị hash của các bộ này. Các
cặp bộ được chọn phụ thuộc vào giá trị hash khóa thủy vân K và số bộ trong nhóm. Sau đó
cặp được chọn có thể bị đổi chỗ hay không tùy thuộc vào bít thủy vân W của cặp.
3.2. Phát hiện thủy vân
Để kiểm tra tính toàn vẹn của quan hệ cũng như phát hiện xem có các giả mạo nào trong
quan hệ đã nhúng thủy vân hay không thì cần phải phát triển một thuật toán để tìm lại thủy
vân. Thuật toán 2 sau đây được sử dụng để phát hiện thủy vân đã được nhúng trong quan hệ
bằng Thuật toán 1. Thuật toán này cần phải biết khóa thủy vân Kvà số nhóm g.
Thuật toán 2. Phát hiện thủy vân
1. for k = 1 to g do // khởi tạo các chỉ số và các nhóm
2. qk = 0
3. Gk = ∅
4. end for
5. for i = 1 to ω do // chia các bộ thành g nhóm
6. hi = HASH(K, ri.A1, ri.A2, ..., ri.Aγ)
7. Hi = HASH(K, ri.p)
8. k = Hi mod g // xác định nhóm
9. ri → Gk // đưa bộ ri vào nhóm Gk
10. qk ++
11. end for
12. for k = 1 to g do
13. Lưu khóa chính của các bộ trong Gk vào một cột trung gian T và sắp thứ tự
14. H = HASH(K,hk1 , hk2 , ..., hkqk )// hki : giá trị hash của bộ nhóm k sau sắp thứ tự
15. W = ExtractBits(H, bqk/2c) // bxc: phần nguyên của x
16. for i = 1 to bqk/2c do
17. j = HASH(K) mod (qk − 2i+ 1) + 2
18. If hk1 < hkj then
19. W ∗[i] = 0
20. else
MỘT LƯỢC ĐỒ THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ VỚI DỮ LIỆU PHÂN LOẠI 7
21. W ∗[i] = 1
22. end if
23. Loại bỏ khóa chính của bộ rk1 và rkj khỏi cột T và sắp lại thứ tự
24. end for
25. if W ∗ ==W then
26. V = true
27. else
28. V = false
29. end if
30. end for
Giải thích Thuật toán 2: Phát hiện thủy vân trong từng nhóm được thực hiện dựa trên
việc so sánh 2 chuỗi thủy vân. Chuỗi thứ nhất được tính tương tự như Thuật toán 1. Chuỗi
thứ hai được rút ra từ quan hệ cần xác minh bằng cách so sánh giá trị hash của các cặp bộ
trong nhóm.
Nếu như kết quả so sánh hai chuỗi là trùng nhau thì ta kết luận không có giả mạo, ngược
lại thì có giả mạo trong nhóm đang xét. Nếu tất cả các nhóm không có giả mạo thì kết luận
quan hệ đem xác minh là toàn vẹn. Ngược lại, quan hệ là không toàn vẹn và xác minh các
nhóm là không toàn vẹn.
Từ thuật toán nhúng thủy vân và phát hiện thủy vân, có thể dễ dàng nhận thấy độ phức
tạp tính toán của cả hai thuật toán có bậc bằng số các bộ trong quan hệ, tức là bậc O(ω).
4. TÍNH ĐÚNG ĐẮN
Trong phần này sẽ chứng minh tính đúng đắn của các thuật toán đề xuất. Để chứng minh
tính đúng đắn của định lý, ta có mệnh đề sau.
Mệnh đề 1. Nếu trong thuật toán nhúng, một bộ thuộc vào nhóm Gk nào đó và giá trị khóa
chính của nó không bị thay đổi thì bộ này vẫn thuộc nhóm Gk trong thuật toán phát hiện
thủy vân.
Chứng minh. Giả sử có một quan hệ có ω bộ với một khóa chính là P, γ thuộc tính và có
dữ liệu phân loại, ký hiệu là R(P,A1, A2, ..., Aγ). Xét bộ ri(p, a1, a2, ..., aγ) trong quan hệ R.
Theo giả thiết, khóa chính p không bị thay đổi khi quan hệ bị tấn công và chủ sở hữu quan
hệ hoặc người có thẩm quyền biết về khóa bí mật K và số nhóm phân chia g.
Trong thuật toán nhúng thủy vân, ta có:
+ Theo tính chất của hàm HASH;
+ Hi = HASH(K, ri.p) chỉ phụ thuộc vào giá trị các tham số K và ri.p;
+ Chỉ số nhóm k = Hi mod g;
=⇒ ri ∈ Gk.
Trong thuật toán phát hiện thủy vân, theo giả thiết ta có ri.p không thay đổi và tham số
8 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
K, g đã biết trước và không thay đổi. Khi đó:
+ Theo tính chất của hàm HASH;
+ Hi = HASH(K, ri.p) chỉ phụ thuộc vào giá trị các tham số K và ri.p;
+ Mặt khác, việc xác định chỉ số nhóm của ri theo công thức k = Hi mod g;
+ Tham số g,K, ri.p không thay đổi;
=⇒ ri ∈ Gk.
Do đó, ri ∈ Gk trong cả hai thuật toán nhúng và phát hiện thủy vân. Mà ri là một bộ
được chọn ngẫu nhiên trong quan hệ R. Vì vậy, ta có điều phải chứng minh. 
Định lý 1. Nếu một quan hệ có dữ liệu phân loại không bị giả mạo hoặc xuyên tạc thì thủy
vân đã nhúng vào quan hệ bằng Thuật toán 1 và thủy vân được trích ra từ quan hệ bằng
Thuật toán 2 là như nhau.
Chứng minh. Giả sử có một quan hệ có ω bộ với một khóa chính là P, γ thuộc tính và có dữ
liệu phân loại, ký hiệu là R(P,A1, A2, ..., Aγ). Theo giả thiết, quan hệ không bị thay đổi. Vì
vậy, theo Mệnh đề 1 ω bộ được phân vào g nhóm Gi(i = 1, 2, ..., g) là giống nhau trong thuật
toán nhúng và phát hiện thủy vân.
Giả sử xét nhóm Gk, có qk bộ. W (W [1],W [2], ...,W [bqk/2c]) là thủy vân được sinh ra
trong quá trình nhúng thủy vân, trong đó
W [i] ={0, 1}, i = 1, 2, ..., bqk/2c; W ′(W ′[1],W ′[2], ...,W ′[bqk/2c])
là thủy vân được sinh ra trong quá trình phát hiện thủy vân, trong đó W ′[i] = {0, 1}.
W ∗(W ∗[1],W ∗[2], ...,W ∗[bqk/2c]) là thủy vân được trích ra từ quan hệ trong thuật toán phát
hiện thủy vân, trong đó W ∗[i] = {0, 1}. Vì lược đồ thủy vân sử dụng duy nhất một cách sắp
thứ tự cho cả thuật toán nhúng và phát hiện thủy vân cho nên các bộ ri (i = 1, 2, ..., qk)
được sắp thứ tự như nhau trong phần nhúng và phát hiện thủy vân.
Trong phần nhúng, theo tính chất của hàm HASH, và cách tính:
+ hi = HASH(K, ri.A1, ri.A2, ..., ri.Aγ);
+ H = HASH(K,h′1, h′2, ..., h′qk);
trong đó, h′j là giá trị hi sau khi sắp thứ tự. Sử dụng hàm ExtractBits với tham số đầu vào
là giá trị của H ta sẽ sinh ra được chuỗi thủy vân nhúng W :
W = ExtractBits(H, bqk/2c).
Trong phần phát hiện, tương tự như trên ta có:
+ h′i = HASH(K, ri.A1, ri.A2, ..., ri.Aγ);
+ H ′ = HASH(K,h′1, h′2, ..., h′qk);
+ W ′ = ExtractBits(H ′, bqk/2c);
+ Vì quan hệ không bị giả mạo hoặc xuyên tạc và cũng được sắp thứ tự như nhau cho
nên các ri.Aj là không thay đổi trong phần phát hiện.
=⇒ h′i = hi ∀i = 1, 2, ..., qk ⇒ H ′ = H ⇔W ′ =W. (1)
Xét thuật toán nhúng thủy vân:
MỘT LƯỢC ĐỒ THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ VỚI DỮ LIỆU PHÂN LOẠI 9
If (hk1 ≤ hkj and W [i] == 1) or (hk1 > hkj and W [i] == 0) then
đổi chỗ bộ rk1 và rkj của quan hệ
Như vậy, ta xét các điều kiện để đổi chỗ bộ rk1 và rkj :
+ hk1 < hkj và W [i] = 0 thì không đổi chỗ.
+ hk1 hkj .
+ hk1 ≥ hkj và W [i] = 0 thì đổi chỗ. Sau đổi chỗ thì hk1 ≤ hkj .
+ hk1 ≥ hkj và W [i] = 1 thì không đổi chỗ.
⇔ hk1 ≥ hkj thì W [i] = 1 và hk1 < hkj thì W [i] = 0. (2)
Các bit W [i] của thủy vân W lần lượt được nhúng vào trong nhóm Gk bằng việc đổi chỗ
các bộ trong quan hệ ban đầu như đã xét trong các trường hợp ở trên.
Tương tự, ta xét quá trình trích thủy vân W ∗ trong thuật toán phát hiện:
If hk1 < hkj then
W ∗[i] = 0 (3)
else
W ∗[i] = 1
Từ (3) =⇒ hk1 < hkj thì W ∗[i] = 0 và khi hk1 ≥ hkj thì W ∗[i] = 1. (4)
Từ (2), (4) và do quan hệ không bị thay đổi cho nên W ∗[i] = W [i]. Vì W ∗[i], W [i] là bất
kỳ nên W ∗ =W . (5)
Lược đồ thủy vân thực hiện trên nhóm Gk(k = 1, 2, ..., g) và các nhóm độc lập với nhau.
(6)
Từ (1), (5) và (6), ta có điều phải chứng minh. 
5. CÂN ĐỐI GIỮA SỐ BỘ TRONG QUAN HỆ VÀ SỐ NHÓM
Với lược đồ đề xuất ở trên, nếu có một nhóm bị phát hiện là giả mạo thì người ta có thể
loại nhóm đó đi và các nhóm không bị giả mạo sẽ tiếp tục được sử dụng. Việc xác định một
nhóm nào đó có bị giả mạo hay không có thể được thực hiện trong Thuật toán 2.
Trước khi thủy vân một quan hệ, cần phải lựa chọn tham số g (số nhóm thủy vân) sao
cho phù hợp với số bộ trong quan hệ. Số các bộ của quan hệ và số nhóm phải được chọn như
thế nào đó để có thể thỏa mãn đồng thời hai tính chất. Đó là tăng cường tính bền vững của
thủy vân và tối đa số các bộ có thể tiếp tục được sử dụng. Có thể thấy ngay là không thể
nào thỏa mãn được đồng thời hai tính chất này. Điều này được khẳng định bằng các Mệnh
đề 2 và Mệnh đề 3. Vì vậy, sẽ phải có một sự thỏa hiệp để cân đối giữa hai tính chất trên.
Số lượng nhóm nên được chọn vừa đủ tương ứng với số lượng các bộ của quan hệ để vừa có
các chuỗi thủy vân bền vững trong mỗi nhóm và vừa có thể tiếp tục sử dụng được nhiều bộ
nhất. Nhưng nếu cần phải tăng cường tính bền vững của thủy vân thì nên chọn g nhỏ để số
bộ trong mỗi nhóm sẽ tăng lên cùng chiều với độ bền vững. Nếu ngược lại, tức là nhu cầu tiếp
tục sử dụng những bộ không bị xâm phạm là cấp bách thì cần phải chọn g lớn để số lượng
10 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
các bộ phải loại bỏ sẽ ít hơn. Trong các thử nghiệm, với các quan hệ có khoảng 10.000 bộ cho
thấy g nằm trong khoảng từ 6 đến 10 là những lựa chọn tốt cho cả hai tính chất đã đề cập
trên đây.
Mệnh đề 2. Cho một quan hệ có dữ liệu phân loại được thủy vân bằng Thuật toán 1 và 2.
Nếu quan hệ R có kích thước không đổi và số nhóm g tăng thì:
1. Số lượng bộ có thể tiếp tục sử dụng dữ liệu tăng.
2. Độ bền vững của thủy vân giảm.
Chứng minh. Giả sử có một quan hệ có ω bộ với một khóa chính là P, γ thuộc tính và có dữ
liệu phân loại, ký hiệu là R(P,A1, A2, ..., Aγ). Theo giả thiết số bộ ω là cố định.
1. Chứng minh số lượng bộ có thể tiếp tục sử dụng dữ liệu tăng.
Theo giả thiết ta có:
+ ω bộ được phân vào g nhóm Gk(k = 1, 2, ..., g) bằng thuật toán nhúng và phát hiện
thủy vân.
+ Số bộ ω là cố định.
Theo Thuật toán 1 và 2, số bộ trung bình trong mỗi nhóm Gk là qk(qk = ω/g).
Khi g tăng lên thì số bộ trung bình trong mỗi nhóm Gk là βk. Ta dễ dàng nhận thấy
βk < qk(ω/g
′ < ω/g, với g′ là số nhóm sau khi tăng).
Giả sử quan hệ có sửa đổi xảy ra và không mất tổng quát, dựa vào Thuật toán 2, phát
hiện nhóm Gk bị sửa đổi. Hay số lượng bộ có thể tiếp tục sử dụng dữ liệu của quan hệ R sẽ
loại đi số bộ trong nhóm Gk. Dễ dàng nhận thấy số lượng bộ dữ liệu trung bình bị loại đi
trong Gk sau khi g tăng nhỏ hơn trước khi tăng g (giảm đi qk − βk bộ). Khi đó số lượng bộ
có thể tiếp tục sử dụng dữ liệu tăng lên qk − βk bộ.
2. Chứng minh độ bền vững của thủy vân giảm.
Ta có thể thấy, độ bền vững của thủy vân trong Thuật toán 1 và 2 dựa vào độ dài chuỗi
thủy vân W . Như vậy sẽ chứng minh độ bền vững dựa vào độ dài của W .
Theo giả thiết ta có: g tăng =⇒ số lượng bộ dữ liệu trung bình trong nhóm Gk giảm, suy
ra chuỗi thủy vân W và chuỗi thủy vân trích ra W ∗ của Gk có độ dài sẽ giảm đi.
Suy ra điều phải chứng minh. 
Mệnh đề 3. Cho quan hệ R có dữ liệu phân loại được thủy vân bằng Thuật toán 1 và 2 với
số nhóm không đổi, nếu như kích thước quan hệ tăng thì:
1. Số lượng bộ có thể tiếp tục sử dụng dữ liệu giảm.
2. Độ bền vững của thủy vân tăng.
Chứng minh. Giả sử có một quan hệ có ω bộ với một khóa chính là P, γ thuộc tính và có dữ
liệu phân loại, ký hiệu là R(P,A1, A2, ..., Aγ). Theo giả thiết g cố định.
1. Chứng minh: Số lượng bộ có thể tiếp tục sử dụng dữ liệu giảm.
Theo giả thiết ta có:
+ ω bộ được phân vào g nhóm Gk (k = 1, 2, ..., g) bằng thuật toán nhúng và phát hiện
MỘT LƯỢC ĐỒ THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ VỚI DỮ LIỆU PHÂN LOẠI 11
thủy vân.
+ Số nhóm g là cố định nên số phần tử trong nhóm Gk là qk.
Khi ω tăng lên thì số lượng phần tử trong Gk là qk + βk (với βk là số bộ tăng thêm của
Gk khi ω tăng).
Giả sử quan hệ có sửa đổi xảy ra và không mất tổng quát, dựa vào Thuật toán 2, phát
hiện nhóm Gk bị sửa đổi. Khi đó, số lượng bộ có thể tiếp tục sử dụng dữ liệu của quan hệ R
sẽ loại đi số bộ trong nhóm Gk. Hay số lượng bộ bị loại đi trong Gk sau khi ω tăng lớn hơn
trước khi tăng ω là βk bộ. Suy ra, số lượng bộ có thể tiếp tục sử dụng dữ liệu giảm đi βk bộ.
2. Chứng minh: Độ bền vững của thủy vân tăng.
Ta có thể thấy, độ bền vững của thủy vân trong Thuật toán 1 và 2 dựa vào độ dài chuỗi
thủy vân W . Như vậy sẽ chứng minh độ bền vững dựa vào độ dài của W .
Theo giả thiết ta có: ω tăng, suy ra số lượng bộ dữ liệu trong nhóm Gk tăng =⇒ chuỗi
thủy vân W và chuỗi thủy vân trích ra W ∗ của Gk có độ dài sẽ tăng lên.
Suy ra điều phải chứng minh. 
6. KẾT LUẬN
Lược đồ thủy vân đề xuất làm việc trên các nhóm trong quan hệ của cơ sở dữ liệu quan
hệ. Khóa thủy vân và tham số g (số lượng nhóm) được nhúng vào cơ sở dữ liệu quan hệ là
một dữ liệu mật. Trong lược đồ này cần tạo ra sự cân bằng giữa độ an toàn và chi phí tính
toán.
Kích thước của cơ sở dữ liệu càng lớn thì độ bền vững của lược đồ càng tốt nhưng ngược
lại số lượng bộ có thể tiếp tục sử dụng dữ liệu giảm và chi phí tính toán lớn. Trong khi đó,
số nhóm thủy vân càng lớn thì số lượng bộ có thể tiếp tục sử dụng dữ liệu càng tốt nhưng độ
bền vững của lược đồ thủy vân giảm. Vì vậy trong lược đồ này việc chọn g được xem xét để
cân đối với kích thước của quan hệ.
Lược đồ đề xuất sử dụng các nhóm độc lập trong quan hệ, có những điểm mạnh sau:
- Nhúng thủy vân không làm thay đổi giá trị của các bộ.
- Phát hiện và khoanh vùng giả mạo trên từng nhóm độc lập. Do vậy, các nhóm còn lại
trong cơ sở dữ liệu vẫn còn có thể được sử dụng nếu cần thiết.
TÀI LIỆU THAM KHẢO
[1] A. Hamadou, X. Sun, S. A. Shah, L. Gao, A weight-based semi-fragile watermarking scheme for
integrity verification of relational data, International Journal of Digital Content Technology
and its Applications 5 (8) (2011).
[2] Agrawal, Kiernan, Haas, Watermarking relational data: framework, algorithms amd analysis,
The VLDB Journal 12 (2) (2003) 157–169.
[3] Collberg and Thomborson, Watermarking, tamper- proofing, and obfuscation - tools for software
protection, IEEE Trans. Software Engrg 28 (8) (2002) 735–746.
12 LƯU THỊ BÍCH HƯƠNG, BÙI THẾ HỒNG
[4] P. Cousot, R. Cousot, An abstract interpretation -based framework for software watermarking,
31st ACM SIGPLANSIGACT Symposium On Principles Of Programming Languages,
POPL’04, Venice, Italy, January 14-16, 2004.
[5] H. M. Sardroudi, S. Ibrahim, O. Zanganeh, Robust database watermarking technique over nu-
merical data, JCIS 1 1 (2011) 30–40.
[6] J. Lafaye, An analysis of database watermarking security, 3rd International Symposium on In-
formation Assurance and Security, Manchester, United Kingdom, August 29-31, 2007 (IEEE
Computer Society 2007).
[7] R. K. Bedi, P. Gujarathi, P. Gundecha, A unique approach for watermarking non-numeric rela-
tional database, International Journal of Computer Applications 36 (7) (2011) (0975–8887).
[8] Raju Halder, Shantanu Pal, Agostino Cortesi, Watermarking techniques for relational databases:
survey, classification and comparison, Journal of Universal Computer Science 16 (21) (2010)
3164–3190.
[9] Sion, Proving ownership over categorical data, Proceedings of the IEEE International Confer-
ence on Data Engineering IEEE ICDE 2004, Boston, Massachusetts, March 2004 (584–596).
[10] Sukriti Bhattacharya, Agostino Cortesi, A distortion free watermark framework for relationnal
databases, Proc. 4th International Conference on Software and Data technology (IC-
SOFT) (2), Sofia, Bulgaria, 2009 (229–234).
[11] Yingjiu Li, Huiping Guo, Sushil Jajodia, Tamper detection and localization for categorical data
using fragile watermarks, DRM ’04: Proceedings of the 4th ACM Workshop on Digital
Rights Management, New York, NY, USA, 2004 (73–82).
[12] Phan Đình Diệu, Lý thuyết mật mã và an toàn thông tin, NXB Đại học Quốc gia Hà Nội,
2002.
[13] Bùi Thế Hồng, Nguyễn Thị Thu Hằng, Lưu Thị Bích Hương, Thủy vân cơ sở dữ liệu quan hệ,
Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên 52 (4) (2009) 56–59.
[14] Bùi Thế Hồng, Lưu Thị Bích Hương, Thủy vân cơ sở dữ liệu quan hệ bằng kỹ thuật tối ưu, Kỷ
yếu hội thảo Quốc gia lần thứ XII: Một số vấn đề chọn lọc của Công nghệ thông tin và
truyền thông, Đồng Nai, 05-06 tháng 8 năm 2009, (NXB Khoa học và Kỹ thuật, Hà Nội (2010)
443–457).
[15] Lưu Thị Bích Hương, Bùi Thế Hồng, Bảo vệ bản quyền công khai cho các cơ sở dữ liệu, Kỷ
yếu hội thảo Quốc gia lần thứ XIII: Một số vấn đề chọn lọc của Công nghệ thông tin và
truyền thông, Hưng Yên, 19-20 tháng 8 năm 2010, (NXB Khoa học và Kỹ thuật, Hà Nội (2011)
41–50).
Ngày nhận bài 23 - 8 - 2012
Ngày lại sau sửa ngày 07 - 4 - 2013

File đính kèm:

  • pdfmot_luoc_do_thuy_van_co_so_du_lieu_quan_he_voi_du_lieu_phan.pdf