Chuyên ngành: Bo đm toán hc cho máy tính và h thng tính toán.
Mã s : 62 46 35 01
TÓM TT LUN ÁN TIN S TOÁN HC

Hà Ni - 2011
Chương 1
GIỚI THIỆU
1.1. Tổng quan về khai phá dữ liệu có đảm bảo tính riêng tư
Hiện nay, khai phá dữ liệu (KPDL) đóng vai trò quan trọng trong nhiều lĩnh
vực, nó cung cấp cho chúng ta các công cụ hiệu quả để khai phá ra các tri thức
hữu dụng từ các cơ sở dữ liệu. Tuy nhiên, tiến trình khai phá dữ liệu có thể dẫn
đến việc vi phạm các thông tin riêng tư và lĩnh vực khai phá dữ liệu có đảm bảo
tính riêmg tư (PPDM) đã ra đời [Verykios et al., 2004]. Các nghiên cứu trong lĩnh
vực này cho phép khai phá dữ liệu trong khi bảo vệ các thông tin riêng tư ở cấp
độ cá nhân hoặc cấp độ tổ chức.
Về cơ bản, có ba hướng chính trong lĩnh vực PPDM [Charu and Yu, 2008].
Hướng thứ nhất là công bố dữ liệu có đảm bảo tính riêng tư, các nghiên cứu trong
hướng này cho phép một tổ chức (thành viên-party) công bố tập dữ liệu cho các

thức này tốt hơn các giao thức trước đây là chúng có thể đảm bảo sự riêng
tư đầy đủ cho các thành viên tham gia. Thuộc tính này cho phép các giao
thức không cần bất kỳ thành viên tin cậy nào, cũng như không có sự thông
đồng của bất kỳ nhóm thành viên nào có thể làm lộ thông tin riêng tư của
mỗi thành viên.
3. Phát triển hai giao thức mới cho thuật toán phân cụm EM có đảm bảo tính
riêng tư trong dữ liệu phân tán ngang. Khác với giao thức trước đây yêu cầu
ít nhất ba thành viên tham gia và không chống được sự thông đồng. Các giao
thức đã đề xuất cho phép số thành viên tham gia có thể là hai hoặc nhiều
hơn, hơn thế nữa nó chống lại được sự thông đồng lên đến n-2 thành viên.
4. Đề xuất một kỹ thuật biến đổi tuyến tính để thiết kế các giao thức đảm bảo
tính riêng tư cho việc phát hiện các phần tử ngoại lai dựa trên thống kê cho
cả hai tình huống dữ liệu phân tán ngang và phân tán dọc.
Các giao thức được đánh giá dựa trên các tiêu chuẩn phổ biến như: tính riêng tư,
tính đúng đắn, tính hiệu quả và khả năng mở rộng. Mặc dù mỗi vấn đề trong luận
án này được phát biểu một cách độc lập, nhưng chúng cũng có thể được phát biểu
trong một khuôn khổ chung khi tập dữ liệu được phân mảnh theo một cách nào đó
trên một số thành viên hoặc một số lớn người dùng, vấn đề là tìm ra các giải pháp
để đạt được tri thức trên tập dữ liệu liên kết từ các nguồn phân tán này trong khi
đảm bảo tính riêng tư cho mỗi thành viên hoặc người dùn g.
1.3. Tổ chức luận án
Luận án bao gồm sáu chương, 109 trang A4. Chương 1 giới thiệu tổng quan về
PPDM và các vấn đề liên quan. Chương 2 trình bày các khái niệm và công cụ cơ
bản về tính toán bảo mật nhiều thành viên. Chương 3 đề xuất các giao thức cho
việc KPDL dựa trên tần suất có đảm bảo tính riêng tư trong 2PFD. Chương 4 đề
xuất các giao thức để nâng cao tính riêng tư trong việc phát hiện tập phổ biến.
Chương 5 phát triển các giao thức phân cụm dữ liệu có đảm bảo tính riêng tư.
Chương 6 đề xuất các giao thức phát hiện các phần tử ngoại lai có đảm bảo tính
riêng tư. Cuối cùng là phần kết luận của luận án.
2

n
| < ǫ(n)
Trong trường hợp như vậy ta viết X
c
≡ Y , ở đây
c
≡ là ký hiệu không thể phân biệt.
Hàm tính toán bảo mật nhiều thành viên: Trong hệ thống phân tán có n
thành viên (party). Một vấn đề tính toán nhiều thành viên (n-party) bảo mật có
thể phát biểu như là việc tính hàm sau:
f(x
1
, x
2
, , x
n
) → (f
1
(x
1
, x
2
, , x
n
), , f
n
(x
1
, x
2

x)) bao gồm x
i
, các thông điệp mà nó nhận được và các giá trị ngẫu
3
nhiên được tạo ra trong khi tính toán. Với mỗi I ⊂ [1, n], ký hiệu I = {i
1
, , i
t
},
f
I
(
x)=(y
i
1
, , y
i
t
) và view
π
I
(x) = (I, view
π
i
1
(x), , view
π
i
t
(x)). Gọi OUT PUT (x) là

mật cho nhiều thành viên bằng một cách nào đó mà không có thành viên nào biết
giá trị mật đó, nhưng nó dễ dàng tính được giá trị mật đó bằng việc kết hợp các giá
trị chia sẻ cho các thành viên. Ví dụ, sơ đồ chia sẻ mật của Shamir [Shamir, 1979]
hoặc giao thức chia sẻ giá trị trung bình được trình bày trong chương 5.
Tính tổng bảo mật (SSC - Secure sum computation): Vấn đề SSC bao gồm
n thành viên tham gia giao thức P
1
, , P
n
, mỗi thành viên thành viên P
i
có input
x
i
. Mục đích của giao thức SSC là để mỗi thành viên đạt được

x
i
với không bộc
lộ thông tin về mỗi x
i
. Nói cách khác một giao thức SSC là để tính hàm sau:
(x
1
, , x
n
) → x
1
+ + x
n

(C
x
2
)
−1
, sau đó tính f từ f
m
.
Chú ý rằng, khi m lớ n việc giải mã sẽ không hiệu quả. Tuy nhiên, trong các
giao thức của luận án này, chúng ta chỉ cần kiểm tra có hay không m có nhận một
giá trị cho trước không, ví dụ m = 0 hoặc m = c, ở đây c là hằng số nhỏ. Bởi vậy,
nó sẽ tương đương với việc kiểm tra có hay không:
C
1
C
−k
s
2
≡ 1 mod p hoặc C
1
C
−k
s
2
≡ f
c
mod p
Sơ đồ mã hóa ElGamal cải biên có thuộc tính không thể phân biệt dưới giả thiết
quyết định của Diffie-Hellman (DDH) [Boneh, 1998]. Sơ đồ này cũng có hai thuộc
tính đồng cấu cộng và đồng cấu nhân mà chúng ta sẽ vận dụng nó trong các chương

mà không biết được bất kỳ thông tin gì về đa thức P , và Alice không học đượ c bất
kỳ thông tin gì về x. Nói cách khác, một giao thức OPE là để thực hiện tính hàm
sau đây:
(P (y), x) → (∅, P(x) )
Chia sẻ tích vô hướng bảo mật (SSP - Secure scalar product): Giả thiết
rằng hai véc tơ A = (a
1
, , a
n
) và B = (b
1
, , b
n
) được sở hữu bằng hai thành viên
tương ứng Alice và Bob. Một giao thức chia sẻ tích vô hướng bảo mật nhằm cho
phép Alice đạt được r
1
và Bob đạt được r
2
, ở đây r
1
và r
2
là hai số nguyên, nằm
trong khoảng [0, M − 1], sao cho r
1
+ r
2
mod M = A · B (ở đây A · B ∈ [0, M]).
Nói cách khác, một giao thức SSP là để thực hiện tính hàm sau:

+ x
2
). Nói cách khác, một giao thức cho việc tính toán
ln (x) là để tính hàm sau:
(x
1
, x
2
) → (y
1
, y
2
)|y
1
+ y
2
= ln (x
1
+ x
2
)
5
Chương 3
KHAI PHÁ DỮ LIỆU DỰA TRÊN TẦN SUẤT CÓ ĐẢM BẢO TÍNH
RIÊNG TƯ TRONG TÌNH HUỐNG 2PFD
3.1. Giới thiệu
Trong 2PFD, tập dữ liệu gồm n bản ghi được phân tán trên 2n người dùng,
trong đó mỗi bản ghi được sở hữu bởi hai người dùng khác nhau, một người dùng
biết một số giá trị thuộc tính trong khi người dùng còn lại biết các thuộc tính còn
lại của bản ghi. Giả thiết rằng các thuộc tính của mỗi người dùng là nhạy cảm và


u
i
v
i
trong
khi thông tin về mỗi u
i
và v
i
là không bị bộc lộ. Nói cách khác, chúng ta cần một
giao thức tính toán đảm bảo tính riêng tư cho hàm sau:
(u
1
, v
1
, , u
n
, v
n
) →

u
i
v
i
Ký hiệu này ngụ ý rằng mỗi cặp người dùng cung cấp các input cho giao thức và
Miner chỉ nhận output f mà không biết bất kỳ thông tin gì khác.
6
3.2.2. Định nghĩa về việc đảm bảo tính riêng tư

có hai khóa mật x
i
, y
i
chọn ngẫu nhiên trong [1,q-1], và các
khóa công khai tương ứng X
i
= g
x
i
, Y
i
= g
y
i
. Mỗi người dùng V
i
có các khóa mật
p
i
, q
i
và các khóa công khai P
i
= g
p
i
, Q
i
= g

i
) và y =
n

i=1
(y
i
+ q
i
). Trong giao thức đã đề xuất, X và Y
được biết trước bởi người dùng. Giao thức được trình bày trong Hình 3.1.
3.2.4. Phân tích giao thức
Trong luận án đã cung cấp các chứng minh về tính đúng đắn và tính riêng tư
cho giao thức. Tính riêng tư được chỉ ra dựa trên thuộc tính không thể phân biệt
của sơ đồ mã hóa ElGamal dưới giả thiết DDH.
Định lý 3.1. Nếu tất cả người dùng tuân thủ quy tắc của giao thức trong Hình
3.1. Miner sẽ tính chính xác f như đã định nghĩa trong phần 3.2.1.
Định lý 3.2. Giả sử f < n, giao thức trong Hình 3.1 đảm bảo tính riêng tư cho
mỗi người dùng trung thực chống lại Miner và lên đến 2n-2 người dùng không trung
thực. Trong trường hợp với chỉ hai người dùng trung thực, kết luận trên vẫn đúng
khi mà hai người dùng đó không giữ các giá trị thuộc tính của cùng một bản ghi.
7
• Phase 1. Each user U
i
does as follows:
– Randomly choose k
i
from {1, , q − 1}.
– Compute C
(i)

i
= 0 then compute R
(i)
= (R
(i)
1
, R
(i)
2
, R
(i)
3
)=(X
r
i
i
X
q
i
, g
r
i
, Y
p
i
)
– if v
i
= 1 then compute R
(i)

– Send R
(i)
to the miner.
• Phase 3. Each user U
i
does as follows:
– Get R
(i)
from the miner.
– Compute K(u
i
, v
i
) = (K
(i)
1
, K
(i)
2
) = (R
(i)
1
(R
(i)
2
)
−x
i
X
y

Độ phức tạp của mỗi U
i
trong bước thứ nhất và bước thứ ba là 2 và 3 phép mũ
modular. Mỗi V
i
sử dụng 3 phép mũ modular trong bước thứ 2. Miner sử dụng 2n
phép nhân modular và nhiêu nhất n phép so sánh. Để đánh giá hiệu quả của giao
thức trong thực tế chúng ta xây dựng một thí nghiệm sử dụng ngôn ngữ C# trên
một máy tính PC. Đo lường thời gian tính toán của giao thức với n khác nhau, từ
1000 đến 5000. Ta chọn |p| = 1024 bits và |q| = 160 bits, các cặp khóa và các giá
trị X, Y được tạo ra trước khi giao thức thực thi. Kết quả chỉ ra rằng mỗi U
i
cần
trung bình 21ms và 29ms, cho việc tính toán ở bước thứ nhất và bước thứ ba. Mỗi
V
i
cần khoảng 32ms để tính toán. Thời gian của Miner là tương đối hiệu quả và
gần tuyến tính theo n, ví dụ khi n = 5000, Miner cần khoảng 460 ms.
3.3. Khai phá dữ liệu dựa trên tính tần suất trong 2PFD
Phương pháp tính toán tần suất là rất quan trọng trong các ứng dụng PPDM
mà việc học của chúng dựa trên tần suất, ví dụ như học bộ phân lớp naive Bayes,
8
khai phá luật kết hợp, họ c cây quyết định ID3, phân tích tương quan Pearson, v.v.
Trong luận án đã minh họa khả năng ứng dụng của phương pháp bằng việc sử dụng
nó để xây dựng giao thức học bộ phân lớp naive Bayes có đảm bảo tính riêng tư.
3.4. Cải tiến giao thức tính toán tần suất
3.4.1. Giao thức cải tiến
Một vấn đề của giao thức tính toán tần suất là nếu chỉ một người dùng không
tham gia vào giao thức thì người Miner sẽ không tính được giá trị tần suất. Mục
đích cải tiến là để cho phép Miner có thể tính được tần suất f từ dữ liệu của tập

và h(0) = p
0
. Do đó, mỗi U
i
có các cặp khóa
(x
i
, X
i
= g
x
i
) và V
i
có (p
i
, P
i
= g
p
i
). Trong giao thức, H = g
x
0
+p
0
được thông báo
như tham số chung. Giao thức được trình bày trong Hình 3.7.
3.4.2. Phân tích giao thức
So với giao thức trước, giao thức này thay thế Y bằng g và X bằng H = g

(i)
1
, C
(i)
2
) = (g
u
i
X
k
i
i
, g
k
i
)
– Send C
(i)
to the miner.
• Phase 2. Each user V
i
does the follows:
– Get C
(i)
from the miner,
– Randomly choose r
i
and q
i
from {1, , q − 1},

(i)
= (R
(i)
1
, R
(i)
2
, R
(i)
3
)=(g
u
i
X
r
i
+k
i
i
H
q
i
, g
r
i
+k
i
, g
q
i

H
y
i
, R
(i)
3
g
y
i
) .
– Send K
(i)
to Miner.
• Phase 4. Miner computes K =

i∈S
K
(i)
2
• Phase 5. The users does as follows:
– Each U
i
computes a
i
= K
x
i
and sends a
i
to Miner

(i)
1
K
′
.
– Find f from {0, 1, , n} that satisfies g
f
= d
– Output f.
Hình 3.7: Giao thức tính toán tần suất cải tiến
thảo luận một phương pháp cải tiến dựa trên sơ đồ chia sẻ mật của Shamir, việc
cải tiến cho phép Miner có thể đạt được giá trị tần suất mà không yêu cầu sự tham
gia đầy đủ của n cặp người dùng.
10
Chương 4
NÂNG CAO TÍNH RIÊNG TƯ CHO VIỆC KHAI PHÁ TẬP PHỔ
BIẾN TRONG DỮ LIỆU PHÂN MẢNH DỌC
4.1. Giới thiệu
Chương này đề xuất các giao thức cho việc khai phá các tập phổ biến trong
mô hình dữ liệu phân mảnh dọc. Các giao thức này cho phép một số thành viên
(mỗi thành viên giữ tập các thuộc tính của cùng tập các giao dịch) hợp tác để khai
phá tập phổ biến trên tập dữ liệu liên kết của các thành viên trong khi bảo vệ các
thông tin riêng tư của mỗi thành viên. Một số giao thức đã được đề xuất cho vấn
đề này [Zhong, 2007, Vaidya and Clifton, 2005, Han and Ng, 2007]. Tuy nhiên, các
giao thức này hoặc là chỉ chống lại được sự thông đồng của nhiều nhất n −2 thành
viên trong n thành viên tham gia giao thức hoặc là yêu cầu một thành viên tin cậy
không thông đồng. Mục đích của chương này là đề xuất các giao thức có khả năng
đảm bảo được sự riêng tư đầy đủ cho thành viên, do đó chúng có khả chống lại
sự thông đồng của một nhóm thành viên bất kỳ trong khi không yêu cầu bất kỳ
thành viên tin cậy nào. Hơn thế nữa luận án đã đề xuất ra hai giao thức mà cho

im
),
ở đây u
ij
∈ {0, 1}, i = 1, , n, và j = 1, , m. Một giá trị công khai t, vấn đề
xác định tập phổ biến có đảm bảo tính riêng tư là để kiểm tra xem có hay không
s =

m
j=1

n
i=1
u
ij
≥ t, trong khi đảm bảo thông tin về mỗi véc tơ của mỗi thành
viên là không bị bộc lộ cho thành viên khác.
4.3. Định nghĩa về việc đảm bảo tính riêng tư
Tương tự như định nghĩa về việc đảm bảo tính riêng tư trong chương 3, định
nghĩa của chương này cũng được phát biểu như một trường hợp riêng của định
nghĩa 2.3. Tuy nhiên, khác với chương 3, trong mô hình tính toán của chương này,
chúng ta giả thiết mỗi thành viên tham gia trong giao thức đều có thể truyền thông
với nhau, vì vậy vai trò của mỗi thành viên là như nhau. Do đó, định nghĩa này
tương tự như định nghĩa 2.3, chỉ khác là giao thức đã đề xuất dựa trên hệ mã hóa
ElGamal và mỗi thành viên được giả thiết là có một cặp khóa. Bởi vậy, trong View
của mỗi thành viên sẽ bao gồm các khóa công khai của các thành viên còn lại và
mỗi khóa mật được coi như một thành phần của input.
4.4. Giao thức không bộc lộ độ hỗ trợ
4.4.1. Tổng quan
Giả sử X là một tập phổ biến và s = X.count thì t ≤ s ≤ m. Do đó sẽ tồn tại

π (1)
, , g
r
k
λ
π (k)
)
Ở đây (λ
π(1)
, , λ
π(k)
) là một hoán vị ngẫu nhiên của (λ
1
, , λ
m
), và r
j
=

n
i=1
r
ij
,
mỗi r
ij
được chọn ngẫu nhiên trong [1, q −1] bằng thành viên P
i
.
Nếu đạt được kết quả này các thành viên có thể kiểm tra sự tồn tại của λ


n
i=1
y
i
. Trong giao thức đã đề xuất, mỗi thông báo m sẽ
biến đổi thành g
m
trước khi mã hóa. Các thành viên sử dụng y như một khóa công
khai chung để mã hóa. Việc giải mã yêu cầu tất cả các thành viên tham gia. Sơ đồ
này có hai thuộc tính đồng cấu cộng và đồng cấu nhân, các thuộc tính này là rất
quan trọng để đạt được mục tiêu tính toán của chúng ta.
Kỹ thuật ngẫu nhiên hóa: là một giao thức chạy trên mạng gồm một số
mix server. I nput là một tập các mã hóa α
1
, , α
m
, output là tập các mã hóa mới
α
′
1
, , α
′
m
được tạo ra từ tập hoán vị và mã hóa lại từ tập input. Thuộc tính bảo
mật của giao thức này dựa trên tính chất không thể phân biệt được vị trí của mỗi
input khi quan sát trên tập output. Trong giao thức của chúng ta mỗi thành viên
sẽ đóng vai trò như một mix server.
4.4.2. Giao thức
Giao thức được trình bày trong Hình 4.1.

) (u
ij
∈ {0, 1})
Output: Check ∈ {T rue, False}
• Phase 1. Encryption and connection.
For j = 1, , m
– For i = 1, , n: P
i
computes C
i
(j)
def
= (a
ij
, h
ij
) = (y
α
ij
, g
α
ij
), where α
ij
is randomly
picked from [1, q − 1].
– P
1
computes C
j

ij
, h
u
ij
j
h
ij
) and sends C
j
to
P
i+1 (mod n)
P
1
computes C = (a, h) = (

m
j=1
a
j

m
j=1
h
j
) and broadcasts it.
• Phase 2. Encryption randomization. For j = 1, , k
– For i = 1, , n : P
i
computes C

j
to P
2
,
– For i = 2, , n : P
i
computes C
j
= (a
j
, h
j
) = (a
j
a
ij
, h
j
h
ij
) and sends C
j
to P
i+1 (mod n)
• Phase 3. Randomization and permutation. For i = 1, , n
– P
i
computes: for j = 1, , k, R
j
= (R

i+1 (mod n)
. Here π
i
is an permutation on {1, , k} and δ
π
i
(j)
is
uniformly chosen from [1, q −1].
• Phase 4. Decryption.
For j = 1, , k
– For i = 1, , n : P
i
computes h
ij
= (h
j
)
x
i
– P
1
sets h
j
= h
1j
and sends it to P
2
– For i = 2, , n : P
i

j=1

n
i=1
u
ij
≥ t,
ta sẽ đưa ra giao thức để tính s. Ký hiệu λ = {λ
j
|λ
j
=

n
i=1
u
ij
− n, j = 1, , m},
chú ý rằng

n
i=1
u
ij
= 1 khi mà λ
j
= 0. Do đó, s chính là số giá trị 0 trong danh
sách λ. Mục đích của giao thức là để đếm số giá trị 0 này mà không bộc lộ thông
tin về mỗi λ
j

π (m )
)
Nếu đạt được kết quả này, chúng ta đạt được hai mục đích. Đầu tiên các thành
viên có thể đếm số λ
j
= 0 mà nó tương đương với g
λ
j
= g
0
= 1. Thứ hai, tính riêng
tư được bảo vệ vì các thành viên sẽ không biết g
λ
π (j)
được sinh ra từ λ
j
nào.
4.5.2. Giao thức
Giao thức được trình bày trong Hình 4.2
Input: There are n parties, each party P
i
has U
i
= (u
i1
, u
im
) (u
ij
∈ {0, 1})

is
randomly chosen from [1, q −1].
– P
1
computes C
j
= (a
j
, h
j
) = (g
−n
y
α
1j
, g
α
1j
) and sends C
j
to P
2
– For i = 2, , n: each P
i
computes C
j
= (a
j
, h
j

(j)
, h
π
i
(j)
g
δπ
i
(j)
), after that
P
i
sets C
j
= R
j
and sends C
j
to P
i+1 (mod n)
. Here π
i
is an permutation on {1, , m}
and δ
j
is uniformly chosen from [1, q −1].
• Phase 3. The key component computation: For j = 1, , m,
– For i = 1, , n : each P
i
computes h

does:
– s = 0
– For j = 1, , m : d
j
= a
j
/h
j
if d
j
= 1 then s = s + 1;
– Output s
Hình 4.2: Giao thức tính toán độ hỗ trợ.
4.5.3. Phân tích tính đúng đắn
Định lý 4.3. Nếu tất cả các thành viên tuân thủ các bước tính toán của giao thức.
Số lượng giá trị 1 trong danh sách giải mã {d
1
, d
2
, , d
m
} chính là độ hỗ trợ s.
15
4.5.4. Phân tích tính riêng tư
Định lý 4.4. Giao thức trong hình 4.2 đảm bảo sự riêng tư cho mỗi thành viên
tham gia chống lại sự thông đồng lên đến n −1 không trung thực.
4.5.5. Phân tích hiệu năng
Độ phức tạp tính toán và truyền thông thực tế của giao thưc này là nhỏ hơn
giao thức trong Hình 4.1, tuy nhiên về mặt ước lượng là tương đương. Để đánh
giá hiệu quả của giao thức này trong thực tế, ta xây dựng một thí nghiệm sử dụng

rằng các giao thức này có thể chống lại sự thông đồng lên đến n − 1 thành viên
không trung thực trong n thành viên tham gia. Thêm vào đó, luận án đã đưa ra
hai giao thức mà nó cho phép các thành viên có thể chọn một trong hai mức độ
riêng tư, một giao thức không bộc lộ bất kỳ thông tin gì, giao thức còn lại chỉ bộc
lộ độ hỗ trợ của mỗi tập mục.
16
Chương 5
PHÂN CỤM DỮ LIỆU CÓ ĐẢM BẢO TÍNH RIÊNG TƯ
5.1. Giới thiệu
Chương này trình bày phương pháp đảm bảo tính riêng tư cho việc phân cụm
dựa trên thuật toán EM trong dữ liệu phân mảnh ngang. Đầu tiên là một giao thức
nhiều thành viên được đề xuất. Không giống như giao thức đã đề xuất trước đây
[Lin et al., 2005], giao thức được đề xuất trong chương này không bộc lộ các giá
trị tổng của các tham số cục bộ, bởi vậy nó đảm bảo tính riêng tư tốt hơn và có
thể cho phép hai hoặc nhiều thành viên tham gia vào giao thức. Hơn thế nữa giao
thức này đảm bảo sự riêng tư của mỗi thành viên chống lại sự thông đồng với số
lượng có thể lên đến n −2 thành viên khác. Thứ hai là đề xuất một giao thức tốt
hơn trong trường hợp tập dữ liệu chỉ phân mảnh thành hai phần, giao thức này
cho phép tính toán kết quả cuối cùng mà không bộc lộ các thông tin riêng tư và
các trung tâm của các cụm dữ liệu.
5.2. Phát biểu bài toán
Thuật toán EM được trình bày trong [Dempster et al., 1977]. Gọi D là tập dữ
liệu có m đối tượng và d thuộc tính. Giả sử tồn tại k lớp trong D, mỗi lớp thuộc
về một số phân bố Gauss. Các tham số của một lớp i là ψ
i
= {µ
i
, Σ
i
, π

n
, mỗi thành viên
giữ một số đối tượng của D. Mục đích là đề xuất các giao thức cho phép các thành
viên thực hiện phân cụm trên tập dữ liệu liên kết D, sao cho mỗi thành viên sẽ
biết được các đối tượng mà nó sở hữu thuộc về các cụm nào, trong khi đảm bảo
tính riêng tư cho mỗi đối tượng dữ liệu và các tham số thống kê cục bộ.
5.3. Giao thức cho mô hình nhiều thành viên
Trong thuật toán EM, tại bước lặp thứ t để mỗi thành viên tính được z
ij
, nó
cần biết các tham số Σ
i
, µ
i
và π
i
. Các tham số này có thể được trình bày dưới dạng
17
µ
(t+1)
i
=

n
l=1
A
il
/

n

l=1
m
l
.
Các công thức trên có thể trình bày dưới một dạng chung là A/B mà ta gọi là giá
trị trung bình. Ở đây A =

n
i=1
x
i
và B =

n
i=1
m
i
, trong đó mỗi thành viên P
i
sở
hữu hai giá trị x
i
và m
i
. Vì vậy, vấn đề chính là xây dựng giao thức để tính giá trị
trung bình, trong khi đảm bảo thông tin riêng tư về mỗi x
i
và m
i
. Giả sử, A và B

and v
i
to P
n
2: P
n
computes u =

n
i=1
u
i
mod M and v =

n
i=1
v
i
mod M
3: Each P
i
randomly splits r
i
into n − i + 1 parts {r
ij
|j = i, , n}, and k
i
into n − i + 1 parts
{k
ij

k
ij
mod M.
Next it sends r
′
i
and k
′
i
to P
1
5: P
1
computes r = r
11
+

n
i=2
r
′
i
mod M and k = k
11
+

n
i=2
k
′

where α is a public constant used to make all elements integer
7: P
n
computes s
n
= b
n
− a
n
mod M and sends it to P
1
; P
1
computes s
1
= s
n
+ b
1
− a
1
mod M
and broadcasts it to all parties
8: Finally, all parties can calculate µ = exp(s
1
/α).
Hình 5.1: Tính toán giá trị trung bình nhiều thành viên bảo mật
Giao thức tính giá trị trung bình sau đó được sử dụng để thiết kế giao thức
phân cụm EM có đảm bảo tính riêng tư, về cơ bản như trong Hình 5.2.
5.4. Giao thức cho mô hình hai thành viên

(t+1)
i
and π
(t+1)
i
by using Protocol 5.1
7: For each l ∈ {1, , n}, P
l
locally computes B
il
.
8: The parties jointly compute Σ
(t+1)
i
by using Protocol 5.1
9: For each l ∈ {1, , n}, P
l
locally computes z
ijl
.
10: end for
11: t = t + 1
12: The parties jointly compute δ = |log(L(ψ
(t+1)
) −log(L(ψ
(t)
)|
13: end while
Hình 5.2: Phân cụm dữ liệu nhiều thành viên có đảm bảo tính riêng tư
Input: Two parties, Alice and Bob have (n, x) and (m, y), respectively.

, Bob obtains b
2
= Q
3
(pn + pm) = −r(pn + pm) + py +
px − (pn + pm) q.
7: Alice has r
1
= r and Bob computes r
2
=
b
2
b
1
+ q = −r +
x+y
n+m
.
So, the respective outputs of Alice and Bob are r
1
and r
2
, giving us that r
1
+ r
2
=
x+y
n+m

cách Mahalanobis: [Alqallaf e t al., 2002, Hodge and Austin, 2004] :
d
2
i
= (X(i) −
X)
T
C
−1
(X)(X(i) − X)
for i = 1, , N. Khoảng cách lớn sẽ chỉ ra đối tượng thứ i
th
là một phần tử ngoại
lai. Bởi vậy, công việc chính là tính C
−1
(X) và
X.
Giả sử X được phân mảnh dọc hoặc ngang trên K thành viên. Mục đích chương
này là thiết kế các giao thức cho phép các thành viên hợ p tác tìm ra đối tượng
nào là phần tử ngoại lai, trong khi đảm bảo thông tin riêng của mỗi đối tượng dữ
liệu cũng như các tham số thống kê cục bộ ví dụ như: véc tơ trung bình, ma trận
covariance.
6.2.2. Biến đổi tuyến tính
Gọi M là ma trận vuông khả nghịch cấp n, mỗi phần tử m
ij
của M nhận các
giá trị thực. Gọi Y = XM, ta gọi Y là ma trận đạt được từ việc biến đổi tuyến
tính X thông qua ma trận M.
Bổ đề 6.1. Gọi G(X) là ma trận Gram của X, ở đây G(X) = X
T

)
m×q
và B = ( b
ij
)
q×n
là hai ma trận riêng tư của hai thành
viên Alice và Bob tương ứng. Mục đích của giao thức này là để tính hàm sau:
(A, B) → (S
a
, S
b
)|S
a
+ S
b
= AB
6.3. Các giao thức cho trường hợp dữ liệu phân mảnh ngang
Gỉa sử tập dữ liệu được phân mảnh ngang trên K thành viên, mỗi thành viên
P
i
có tập X
i
của N
i
đối tượng, chú ý rằng N =

K
i=1
N

Trong các phần tiếp theo sẽ trình bày hai giao thức cho việc phát hiện các phần
tử ngoại lai trong dữ liệu phân mảnh ngang. Hai công việc quan trọng là tính
X
và C
−1
(X). Sau đó các thành viên có thể sử dụng các giá trị này để tính khoảng
cách Mahalanobis cục b ộ cho mỗi đối tượng mà nó sở hữu.
21
6.3.1. Giao thức hai thành viên
Giả sử tập dữ liệu được phân mảnh ngang trên hai thành viên Alice và Bob,
trong đó Alice có tập X
1
của N
1
đối tượng và Bob có tập X
2
của N
2
đối tượng.
Giao thức được trình bày trong hình 6.2.
Input: Alice and Bob have the data sets X
(1)
and X
(2)
, respectively.
Output: The Mahalanobis distance of each object
1. The parties use the secure sharing mean protocol to compute X.
2. The parties share the matrix C(X) by using the secure mean sharing protocol. Alice obtains
C
(1)

T
7. Each party uses C
−1
(X) and
X to locally compute Mahalonobise distance for its every object.
Hình 6.2: Giao thức cho dữ liệu phân mảnh ngang hai thành viên.
6.3.2. Giao thức nhiều thành viên
Giao thức được trình bày trong hình 6.3.
6.4. Giao thức cho dữ liệu phân mảnh dọc hai thành viên
Giả sử tập dữ liệu được phân mảnh dọc trên hai thành viên Alice và Bob, trong
đó Alice có tập X
1
của n
1
thuộc tính và Bob có tập X
2
của n
2
thuộc tính. Trong
trường hợp này chú ý rằng
X có thể được tính toán cục bộ bằng mỗi thành viên, vấn
đề còn lại là tính ma trận C(X). Như trong luận án đã trình bày, C(X) có thể tính
được nhờ sử dụng giao thức PMPS. Đối với việc tính khoảng cách Mahalanobis,
vì mỗi đối tượng được chia thành hai phần, mỗi phần được giữ bằng một thành
viên khác, do đó các thành viên không thể tính toán cục bộ khoảng cách này như
trường hợp phân mảnh ngang, mà nó phải giải quyết bằng SPP. Bởi vậy, giao thức
đã đề xuất sẽ phải thực hiện các tính toán sau:
1. Sử dụng PMPS để tính (
ˆ
X

(i)
.
Output: The Mahalanobis distance of each object
1. The parties use the secure sum protocol to compute N =

K
i=1
N
i
2. Each party locally the matrix C
k
.
3. Party 1 generates a random matrix M, then each party i (i = 2, , K) and party 1 uses
PMPS proto col to share C
(i)
M, party 1 obtains M
(1)
i
and party i obtains M
(2)
i
.
4. Party 1 computes C
(1)
M +

K
i=1
M
(1)

phương pháp chia sẻ bộ nhớ dùng chung. Tập dữ liệu gồm 500 mẫu với 20 thuộc
tính, thực hiện đánh giá thí nghiệm cho trường hợp dữ liệu được phân mảnh ngang
hai thành viên. Kết quả cho thấy, giao thức là tương đối hiệu quả, thời gian tính
toán là tuyến tính, chủ yếu phụ thuộc n và phụ thuộc rất ít vào N. Ví dụ, khi
n = 20 và N = 500, thời gian tính toán khoảng 10.47s.
6.6. Kết luận chương
Chương này đã đề xuất các giao thức đảm bảo tính riêng tư cho việc phát hiện
phần tử ngoại lai dựa trên thống kê. Tính đúng đắn của giao thức đã được chứng
minh dựa trên Bổ đề 6.1. Tính riêng tư của giao thức đượ c chứng minh dựa trên
cả hai mô hình đảm bảo tính riêng tư là mô hình semi-honest và mô hình mở rộng.
Trong luận án cũng đã cung cấp các kết quả thực nghiệm để chỉ ra hiệu quả của
các giao thức.
23
KẾT LUẬN
Luận án đã đề xuất bốn giải pháp cho bốn vấn đề trong PPDM. Mỗi giải pháp
đã được cung cấp các phân tích để chứng mình tính đúng đắn cũng như tính riêng
tư dựa trên định nghĩa đảm bảo tính riêng tư trong mô hình semi-honest. Độ phức
tạp truyền thông và tính toán của mỗi giải pháp được đánh giá dựa trên phương
pháp ước lượng lý thuyết. Luận án cũng đã cung cấp một số thực nghiệm để đánh
giá hiệu quả của các giải pháp trong thực tế.
Đóng góp thứ nhất là đề xuất một giải pháp khai phá dữ liệu dựa trên tính tần
suất trong tình huống mới 2PFD. Bước quan trọng của giải pháp là phương pháp
tính toán tần suất có đảm bảo tính riêng tư. Khả năng ứng dụng của phương pháp
đã được minh họa bằng việc sử dụng nó để xây dựng giao thức cho việc học bộ
phân lớp Naive Bayes. Các kết quả thực nghiệm chỉ ra rằng giao thức đ ã đề xuất
là hiệu quả và thực tế.
Đóng góp thứ hai là đề xuất hai giao thức mới cho việc khai phá tập phổ biến
trong dữ liệu phân mảnh dọc: một giao thức không bộc lộ bất kỳ thông tin gì, giao
thức còn lại chỉ bộc lộ độ hỗ trợ của tập phổ biến. Thuộc tính quan trọng của các
giao thức này tốt hơn các giao thức trước đây ở chỗ nó có thể đảm bảo sự riêng