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