Vi»c sß dụng h» thŁng lưu trœ ngoài đ¢ trở n¶n phŒ bi‚n không ch¿ cho c¡c doanh
nghi»p mà cÆn cho c¡c c¡ nh¥n. Đặc bi»t cùng với sự ph¡t tri”n cıa đi»n to¡n đ¡m
m¥y, người dùng lưu trœ dœ li»u ở c¡c nhà cung c§p dịch vụ ngày càng nhi•u. Læi th‚
cıa đi»n to¡n đ¡m m¥y và c¡c h» thŁng lưu trœ ngoài là vi»c lưu trœ dœ li»u không
cÆn bị giới h⁄n trong h» thŁng m¡y t‰nh cıa c¡ nh¥n/ tŒ chøc người dùng mà đưæc
cung c§p bởi c¡c nhà cung c§p dịch vụ chuy¶n nghi»p. Người dùng có th” sß dụng
c¡c dịch vụ cıa nhà cung c§p mºt c¡ch d„ dàng mà không cƒn quan t¥m đ‚n vi»c
cài đặt, c§u h nh, b£o tr h» thŁng, mở rºng tài nguy¶n,. B¶n c⁄nh c¡c læi ‰ch, người
dùng cƒn c¥n nh›c c¡c kh‰a c⁄nh v• b£o m“t và t‰nh ri¶ng tư. Người dùng không n¶n
tin c“y nhà cung c§p dịch vụ hoàn toàn mà n¶n c¥n nh›c vi»c b£o v» dœ li»u cıa
m nh
125 trang |
Chia sẻ: tranhieu.10 | Lượt xem: 959 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận án Kiểm định công khai đảm bảo tính riêng tư cho dữ liệu lưu trữ ngoài, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠI HỌC QUỐC GIA TPHCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
ĐẶNG HẢI VÂN
KIỂM ĐỊNH CÔNG KHAI ĐẢM BẢO TÍNH RIÊNG TƯ
CHO DỮ LIỆU LƯU TRỮ NGOÀI
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
Tp. Hồ Chí Minh, 2017
ĐẠI HỌC QUỐC GIA TPHCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
ĐẶNG HẢI VÂN
KIỂM ĐỊNH CÔNG KHAI ĐẢM BẢO TÍNH RIÊNG TƯ
CHO DỮ LIỆU LƯU TRỮ NGOÀI
Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 62.48.01.01
Phản biện 1: PGS. TS. Tôn Thất Trí
Phản biện 2: PGS. TS. Trần Công Hùng
Phản biện 3: TS. Trần Nam Dũng
Phản biện độc lập 1: PGS. TS. Nguyễn Linh Giang
Phản biện độc lập 2: PGS. TS. Trần Công Hùng
Người hướng dẫn khoa học: PGS. TS. Nguyễn Đình Thúc
Tp. Hồ Chí Minh, năm 2017
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn của PGS. TS. Nguyễn
Đình Thúc. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất
kỳ công trình nào khác.
Ký tên
Đặng Hải Vân
Con cảm ơn ba mẹ đã luôn lo lắng cho con.
Em cảm ơn thầy đã luôn tận tình hướng dẫn em.
Tôi cảm ơn những người bạn đã luôn bên cạnh và động viên tôi.
Mục lục
Danh mục các thuật ngữ tiếng Anh 5
Danh mục các từ viết tắt tiếng Anh 6
Danh mục các bảng 7
Danh mục các hình vẽ 9
1 Giới thiệu 10
1.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Mục tiêu và Bố cục luận án . . . . . . . . . . . . . . . . . . . . . . . 22
2 Cơ sở lý thuyết 28
2.1 Ma trận giả nghịch đảo . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.2 Xây dựng ma trận giả nghịch đảo trên trường hữu hạn . . . . 33
2.1.3 Thuật toán xây dựng ma trận giả khả nghịch . . . . . . . . . 40
2.1.4 Phân tích thời gian sinh ma trận giả khả nghịch và thực nghiệm 45
2
2.2 Mã xác thực thông điệp đảm bảo tính riêng tư . . . . . . . . . . . . . 49
2.2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2.2 Mô tả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2.3 Độ an toàn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.2.4 Chi phí tính toán, lưu trữ và truyền thông . . . . . . . . . . . 60
3 Kiểm định công khai đảm bảo tính riêng tư cho dữ liệu lưu trữ ngoài 64
3.1 Phương pháp 1: Dựa vào ma trận giả nghịch đảo . . . . . . . . . . . 64
3.1.1 Mô tả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.1.2 Phân tích . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.2.1 Chi phí lưu trữ và truyền thông . . . . . . . . . . . . 69
3.1.2.2 Chi phí tính toán . . . . . . . . . . . . . . . . . . . . 70
3.1.2.3 Độ an toàn . . . . . . . . . . . . . . . . . . . . . . . 72
3.1.2.4 Về việc lựa chọn tham số . . . . . . . . . . . . . . . 73
3.1.2.5 Về tính chính xác khi thực hiện kiểm định . . . . . . 74
3.1.3 Thực nghiệm đo thời gian thuật toán kiểm định dữ liệu . . . . 77
3.2 Phương pháp 2: Dựa vào mã xác thực thông điệp . . . . . . . . . . . 80
3.2.1 Mô tả giao thức tổng quát . . . . . . . . . . . . . . . . . . . . 81
3.2.2 Phân tích . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.2.1 Chi phí lưu trữ . . . . . . . . . . . . . . . . . . . . . 87
3.2.2.2 Chi phí truyền thông . . . . . . . . . . . . . . . . . . 88
3.2.2.3 Chi phí tính toán . . . . . . . . . . . . . . . . . . . . 89
3.2.3 Mô tả giao thức cụ thể . . . . . . . . . . . . . . . . . . . . . . 90
3.2.4 Áp dụng phương pháp cho cơ sở dữ liệu . . . . . . . . . . . . 92
3
3.3 So sánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4 Kết luận 99
Danh mục công trình khoa học 102
Danh mục tài liệu tham khảo 103
A Phụ lục 108
A.1 Ma trận trực giao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.2 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
A.3 Phương pháp kiểm định công khai dựa vào vị nhóm chính quy . . . . 114
A.4 Chia sẻ khóa và thay khóa . . . . . . . . . . . . . . . . . . . . . . . . 117
A.4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
A.4.2 Trường hợp 2 người dùng . . . . . . . . . . . . . . . . . . . . 118
A.4.3 Trường hợp N người dùng . . . . . . . . . . . . . . . . . . . . 120
Danh mục các thuật ngữ tiếng Anh
Bảng 1: Bảng thuật ngữ tiếng Anh
Tiếng Việt Tiếng Anh
Tổ chức thứ ba Third-party
Tính bảo mật Security
Tính riêng tư Privacy
Tính bí mật Confidentiality
Tính toàn vẹn Integrity
Nhãn Tag
Mẫu tin Record
Khối dữ liệu Block
Phần dữ liệu Sector
Tính chất đồng cấu Homomorphic property
Máy chủ Server
Chủ dữ liệu Data owner (DO)
Tổ chức thứ 3 thực hiện kiểm định Third-party auditor (TPA)
Thông tin cần thiết cho việc kiểm định Metadata
Ma trận giả nghịch đảo Pseudoinverse matrix
Mã xác thực thông điệp Message Authentication Code
Đám mây Cloud
5
Danh mục các từ viết tắt tiếng Anh
Bảng 2: Bảng từ viết tắt tiếng Anh
Từ viết tắt Từ viết đầy đủ
E-PDP Efficient Provable Data Possession (Phương pháp đề xuất bởi nhóm
tác giả Ateniese, Burns, Curtmola và Herring [1])
S-PDP Strong Provable Data Possession (Phương pháp đề xuất bởi nhóm
tác giả Ateniese, Burns, Curtmola và Herring [1])
BLS Phương pháp tạo chữ ký điện tử đề xuất bởi nhóm tác giả Dan
Boneh, Ben Lynn, and Hovav Shacham [5]
TPA Third-party auditor
DO Data owner
SVD Singular Value Decomposition
MAC Message Authentication Code
HMAC Hash-based Message Authentication Code
PPMAC Privacy-preserving Message Authentication Code
PRF Pseudorandom function
6
Danh sách bảng
1 Bảng thuật ngữ tiếng Anh . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Bảng từ viết tắt tiếng Anh . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1 Tóm tắt về các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . 22
2.1 Cấu hình hệ thống . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2 Thời gian sinh ma trận giả khả nghịch (Đơn vị: giây) . . . . . . . . . 47
3.1 Các bước kiểm định bảo toàn tính riêng tư . . . . . . . . . . . . . . . 66
3.2 Bảng kích thước ma trận . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3 Cấu hình hệ thống . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.4 Thời gian thực hiện kiểm định (Đơn vị: giây) . . . . . . . . . . . . . . 80
3.5 So sánh chi phí của 2 phương pháp đề xuất . . . . . . . . . . . . . . . 95
3.6 Bảng so sánh các phương pháp . . . . . . . . . . . . . . . . . . . . . 96
A.1 Cấu hình hệ thống . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
A.2 Thời gian chạy pha 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
A.3 Thời gian chạy của pha 2 . . . . . . . . . . . . . . . . . . . . . . . . . 112
A.4 Thời gian chạy của pha 3 . . . . . . . . . . . . . . . . . . . . . . . . . 113
7
A.5 Bảng tóm tắt các bước chia sẻ khóa bí mật giữa hai người dùng trên
cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
A.6 Bảng tóm tắt các bước Alice chia sẻ M ·X cho Bob . . . . . . . . . . 121
8
Danh sách hình vẽ
1.1 Mô hình kiểm định . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1 Thời gian tạo ma trận giả khả nghịch . . . . . . . . . . . . . . . . . . 48
3.1 Pha 1 của quá trình kiểm định . . . . . . . . . . . . . . . . . . . . . . 82
3.2 Pha 2 của quá trình kiểm định . . . . . . . . . . . . . . . . . . . . . . 83
3.3 Pha 3 của quá trình kiểm định . . . . . . . . . . . . . . . . . . . . . . 84
A.1 Thời gian chạy pha 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
A.2 Thời gian chạy của pha 2 . . . . . . . . . . . . . . . . . . . . . . . . . 113
A.3 Thời gian chạy của pha 3 . . . . . . . . . . . . . . . . . . . . . . . . . 114
9
Chương 1
Giới thiệu
1.1 Đặt vấn đề
Việc sử dụng hệ thống lưu trữ ngoài đã trở nên phổ biến không chỉ cho các doanh
nghiệp mà còn cho các cá nhân. Đặc biệt cùng với sự phát triển của điện toán đám
mây, người dùng lưu trữ dữ liệu ở các nhà cung cấp dịch vụ ngày càng nhiều. Lợi thế
của điện toán đám mây và các hệ thống lưu trữ ngoài là việc lưu trữ dữ liệu không
còn bị giới hạn trong hệ thống máy tính của cá nhân/ tổ chức người dùng mà được
cung cấp bởi các nhà cung cấp dịch vụ chuyên nghiệp. Người dùng có thể sử dụng
các dịch vụ của nhà cung cấp một cách dễ dàng mà không cần quan tâm đến việc
cài đặt, cấu hình, bảo trì hệ thống, mở rộng tài nguyên,... Bên cạnh các lợi ích, người
dùng cần cân nhắc các khía cạnh về bảo mật và tính riêng tư. Người dùng không nên
tin cậy nhà cung cấp dịch vụ hoàn toàn mà nên cân nhắc việc bảo vệ dữ liệu của
mình [21, 22, 26], bao gồm
1. Người dùng (cá nhân hoặc công ty) sử dụng dịch vụ lưu trữ dữ liệu cần được
10
đảm bảo tính bí mật và tính toàn vẹn cho dữ liệu [21].
2. Người dùng cần chia sẻ dữ liệu cho một hay nhiều người dùng khác sao cho nhà
cung cấp dịch vụ không đọc được nội dung dữ liệu [22].
3. Người dùng cần được đảm bảo là nhà cung cấp dịch vụ không xóa hay làm mất
mát bất kỳ phần nào dữ liệu mà người dùng lưu trữ [26].
Trong các vấn đề trên, luận án quan tâm đến vấn đề (3). Giải pháp cho vấn đề này là
thực hiện kiểm tra xem dữ liệu có bị mất mát hay xóa hay không. Quá trình kiểm tra
này được gọi là kiểm định dữ liệu (data auditing). Theo nhóm tác giả Mehdi Sookhak
và cộng sự [24], khi thiết kế và thực hiện các giải pháp kiểm định dữ liệu cần cân
nhắc đến một số khía cạnh sau:
• Tính hiệu quả: kiểm định dữ liệu với độ phức tạp tính toán ít nhất có thể
• Kiểm định công khai: cho phép ủy quyền việc kiểm định cho một tổ chức thứ
ba đáng tin cậy, do đó giảm gánh nặng tính toán cho người dùng
• Tính thường xuyên: cho phép quá trình kiểm định có thể lặp lại thường xuyên
với các yêu cầu kiểm định khác nhau
• Khả năng phát hiện: có khả năng phát hiện ra nếu dữ liệu có mất mát hay bị
xóa
• Khả năng phục hồi: có khả năng phục hồi lại dữ liệu nếu xảy ra sự cố
• Tính động: có khả năng kiểm định dữ liệu trong khi người dùng thêm/ xóa/
sửa dữ liệu mà không cần phải tải về toàn bộ dữ liệu
11
Trong các khía cạnh trên, khía cạnh kiểm định công khai là một trong những khía
cạnh quan trọng, được nhiều nhóm nghiên cứu quan tâm. Trong kiểm định công khai,
việc kiểm định được người dùng ủy quyền cho một tổ chức thứ ba. Thông thường, để
kiểm định dữ liệu, tổ chức thứ ba cần biết nội dung cần kiểm định. Nếu tổ chức thứ
ba không đáng tin cậy hoàn toàn thì các giải pháp cho kiểm định công khai cần cân
nhắc về tính riêng tư dữ liệu: tổ chức thứ ba không nên biết nội dung dữ liệu cần
kiểm định.
Ngoài ra, đối với môi trường lưu trữ dữ liệu ngoài đặc thù hơn như điện toán đám
mây, các giải pháp cần xét đến đặc điểm của môi trường lưu trữ. Cụ thể, đối với môi
trường điện toán đám mây, dữ liệu thường được các nhà cung cấp dịch vụ nhân bản
thành các bản sao khác nhau để đề phòng khi có sự cố dữ liệu không bị mất mát.
Khi đó việc kiểm định dữ liệu cần áp dụng cho toàn bộ các bản sao trên đám mây.
Cuối cùng, đối với dữ liệu có tính chất thay đổi thường xuyên, việc kiểm định
toàn bộ dữ liệu mỗi lần cập nhật là không khả thi và tốn nhiều chi phí. Khi đó, người
dùng cần các giải pháp kiểm định cho việc cập nhật dữ liệu, bao gồm thêm, xóa, sửa
dữ liệu.
1.2 Các nghiên cứu liên quan
Năm 2007, Juels và Kaliski [12] định nghĩa giao thức kiểm định dữ liệu (các tác giả
gọi là giao thức "proof of retrievability"). Các tác giả xem dữ liệu gốc là một tập tin
gồm nhiều khối. Theo phương pháp này, dữ liệu gốc được chèn thêm các khối dữ liệu
giả (gọi là các "sentinel"), sau đó hoán vị để phân tán vị trí của các khối dữ liệu giả.
Khi đó, nếu như máy chủ xóa hay chỉnh sửa một phần đáng kể nội dung của tập tin
12
dữ liệu ban đầu, xác suất máy chủ cũng xóa đi các khối dữ liệu giả là cao. Vì vậy,
khi tổ chức kiểm định (có thể chính là chủ dữ liệu hoặc tổ chức thứ ba được thuê để
thực hiện kiểm định) truy vấn nhiều dữ liệu giả, máy chủ không thể đưa ra câu trả lời
đầy đủ, nhờ đó tổ chức kiểm định phát hiện được việc mất mát dữ liệu. Ưu điểm của
phương pháp là tính đơn giản và tổ chức kiểm định không cần biết nội dung dữ liệu
do giao thức kiểm định dựa trên dữ liệu giả. Bù lại, máy chủ phải tăng thêm chi phí
lưu trữ do việc chèn thêm các dữ liệu giả. Ngoài ra, phương pháp này không hỗ trợ
tốt việc thay đổi dữ liệu như xóa một khối, chèn một khối vào vị trí bất kỳ vì khi đó,
tổ chức kiểm định cần được cập nhật về sự thay đổi vị trí các khối và việc này làm
cho hệ thống trở nên phức tạp hơn. Bên cạnh đó, đối với trường hợp chỉ một phần
nhỏ dữ liệu bị lỗi, nhờ vào việc áp dụng cơ chế mã sửa sai (error-correcting code) [8]
như được đề cập trong bài báo, người dùng có thể phục hồi lại dữ liệu gốc.
Cũng trong năm 2007, nhóm tác giả Ateniese, Burns, Curtmola và Herring [1] đề
xuất hai phương pháp không cần phải chèn thêm dữ liệu giả: S-PDP (strong PDP)
và E-PDP (efficient PDP), trong đó PDP là viết tắt của "provable data possession".
Phương pháp đầu tiên (gọi là S-PDP) dựa trên RSA, hàm băm mật mã, phép toán
nhân và nghịch đảo trên một trường hữu hạn thích hợp. Dữ liệu được chia thành
các khối, sau đó ứng với mỗi khối sẽ được sinh một nhãn. Mỗi nhãn là một bản mã
RSA, trong đó bản rõ có chứa thông tin về nội dung của khối dữ liệu. Khi tổ chức
kiểm định gửi truy vấn, trong đó có bao gồm số lượng khối dữ liệu mà tổ chức kiểm
định muốn truy vấn, máy chủ dựa trên hàm sinh số ngẫu nhiên được cung cấp trước
để tính ra danh sách các chỉ số của các khối dữ liệu được truy vấn và dựa trên hàm
băm mật mã để tính hệ số (là các hằng số) sẽ được dùng cho từng khối dữ liệu khi
tổng hợp thông tin để trả về cho tổ chức kiểm định. Cuối cùng, máy chủ tổng hợp
13
các nhãn của các khối bằng cách tính tích của lũy thừa các nhãn theo các hằng số
được sinh ra trước đó. Do mỗi nhãn là một bản mã RSA và dựa vào tính chất đồng
cấu, kết quả tổng hợp cũng là một bản mã RSA. Máy chủ gửi nhãn tổng hợp cùng
với giá trị băm được tính từ nội dung của các khối dữ liệu về cho tổ chức kiểm định.
Tổ chức kiểm định sử dụng khóa riêng để giải mã nhãn tổng hợp thành bản rõ, sau
đó băm lại và so sánh với giá trị băm nhận được từ máy chủ. Nếu hai kết quả khớp
nhau, điều đó có nghĩa là dữ liệu không bị chỉnh sửa, thêm bớt. Ưu điểm của phương
pháp này là độ an toàn phụ thuộc vào độ an toàn của hệ mã RSA vốn đã được thừa
nhận. Khuyết điểm của phương pháp này là chi phí tính toán, vì thực hiện nhiều
phép nhân, lấy nghịch đảo và phép lũy thừa trong trường hữu hạn. Vì vậy, nhóm tác
giả mô tả một phương pháp khác tương tự, gọi là E-PDP hiệu quả hơn nhưng giảm
đi độ an toàn. Phương pháp thứ 2 này bỏ đi việc sử dụng hàm băm mật mã để tính
hệ số (là các hằng số) sẽ được dùng cho từng khối dữ liệu khi tổng hợp nhãn, nhờ
vậy giảm đi chi phí tính toán tính toán khi tổng hợp nhãn và khi kiểm định dữ liệu.
Nhưng như vậy đồng thời giảm đi tính an toàn so với phương pháp đầu tiên.
Cả hai phương pháp này có thể áp dụng để chủ dữ liệu tự kiểm định (gọi là kiểm
định riêng) hoặc thuê một tổ chức thứ ba thực hiện kiểm định (gọi là kiểm định công
khai). Tuy nhiên, dù có thể hỗ trợ tổ chức thứ ba thực hiện kiểm định thay cho chủ
dữ liệu, phương pháp này không đảm bảo tổ chức thứ ba không đọc được nội dung
dữ liệu. Bên cạnh đó, do các nhãn của các khối dữ liệu được tạo ra dựa vào vị trí của
khối, hai phương pháp này không hỗ trợ tốt cho việc cập nhật dữ liệu, vì vậy thích
hợp hơn cho dữ liệu tĩnh.
Một năm sau đó, nhóm tác giả Shacham và Waters[23] đưa ra hai phương pháp
kiểm định: một phương pháp kiểm định riêng và một phương pháp kiểm định công
14
khai. Cả hai phương pháp chia dữ liệu thành các khối, mỗi khối được chia thành các
phần (gọi là sector). Dựa trên các phần dữ liệu, chủ dữ liệu tạo các nhãn cho từng
khối bằng cách nhân giá trị dữ liệu từng phần với hệ số được sinh ngẫu nhiên, sau
cùng cộng với một giá trị ngẫu nhiên được sinh ra bằng cách dùng hàm ngẫu nhiên
với khóa bí mật và giá trị chỉ số của khối dữ liệu. Dữ liệu và tập nhãn của các khối
dữ liệu được gửi đến lưu trữ ở máy chủ. Ngoài ra, chủ dữ liệu tạo một nhãn cho toàn
bộ tập tin dữ liệu, trong đó có chứa thông tin khóa bí mật và các hệ số được sử dụng
để tạo các nhãn cho các khối dữ liệu. Chủ dữ liệu có thể xóa dữ liệu, chỉ giữ lại nhãn
này. Mỗi khi cần kiểm định dữ liệu, chủ dữ liệu sinh một tập các chỉ số ngẫu nhiên
và các hằng số ngẫu nhiên, sau đó gửi cho máy chủ. Máy chủ dựa vào giá trị của các
khối dữ liệu được yêu cầu kiểm định và các hằng số nhận được, tổng hợp dữ liệu theo
chiều dọc, theo nghĩa mỗi lần tính sẽ lấy một phần dữ liệu trong mỗi khối nhân với
hằng số tương ứng, sau đó cộng lại. Kết quả là s giá trị tổng hợp với s là số lượng
phần dữ liệu trong từng khối. Đồng thời, chủ dữ liệu tổng hợp các nhãn cũng bằng
cách nhân hằng số cho từng nhãn và cộng lại. Máy chủ gửi kết quả tính được về cho
chủ dữ liệu. Chủ dữ liệu dựa vào đó để kiểm định xem thông tin tổng hợp do máy
chủ gửi về và thông tin tự tổng hợp (do chủ dữ liệu có giữ khóa bí mật) có khớp nhau
hay không. Phương pháp này đơn giản, chủ yếu dựa trên phép nhân hằng số và phép
cộng, cuối cùng so sánh giá trị.
Trong phương pháp thứ hai, nhãn của từng khối dữ liệu được tạo ra bằng cách
tính tích của các lũy thừa của hằng số được chọn ngẫu nhiên với số mũ là giá trị của
các phần (sector) trong khối, sau đó nhân với giá trị được tạo ra dựa vào vị trí của
khối, cuối cùng dùng khóa riêng (chỉ chủ dữ liệu có) để lũy thừa kết quả tính được.
Tương tự, khi máy chủ tổng hợp nhãn của các khối dữ liệu được yêu cầu sẽ lũy thừa
15
các nhãn với khóa công khai, sau đó nhân lại. Đồng thời, máy chủ tổng hợp dữ liệu
theo khối bằng cách tính tích từng phần (sector) với khóa công khai và cộng dồn lại.
Máy chủ gửi nhãn tổng hợp và các giá trị tổng hợp của các khối đến cho tổ chức kiểm
định. Cuối cùng, khi tổ chức thứ ba kiểm định dữ liệu sẽ dựa vào dữ liệu tổng hợp và
nhãn nhận được, áp dụng ánh xạ song tuyến tính để kiểm tra thông tin trong nhãn
và trong dữ liệu tổng hợp có khớp với nhau hay không. Tổ chức thứ ba không cần
biết giá trị của khóa riêng của chủ dữ liệu, vì vậy có thể là bất kỳ ai.
Năm 2009, nhóm tác giả Qian Wang và các cộng sự [28] đề xuất một phương pháp
kiểm định dữ liệu có hỗ trợ việc cập nhật dữ liệu. Phương pháp này dựa trên phương
pháp tạo chữ ký BLS [5] và cấu trúc dữ liệu cây nhị phân Merkle Hash. Mỗi tập tin
hay thông điệp được chia thành các khối dữ liệu. Mỗi khối được tạo nhãn dựa vào
chữ ký BLS. Khi máy chủ gửi thông tin về cho tổ chức kiểm định, máy chủ tổng hợp
các khối dữ liệu được truy vấn bằng cách nhân từng khối với các hệ số ngẫu nhiên và
cộng dồn lại. Tương tự, máy chủ cũng tổng hợp các nhãn tương ứng bằng cách lũy
thừa từng nhãn và nhân lại với nhau. Tổ chức kiểm định sẽ dựa vào tính chất của
ánh xạ song tuyến tính và thông tin nhận được từ máy chủ để kiểm tra tính nguyên
vẹn của dữ liệu. Bên cạnh đó, máy chủ gửi thông tin chữ ký của nút gốc trong cây
Merkle Hash cho tổ chức kiểm định. Trong cây nhị phân Merkle Hash, các nút lá
chứa các giá trị băm của các khối dữ liệu và được lưu theo thứ tự từ trái qua phải, vì
vậy mỗi nút lá được xác định duy nhất dựa vào dãy các nút từ gốc tới nó. Tương tự
các phương pháp trước, với mỗi khối dữ liệu, chủ dữ liệu dùng phương pháp tạo chữ
ký BLS với khóa bí mật để tạo ra nhãn tương ứng. Khác với các phương pháp trước,
thông tin vị trí của khối không được lưu trực tiếp trong nhãn của các khối dữ liệu.
Thay vì vậy, thông tin này được lưu thông qua các ràng buộc vị trí của các nút lá
16
trong cây Merkle Hash. Nhờ vậy, việc thêm/ xóa/sửa dữ liệu dễ dàng hơn, và có thể
kiểm định việc máy chủ thêm/ xóa/ chỉnh sửa dữ liệu có đúng yêu cầu không. Khi
thực hiện kiểm định, máy chủ cần gửi về cho tổ chức kiểm định thông tin nhãn của
các khối dữ liệu được yêu cầu và thông tin về nút gốc và đường đi từ nút gốc đến nút
lá tương ứng với khối dữ liệu được yêu cầu. Tổ chức kiểm định thực hiện hai phép
kiểm tra: phép kiểm tra để kiểm định vị trí