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

ĐẠ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í