Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Kiểm định công khai đảm bảo tính riêng tư cho dữ liệu lưu trữ ngoài (tóm tắt)...

Tài liệu Kiểm định công khai đảm bảo tính riêng tư cho dữ liệu lưu trữ ngoài (tóm tắt)

.PDF
32
861
142

Mô tả:

ĐẠI HỌC QUỐC GIA TPHCM TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊ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 TÓM TẮT LUẬN ÁN TIẾN SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Tp. Hồ Chí Minh, năm 2016 Công trình được hoàn thành tại: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Người hướng dẫn khoa học: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (ghi rõ họ tên, chức danh khoa học, học vị) Phản Phản Phản Phản Phản biện biện biện biện biện 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . độc lập 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . độc lập 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Luận án sẽ được bảo vệ trước Hội đồng chấm luận án họp tại .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vào lúc · · · giờ · · · ngày · · · tháng · · · năm· · · Có thể tìm hiểu luận án tại thư viện: - Thư viện Khoa học Tổng hợp Tp.HCM - Thư viện Trường Đại học Khoa học Tự Nhiên Mục lục 1 Giới thiệu 1 2 Cơ sở lý thuyết 2.1 Ma trận giả nghịch đảo . . . . . . . . . . . . . . . . . . 2.2 Mã xác thực thông điệp đảm bảo tính riêng tư . . . . . 4 4 8 3 Kiểm định công khai đảm bảo tính riêng tư cho dữ lưu trữ ngoài 3.1 Phương pháp dựa vào ma trận giả nghịch đảo . . . . 3.1.1 Mô tả . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Phân tích . . . . . . . . . . . . . . . . . . . . 3.1.3 Thực nghiệm đo thời gian chạy thuật toán . . 3.2 Phương pháp dựa vào mã xác thực thông điệp . . . 3.2.1 Mô tả giao thức tổng quát . . . . . . . . . . . 3.2.2 Phân tích . . . . . . . . . . . . . . . . . . . . 3.2.3 Mô tả giao thức cụ thể . . . . . . . . . . . . . 3.3 So sánh . . . . . . . . . . . . . . . . . . . . . . . . . liệu . . . . . . . . . . . . . . . . . . 12 12 12 15 16 17 17 19 20 22 4 Kết luận 24 Danh mục tài liệu tham khảo 26 Danh mục công trình khoa học 28 Chương 1. Giới thiệu Việc sử dụng hệ thống lưu trữ ngoài hay lưu trữ trên đám mây điện toán đã trở nên phổ biến không chỉ cho các doanh nghiệp mà còn các cá nhân. 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. 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ư [12, 13, 16], trong đó bao gồm việc 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ữ [16]. Giải pháp cho vấn đề này là chủ dữ liệu thưc hiện kiểm tra xem dữ liệu có bị mất mát hay xóa hay không, hoặc thuê một tổ chức thứ ba thực hiện. Quá trình kiểm tra này được gọi là kiểm định dữ liệu (auditing). Các phương pháp kiểm định dữ liệu đã được đề xuất có thể phân chia thành 2 loại dựa vào đối tượng thực hiện kiểm định: chủ dữ liệu tự thực hiện kiểm định (gọi là kiểm định riêng) [8, 14], một tổ chức thứ ba do chủ dữ liệu thuê thực hiện kiểm định (gọi là kiểm định công khai) [1, 18, 17, 6]. Trường hợp chủ dữ liệu thuê một tổ chức thứ ba, thông thường chủ dữ liệu muốn đảm bảo tính riêng tư dữ liệu, không cho tổ chức thứ ba đọc được dữ liệu (gọi là đảm bảo tính riêng tư (privacy-preserving)). Hầu hết các phương pháp dựa trên các kỹ thuật chính sau: mã xác thực thông điệp, chèn dữ liệu giả [8], phương pháp mã hóa RSA và tính chất đồng cấu [1, 6], chữ ký BLS và ánh xạ song 1 tuyến tính [18, 14]. Một số phương pháp có hỗ trợ kiểm định các thao tác cập nhật dữ liệu (thêm, xóa, sửa) nhờ vào việc sử dụng các cấu trúc dữ liệu đặc biệt như cây Merkle Hash [19], danh sách xác thực nhảy cóc [5]. Tiêu chí thiết kế thuật toán của các phương pháp đã được đề xuất thường là chi phí dùng để kiểm định, chi phí phát sinh thêm do cần lưu thêm thông tin cần thiết hỗ trợ cho việc kiểm định (gọi là metadata), chi phí truyền tải từ máy chủ đến tổ chức kiểm định sao cho các chi phí này càng nhỏ càng tốt. Mục tiêu của luận án là đề xuất một hướng tiếp cận khác để giải bài toán kiểm định công khai đảm bảo tính riêng tư dữ liệu. Mô hình kiểm định dữ liệu công khai gồm 3 đối tượng: • Máy chủ (Server): Máy chủ cung cấp dịch vụ lưu trữ dữ liệu ngoài. Giả thiết rằng máy chủ không sử dụng hay tiết lộ dữ liệu người dùng nhưng có thể giấu giếm thông tin nếu xảy ra mất mát dữ liệu hoặc chủ động xóa một phần dữ liệu ít truy xuất đến của người dùng. • Chủ dữ liệu (Data Owner, viết tắt là DO): Người dùng dịch vụ lưu trữ dữ liệu ngoài. • Tổ chức kiểm định thứ ba (Third-party auditor, viết tắt là TPA): Một tổ chức thứ ba được người dùng thuê để kiểm định dữ liệu trên máy chủ nhưng lại không đọc được nội dung của dữ liệu. Chúng tôi xây dựng giải pháp cho bài toán kiểm định công khai từ hai hướng tiếp cận khác nhau: dựa trên ma trận giả nghịch đảo [11], dựa trên mã xác thực thông điệp mới (gọi là mã xác thực thông điệp đảm bảo tính riêng tư). Phương pháp dựa trên ma trận giả nghịch đảo có chi phí tính toán khi thực hiện kiểm định thấp hơn phương pháp dựa vào RSA [1] và ánh xạ song tuyến tính [16]. Phương pháp dựa trên mã xác thực thông điệp mới có chi phí tính toán cao hơn phương pháp dùng mã xác thực thông thường, nhưng lại đảm bảo được tính riêng tư 2 của dữ liệu, trong khi phương pháp dùng mã xác thực thông thường thì không có [17]. Bố cục của luận án gồm các phần sau 1. Mục tiêu, nội dung nghiên cứu và bố cục của luận án được giới thiệu trong Chương 1. 2. Cơ sở lý thuyết, bao gồm ma trận giả nghịch đảo và mã xác thực thông điệp được trình bày trong Chương 2. 3. Ứng dụng kiểm định dữ liệu đảm bảo tính riêng tư theo 2 phương pháp: phương pháp dựa vào ma trận giả nghịch đảo, phương pháp dựa vào mã xác thực thông điệp đảm bảo tính riêng tư và so sánh giữa 2 phương pháp được mô tả trong Chương 3. 4. Phần tổng kết các nội dung đã làm trong luận án và hướng phát triển được trình bày trong Chương 4. 3 Chương 2. 2.1 Cơ sở lý thuyết Ma trận giả nghịch đảo Ma trận giả nghịch đảo là một khái niệm tổng quát hóa của ma trận nghịch đảo được Penrose đưa ra vào năm 1955 [11]. Định lý 1. Cho trước ma trận số thực (hay số phức) A. Bốn phương trình có nghiệm duy nhất. [11]. AXA = A (2.1.1) XAX = X (2.1.2) (AX)T = AX (2.1.3) (XA)T = XA (2.1.4) 1 Nghiệm duy nhất của 4 phương trình (2.1.1), (2.1.2), (2.1.3), (2.1.4) được gọi là ma trận giả nghịch đảo (pseudoinverse, Moore-Penrose inverse) của A., ký hiệu là A† . Trường hợp A là ma trận vuông khả nghịch, A† = A−1 [11]. 1 Ma trận giả nghịch đảo được định nghĩa tổng quát cho số phức. Tuy nhiên, để đơn giản, chúng tôi chỉ trình bày định nghĩa cho số thực. Ký hiệu T để chỉ phép toán chuyển vị ma trận. Đối với số phức, phép chuyển vị AT đổi thành phép chuyển vị liên hợp (conjugate transpose) A∗ 4 Dựa trên tính chất của ma trận giả nghịch đảo trên trường số thực [3, 11], chúng tôi khảo sát lại tính chất của chúng trên trường hữu hạn Zp với p nguyên tố như phát biểu trong mệnh đề sau. Mệnh đề 1. Xét ma trận A có kích thước m × n với hệ số trên Zp . Khi đó 1. Nếu ma trận AT A khả nghịch thì A† = (AT A)−1 AT (2.1.5) và m ≥ n. 2. Nếu ma trận AAT khả nghịch thì A† = AT (AAT )−1 (2.1.6) và m ≤ n. Dựa vào Mệnh đề 1, ta có thể xây dựng ma trận giả nghịch đảo bằng cách xây dựng ma trận A để AAT khả nghịch. Để tạo ma trận A sao cho AAT khả nghịch, chúng tôi đề nghị 2 hướng tiếp cận: • Cách 1: tạo ma trận A ngẫu nhiên và kiểm tra tính khả nghịch của AAT . Nếu AAT khả nghịch thì dừng lại, nếu không thì lặp lại. • Cách 2: tạo ma trận A dựa vào ma trận khả nghịch và ma trận tự trực giao theo dòng [9]. Định nghĩa 1. [9] Một ma trận không vuông C được gọi là tự trực giao theo dòng (row-self-orthogonal) nếu CC T = O trong đó O là ma trận zero có kích thước phù hợp. Tính chất sau sẽ giúp việc xây dựng ma trận tự trực giao theo dòng dễ dàng. 5 Mệnh đề 2. Cho ma trận Q kích thước k × m trong trường   có đặc số 2 p sao cho tồn tại α mà α = −1. Ma trận P = Q αQ là ma trận tự trực giao theo dòng, kích thước k × 2m. [9] Dựa vào ma trận tự trực giao theo dòng và ma trận khả nghịch, chúng tôi xây dựng ma trận giả khả nghịch theo phương pháp như sau Mệnh đề 3. Cho ma trận khả nghịch Z ∈ Zpm×m , ma trận tự trực giao m×(n−m) theo dòng V ∈ Zp (m < n). Ma trận tạo bằng cách nối  A được  ma trận Z với ma trận V theo cột, A = Z V , thì tích của ma trận A và chuyển vị, AAT , sẽ khả nghịch. Chứng minh.  A= Z V  T ⇔A = ZT VT ! ⇒ AAT = ZZ T + V V T = ZZ T + O (vì V tự trực giao theo dòng) = ZZ T ⇒ det(AAT ) = det(ZZ T ) = det(Z)det(Z T ) 6= 0 (vì Z khả nghịch) Suy ra AAT khả nghịch. Từ đó, chúng tôi xây dựng 2 thuật toán sinh ma trận giả nghịch đảo trên trường Zp , gồm 1. Thuật toán sinh vector cột và giả nghịch đảo tương ứng (Thuật toán 1) dựa theo cách 1 đã nêu ở trên. 2. Thuật toán sinh ma trận kích thước m × n(m < n) và giả nghịch đảo tương ứng (Thuật toán 2) dựa theo cách 2 đã nêu ở trên. 6 Thuật toán 1 SimplePseudoMatrix(n, p)- Thuật toán sinh vector giả khả nghịch Đầu vào: n, p {gcd(n, p) = 1 và p nguyên tố} Đầu ra: Ma trận A kích thước 1 × n trong trường Zp sao cho tồn tại −1 ma trận giả nghịch đảo A† = AT · A · AT 1: for i = 1 → (n − 1) do 2: A[1, i] = random(p) {random(p) là hàm sinh số ngẫu nhiên thuộc {0, ..., p − 1}} 3: end for Pn−1 4: Chọn q trong {0, 1, ..., p−1} sao cho ( i=1 A[1, i]2 +q 2 ) (mod p) 6= 0 5: A[1, n] = q 6: Trả về A Thuật toán 2 PseudoInverseMatrix(m, n, p)- Thuật toán sinh ma trận chữ nhật giả khả nghịch Đầu vào: m, n, p : m < n Đầu ra: Ma trận A kích thước m × n trong trường Zp sao cho tồn tại −1 ma trận giả nghịch đảo A† = AT · A · AT . 0 1: Sinh ngẫu nhiên ma trận khả nghịch A kích thước m × m. 2: Sinh ngẫu nhiên ma trận tự trực giao dòng A” kích thước m × (n − m).   3: Tạo ma trận A = A0 A” bằng cách ghép 2 ma trận A0 và A00 theo cột. 4: Trả về A Để đánh giá tốc độ thực thi, chúng tôi cài đặt chương trình thực nghiệm đánh giá thời gian sinh ma trận giả khả nghịch bằng cách chạy Thuật toán 2 - PseudoInverseMatrix(m, n, p) và đo thời gian chạy của thuật toán với các giá trị tham số: • m, n được sinh ngẫu nhiên. Kết quả 2 lần sinh ngẫu nhiên m, n 7 là: m = 20, n = 26 và m = 16, n = 22 • Kích thước (số bit) của p: 8 bit, 16 bit Trong mỗi trường hợp, chúng tôi chạy chương trình 30 lần và tính thời gian chạy trung bình. Chương trình thực nghiệm được thực hiện trên máy ảo Virtual Box có cài đặt phần mềm SageMath và cấu hình như sau: Bảng 2.1: Cấu hình hệ thống Bộ nhớ 512 MB Hệ điều hành Fedora (32 bit), ổ cứng cấp phát động, kích thước thật sự 6.6 GB. Bộ vi xử lý của máy chủ (host machine): Intel Core i5-2430M CPU @ 2.4 GHz Kết quả thực nghiệm như sau: Bảng 2.2: Thời gian sinh ma trận giả khả nghịch (Đơn vị: giây) Kích thước ma trận m×n Chiều dài (số bit) của p Trung bình thời gian sinh ma trận (số giây) Độ lệch chuẩn 20 × 26 20 × 26 16 × 22 16 × 22 8 16 8 16 0.0063 0.0089 0.0044 0.0088 0.002 0.0024 0.0019 0.0032 2.2 Mã xác thực thông điệp đảm bảo tính riêng tư Cho trước số nguyên dương n, z, z 0 và khóa chia sẻ k, ký hiệu 8 • hk : {0, 1}∗ → {0, 1}n là một hàm băm mật mã, 0 • Hi : {0, 1}z → {0, 1}z là các hàm băm một chiều, i ∈ {0, 1, 2} • Qk : {0, 1}∗ → {0, 1}n+1 là hàm sinh số nguyên tố n + 1 bit sao cho Qk thỏa 2 điều kiện Qk (s) 6= Qk (s0 ), ∀s 6= s0 , và Qk (s) 6= Qk0 (s), ∀k 6= k 0 . (Chú ý rằng không khó để sinh một số nguyên tố (xem [4])) và không mất tính tổng quát, giả sử m = m0 km1 km2 ∈ {0, 1}∗ là thông điệp, với |m0 | = |m1 | = |m2 | = |m|/3 = z và k là phép ghép chuỗi bit. Định nghĩa 2. Mã xác thực thông điệp bảo toàn tính riêng tư (Privacy-preserving Message Authentication Code - PPMAC) Cho m = m0 km1 km2 ∈ {0, 1}∗ là một thông điệp. Đặt M = H0 (m0 ) ⊕ H1 (m1 ) ⊕ H2 (m2 ), fi = hk (M ⊕ Hi (mi )), i = 0, 1, 2, qi = Qk (ikfi ), i = 0, 1, 2. Mã chứng thực thông điệp bảo toàn tính riêng tư (PPMAC) của thông điệp m được định nghĩa là nghiệm của hệ phương trình đồng dư: X ≡ f0 (mod q0 ) X ≡ f1 (mod q1 ) X ≡ f2 (mod q2 ) Mã thông điệp trên được định-nghĩa-tốt vì X là nghiệm duy nhất của hệ phương trình đồng dư. Từ Định nghĩa 2, chúng tôi thiết kế thuật toán tạo mã xác thực thông điệp đảm bảo tính riêng tư và thuật toán kiểm tra tính mã xác thực thông điệp như sau. 9 Thuật toán 3 CreateMAC(·)-Tạo mã xác thực Tính M = H0 (m0 ) ⊕ H1 (m1 ) ⊕ H2 (m2 ). Tính fi = hk (M ⊕ Hi (mi )), i = 0, 1, 2. Tạo các số nguyên tố qi = Qk (ikfi ), i = 0, 1, 2. Giải hệ X ≡ f0 (mod q0 ); X ≡ f1 (mod q1 ); X ≡ f2 (mod q2 ) (5) Trả về X (1) (2) (3) (4) Thuật toán 4 Verify(·)-Kiểm tra mã xác thực Đầu vào: H0 (m0 ) ⊕ H1 (m1 ), H0 (m0 ) ⊕ H2 (m2 ) và mã xác thực X (1) Tính f1 = hk (H0 (m0 ) ⊕ H2 (m2 )), và f2 = hk (H0 (m0 ) ⊕ H1 (m1 )) (2) Tính qi = Qi (ikfi ), i = 1, 2 (3) Kiểm tra xem X (mod qi ) = fi , ∀i = 1, 2. Nếu phải, trả về 1. Nếu không, trả về 0. Độ an toàn của mã xác thực thông điệp đảm bảo tính riêng tư được mô tả qua Mệnh đề 4 như sau. Định lý 2. [2, 4] Số lượng số nguyên tố không vượt quá x tiệm cận với x/lnx. Hệ quả 1. Số nguyên tố (n + 1) bit tiệm cận với 2n (n − 1)/(n(n + 1)) Mệnh đề 4. Không biết trước khóa chia sẻ và {hk } là hàm sinh số ngẫu nhiên (pseudorandom functions (PRF)) an toàn, kẻ tấn công không giả mạo được mã xác thực đảm bảo tính riêng tư X với xác suất đáng kể trong thời gian đa thức. Mệnh đề 5. Hệ phương trình xi ⊕ xj = ai (i = 1, . . . , m − 1; j = i + 1, . . . , m; m ≥ 2 và xi ∈ Zn2 , ∀i) có 2n nghiệm. 10 Mệnh đề 6. Dựa trên H0 (m0 )⊕H1 (m1 ), H0 (m0 )⊕H2 (m2 ), người thực hiện xác thực không tìm được nội dung của H0 (m0 ), H1 (m1 ), H2 (m2 ) bằng tấn công đại số trong thời gian đa thức. Chứng minh. Dựa trên H0 (m0 ) ⊕ H1 (m1 ), H0 (m0 ) ⊕ H2 (m2 ), người thực hiện xác thực có thể thiết lập hệ phương trình như trong Mệnh đề 5. Theo Mệnh đề 5, nếu Hi (mi ) ∈ Zn2 , ∀i = 0, 1, 2 thì hệ phương trình có 2n nghiệm. Vì vậy, người thực hiện xác thực không tìm được nội dung của H0 (m0 ), H1 (m1 ), H2 (m2 ) bằng tấn công đại số trong thời gian đa thức. Một số nhận xét về chi phí tính toán và lưu trữ: • Kích thước mã xác thực đảm bảo tính riêng tư tương đương với kích thước mã xác thực dùng hàm băm thông thường. • Kích thước dữ liệu cần gửi đi có thể nhỏ hơn trường hợp mã xác thực dùng hàm băm thông thường nếu chọn tham số phù hợp. • Chi phí tính toán cao hơn so với trường hợp mã xác thực dùng hàm băm thông thường. Tóm tắt Trong chương này chúng tôi giới thiệu khái niệm và các tính chất của ma trận giả nghịch đảo được Penrose đưa ra vào năm 1955 [11] và mã xác thực thông điệp đảm bảo tính riêng tư. Chúng tôi sẽ dựa vào 2 khái niệm này để xây dựng mô hình kiểm định dữ liệu. Trong chương tiếp theo, chúng tôi áp dụng ma trận giả nghịch đảo và mã xác thực thông điệp đảm bảo tính riêng tư vào ứng dụng kiểm định dữ liệu. 11 Chương 3. Kiểm định công khai đảm bảo tính riêng tư cho dữ liệu lưu trữ ngoài 3.1 Phương pháp dựa vào ma trận giả nghịch đảo 3.1.1 Mô tả Trong mô hình này chúng tôi giả sử đã có sẵn các thành phần như sau: • Hàm f sinh một ma trận khả nghịch. Đầu vào của hàm này là 2 giá trị có vai trò như tham số khởi tạo (seed). • Một khóa chia sẻ giữa chủ dữ liệu và tổ chức kiểm định. Khóa này là 1 ma trận giả khả nghịch X trên trường hữu hạn Zp (p là số nguyên tố). • Dữ liệu gồm nhiều mẫu tin. Mỗi mẫu tin có thể xem là 1 ma trận. • Mỗi lần tổ chức kiểm định ít nhất 2 mẫu tin. 12 Bảng 3.1: Các bước kiểm định bảo toàn tính riêng tư Chủ dữ liệu (DO) Máy chủ (Server) Khóa chia sẻ X Tổ chức kiểm định (TPA) Khóa chia sẻ X DO gửi dữ liệu đến máy chủ để lưu trữ (1) (2) Với mỗi mẫu tin Mi với chỉ số i ∈ I, sinh một ma trận khả nghịch Qi = f (X, i). Tính Ti = Qi · Mi · X · X † . Gửi (i, Mi , Ti ) đến máy chủ. Lưu trữ {(i, Mi , Ti )} Tổ chức thứ ba kiểm định dữ liệu (3) Lưu trữ {(i, Mi , Ti )} (4) Sinh ngẫu nhiên các số nguyên cij . Tính A =  Σ`j=1 cij R · Qij · Mij  và B = Σ`j=1 cij Tij , và gửi đến tổ chức kiểm định. (5) Sinh ngẫu nhiên danh sách các chỉ số {ij }, j = 1 . . . `, ` ≥ 2. Sinh một ma trận khả nghịch R và Qij = f (X, ij ), j = 1 . . . `. Gửi {(ij , R · Qij )} đến máy chủ. Trả về 1 nếu A · X = R · B · X, trả về 0 nếu ngược lại (1 nghĩa là dữ liệu toàn vẹn và 0 nghĩa là dữ liệu đã bị thay đổi). 13 Mệnh đề 7. (Tính đúng đắn) Gọi i1 , . . . , i` là chỉ số các mẫu tin tổ chức kiểm định cần truy vấn và giả sử rằng các mẫu tin tương ứng Mij (j = 1, . . . , `) vẫn còn nguyên vẹn. X là khóa bí mật của tổ chức kiểm định. Thông tin máy chủ gửi về được  sinh ra từ các mẫu tin đó  ` gồm A = Σj=1 cij R · Qij · Mij và B = Σ`j=1 cij Tij . Tổ chức kiểm định sẽ trả kết quả là 1, nghĩa là xác nhận dữ liệu còn nguyên vẹn.   Chứng minh. Ta có: A·X = Σ`j=1 cij R · Qij · Mij ·X = R·Σ`j=1 cij Qij · Mij ·    X · X † · X = R · Σ`j=1 cij Qij · Mij · X · X † · X = R · Σ`j=1 cij Tij · X = R·B·X Vì vậy, tổ chức kiểm định trả kết quả về 1. Kích thước các ma trận trong phương pháp trên được trình bày trong bảng sau Bảng 3.2: Bảng kích thước ma trận Ma trận Kích thước Qi k×k Mi k×m X m×k Ti k×m R k×k A k×m B k×m Ghi chú k k, ngầm hiểu X sẽ được tạo ra dựa vào Mệnh đề 1 sao cho X T X khả nghịch. Suy ra X độc lập tuyến tính cột. 14 3.1.2 Phân tích Mệnh đề 8. (Chi phí lưu trữ) Gọi N là số lượng dữ liệu của cơ sở dữ liệu và (k × m) là kích thước của một mẫu tin. • Chi phí để lưu trữ trên máy chủ là O(N km). • Chi phí để lưu trữ ở phía chủ dữ liệu và tổ chức kiểm định đều là km. Mệnh đề 9. (Chi phí trên đường truyền) Gọi ` là số lượng mẫu tin được yêu cầu kiểm định, k ×m là kích thước mẫu tin, |Int| là kích thước của 1 số nguyên. 1. Máy chủ gửi về cho tổ chức kiểm định dữ liệu với kích thước 2 × k × m. 2. Tổ chức kiểm định gửi về cho máy chủ yêu cầu với kích thước `(|Int| + k × k). Mệnh đề 10. (Về chi phí tính toán) Gọi N là số lượng mẫu tin của cơ sở dữ liệu, ` là số lượng dữ liệu được yêu cầu kiểm định. 1. Chủ dữ liệu thực hiện 2N phép băm, 4N phép nhân ma trận để gửi N dữ liệu lên máy chủ 2. Máy chủ thực hiện 2` phép nhân ma trận để trả lời truy vấn kiểm định ` mẫu tin. 3. Tổ chức kiểm định thực hiện 2` + 1 phép băm, ` + 4 phép nhân ma trận để kiểm định ` mẫu tin, 1 phép so sánh ma trận. Tiếp đến, chúng tôi phân tích độ an toàn của mô hình, trong đó chúng tôi chỉ giới hạn xét một số mô hình tấn công cụ thể như sau: • Máy chủ dựa vào các giá trị nhãn Ti và các mẫu tin Mi để tìm giá trị khóa X. Phương pháp máy chủ tìm khóa X là phương pháp đại số: phân tích Ti = Qi · Mi · X · X † , biết trước Mi để tìm X. 15 • Tổ chức kiểm định dựa vào A, B để tìm giá trị mẫu tin Mij . Phương pháp tổ chức kiểm định tìm các mẫu tin Mij là phương  pháp đại số, giải hệ phương trình A = Σ`j=1 cij R · Qij · Mij và  B = Σ`j=1 cij Tij = Σ`j=1 cij Qij · Mij · X · X † , biết trước R · Qij và X. Mệnh đề 11. (An toàn của khóa bí mật) Gọi Mi là mẫu tin thứ i và Ti = Qi · Mi · X · X † là giá trị nhãn tương ứng. Dựa vào Mi , Ti , máy chủ không tìm được giá trị khóa X dựa vào tấn công đại số trong thời gian đa thức.  Mệnh đề 12. (Bảo toàn tính riêng tư) Gọi A = Σ`j=1 cij R · Qij · Mij  và B = Σ`j=1 cij Tij = Σ`j=1 cij Qij · Mij · X · X † là dữ liệu máy chủ gửi cho tổ chức kiểm định, trong đó R, {Qij } do tổ chức kiểm định tạo ra, X là khóa bí mật. Tổ chức kiểm định không tìm được nội dung của các mẫu tin {Mij } dựa vào tấn công đại số trong thời gian đa thức. Giả sử năng lực tính toán của máy tính là 280 và chúng tôi chỉ xét khía cạnh lựa chọn tham số như thế nào để đảm bảo tính riêng tư của dữ liệu, chống lại tấn công vét cạn. Kết quả đánh giá là các hệ số cần được chọn sao cho (` − 2) × k × m × |p| > 80 (3.1.1) trong đó |p| chỉ số bit của p. 3.1.3 Thực nghiệm đo thời gian chạy thuật toán Chúng tôi cài đặt chương trình thực nghiệm đo thời gian máy chủ tạo minh chứng và tổ chức thứ 3 kiểm định dữ liệu dựa vào minh chứng như mô tả trong giao thức ở Bảng 3.1, sau đó so sánh với phương pháp dựa trên RSA [1] và phương pháp dựa trên ánh xạ song tuyến tính [16]. Số nguyên tố p được sinh ngẫu nhiên là p = 137. Số lượng mẫu tin được yêu cầu để kiểm định là 460. Với mỗi trường hợp, chúng tôi chạy 50 lần và tính thời gian chạy trung bình. 16 Bảng 3.3: Thời gian thực hiện kiểm định (Đơn vị: giây) Chiều dài mẫu tin (số bit) Phương pháp đề nghị Phương pháp dựa vào RSA [1] Phương pháp dựa vào ánh xạ song tuyến tính [16] 960 Tạo minh chứng: 0.01178 Kiểm tra minh chứng: 0.00012 Tạo minh chứng: 0.0132 Kiểm tra minh chứng: 0.00017 Tạo minh chứng: 2.811 Kiểm tra minh chứng: 2.111 Tạo minh chứng: 3.722 Kiểm tra minh chứng: 2.371 Tạo minh chứng: 0.1481 Kiểm tra minh chứng: 0.1712 Tạo minh chứng: 0.1839 Kiểm tra minh chứng: 0.2629 1200 Theo như bảng kết quả, phương pháp của chúng tôi có chi phí tính toán thấp nhất, kế đến là phương pháp dùng ánh xạ song tuyến tính [16], và sau cùng là phương pháp dùng RSA [1]. 3.2 Phương pháp dựa vào mã xác thực thông điệp Trước tiên, chúng tôi trình bày giao thức ở mức tổng quát. Sau đó, chúng tôi sẽ mô tả thuật toán cụ thể. 3.2.1 Mô tả giao thức tổng quát Quy ước: • Chủ dữ liệu (Data owner, viét tắt là DO) dùng một khóa bí mật x. Khóa này sẽ được chia sẻ với tổ chức kiểm định. 17
- Xem thêm -

Tài liệu liên quan