ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT&TT

Nguyễn Văn Chung

ĐỀ XUẤT MỘT SỐ GIẢI PHÁP KHAI PHÁ
DỮ LIỆU PHÂN TÁN ĐẢM BẢO TÍNH RIÊNG TƯ
Chun ngành

: Khoa học máy tính

Mã số

: 9480101

TĨM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - NĂM 2023


Cơng trình được hồn thành tại: Trường Đại học Cơng nghệ thông tin
và Truyền thông - Đại học Thái Nguyên

Người hướng dẫn khoa học:
1. PGS.TS Trần Đức Sự
2. TS Nguyễn Văn Tảo

Phản biện 1: .........................................................................
..............................................................................................
Phản biện 2: .........................................................................
..............................................................................................

Phản biện 3: .........................................................................
..............................................................................................
Luận án được bảo vệ trước Hội đồng chấm luận án cấp Đại học Thái
Nguyên, họp tại ..................................................................................
.............................................................................................................
Vào hồi

giờ

ngày

tháng

năm

Có thể tìm hiểu luận án tại thư viện: ...................................


1
MỞ ĐẦU
1. Tính cấp thiết
Mỗi ngày, hàng triệu giao dịch điện tử có thể được thực hiện,
hay hàng tỷ bình luận/cảm xúc được bày tỏ trên các trang mạng xã hội.
Bằng việc khai phá, phân tích những nguồn dữ liệu này, các tri thức
hoặc thơng tin có giá trị đã được tìm ra và đem lại nhiều lợi ích đáng
kể cho những tổ chức, cá nhân [1].
Trên thực tế, bất kỳ một tập dữ liệu nào cũng chứa những thông
tin mang tính chất riêng tư, nhạy cảm như: bệnh lý của bệnh nhân, thu
nhập của khách hàng, quan điểm chính trị của người dùng. Vấn đề này
là cản trở lớn đối với hoạt động khai phá dữ liệu.

Trước thách thức đó, nghiên cứu và phát triển các giải pháp khai
phá tri thức và thơng tin hữu ích tiềm ẩn trong các tập dữ liệu trong
khi những thông tin riêng tư, nhạy cảm tồn tại bên trong dữ liệu vẫn
được giữ an tồn và bí mật bởi các bên sở hữu trở thành một nhiệm vụ
rất cần thiết và quan trọng, thu hút được nhiều sự quan tâm từ cộng
đồng nghiên cứu [2].
2. Mục tiêu nghiên cứu
Luận án tập trung nghiên cứu ba vấn đề chính sau đây:
- Vấn đề thứ nhất là nghiên cứu, đánh giá các giải pháp khai phá
dữ liệu đảm bảo tính riêng tư hiện có, đặc biệt là những giải pháp dựa
trên lĩnh vực tính tốn bảo mật nhiều thành viên.
- Vấn đề thứ hai là phát triển một số kỹ thuật tính tốn bảo mật
nhiều thành viên và chứng minh các đề xuất mới hiệu quả hơn và có
khả năng ứng dụng cao hơn các phương pháp đã có.
- Vấn đề thứ ba là dựa trên các kỹ thuật tính tốn bảo mật nhiều
thành viên mới phát triển, đề xuất một số giao thức khai phá dữ liệu đảm
bảo tính riêng tư cho cả hai mơ hình dữ liệu phân mảnh theo chiều ngang
và chiều dọc; đánh giá hiệu quả và tính riêng tư của các giải pháp mới.
3. Đối tượng và phạm vi nghiên cứu
- Đối tượng nghiên cứu của luận án là các phương pháp khai
phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư dựa trên phương
pháp tính tốn bảo mật nhiều thành viên.


2
- Phạm vi nghiên cứu của luận án tập trung vào bài tốn khai
dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư.
4. Cách tiếp cận và phương pháp nghiên cứu
- Cách tiếp cận: luận án tổng hợp, phân tích, đánh giá các cơng
trình có liên quan tới vấn đề khai phá dữ liệu từ nhiều nguồn có đảm

bảo tính riêng tư, từ đó đề xuất giải pháp phù hợp để giải quyết các
vấn đề đã đặt ra.
- Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết
và nghiên cứu thực nghiệm.
5. Các nội dung nghiên cứu chính, đóng góp mới của luận án
- Thứ nhất, luận án góp phần làm rõ bức tranh khái quát về lĩnh
vực khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư, đồng
thời phát hiện ra những khoảng trống nghiên cứu dựa trên việc đánh
giá một số công trình nghiên cứu liên quan.
- Thứ hai, luận án phát triển một số giao thức tính tốn bảo mật
nhiều thành viên. Giao thức thứ nhất tính tổng bảo mật cải tiến, giao
thức thứ hai tính tổng bảo mật tổng quát, giao thức thứ ba cho phép
tính tốn tích vơ hướng bảo mật trong mơ hình ba thành viên dựa trên
giao thức đánh giá đa thức bảo mật, và hai giao thức cuối cùng tính độ
hỗ trợ bảo mật cũng cho mơ hình tính tốn ba thành viên.
- Thứ ba, luận án đề xuất các giao thức an toàn và hiệu quả để
khai phá dữ liệu đảm bảo tính riêng tư cho ngữ cảnh phân tán ngang
và phân tán dọc. Đồng thời, các thí nghiệm trên dữ liệu thật cũng đã
chứng minh khả năng ứng dụng thực tế của những giải pháp đề xuất.
6. Ý nghĩa khoa học và thực tiễn
6.1. Ý nghĩa khoa học
- Đề xuất một số giao thức tính tốn bảo mật nhiều thành viên
an tồn và hiệu quả.
- Đề xuất giải pháp phân lớp dữ liệu Naïve Bayes đảm bảo tính
riêng tư cho mơ hình dữ liệu phân tán ngang và giải pháp khai phá luật
kết hợp đảm bảo tính riêng tư cho kịch bản dữ liệu phân tán dọc ba
thành viên.


3

6.2. Ý nghĩa thực tiễn
Kết quả nghiên cứu của luận án có thể được sử dụng làm cơ sở
phát triển các ứng dụng khai phá dữ liệu đảm bảo tính riêng tư cho các
kịch bản mơ hình dữ liệu phân tán.
7. Bố cục luận án
- Chương 1 trình bày tổng quan về khai phá dữ liệu từ nhiều
nguồn có đảm bảo tính riêng tư.
- Chương 2 trình bày các khái niệm cơ bản về mật mã và tính
tốn bảo mật nhiều thành viên; phân tích đánh giá một số giao thức
tính tốn bảo mật nhiều thành viên điển hình để từ đó phát triển các
giao thức tính tốn bảo mật nhiều thành viên, bao gồm: giao thức tính
tổng bảo mật cải tiến, giao thức tính tổng bảo mật tổng quát, giao thức
tính tích vơ hướng bảo mật trong mơ hình ba thành viên, hai giao thức
tính độ hỗ trợ bảo mật cũng cho mơ hình tính tốn ba thành viên.
- Chương 3 trình bày các giao thức mới để khai phá dữ liệu đảm
bảo tính riêng tư cho ngữ cảnh phân tán dọc và phân tán ngang.
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU TỪ
NHIỀU NGUỒN CÓ ĐẢM BẢO TÍNH RIÊNG TƯ
1.1. Giới thiệu chương
Trong chương này, luận án trình bày tổng quan về khai phá dữ
liệu từ nhiều nguồn có đảm bảo tính riêng tư, trong đó giới thiệu một
số phương pháp phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư
phổ biến: Phương pháp biến đổi ngẫu nhiên, phương pháp tính tốn
bảo mật nhiều thành viên, phương pháp ẩn danh dữ liệu. Cuối chương
này, luận án đánh giá một số giải pháp khai phá luật kết hợp từ nhiều
nguồn có đảm bảo có đảm bảo tính riêng tư và xác định các vấn đề
luận án cần giải quyết.
1.2. Giới thiệu về khai phá dữ liệu có đảm bảo tính riêng tư
Các nghiên cứu về khai phá dữ liệu phân tán có đảm bảo quyền
riêng tư liên quan đến ba vấn đề chính sau đây [5]. Thứ nhất, các tổ

chức như các cơ quan chính phủ muốn công bố dữ liệu cho các nhà


4
nghiên cứu hay cộng đồng. Tuy nhiên, do các ràng buộc khác nhau mà
họ phải bảo vệ quyền riêng tư dữ liệu, ví dụ dữ liệu riêng tư về sức
khỏe và tài chính. Thứ hai, một nhóm các tổ chức mong muốn cùng
nhau đạt được kết quả khai phá trên tập dữ liệu chung mà không tiết lộ
tập dữ liệu riêng của mỗi bên. Thứ ba, một người khai phá dữ liệu muốn
triển khai các mơ hình khai phá dữ liệu từ dữ liệu người dùng, trong khi
mỗi người vẫn giữ bí mật dữ liệu của họ.
1.3. Tổng quan về các phương pháp khai phá dữ liệu từ nhiều
nguồn có đảm bảo tính riêng tư
Về cơ bản, có ba hướng tiếp cận để xây dựng một giải pháp
PPDM: ngẫu nhiên (randomization), ẩn danh (anonymity), và tính
tốn bảo mật nhiều thành viên (secure multi-party computation-SMC).
1.3.1. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư
dựa trên phương pháp biến đổi ngẫu nhiên
Ý tưởng cơ bản của phương pháp biến đổi ngẫu nhiên: cơ sở dữ
liệu ban đầu chứa những thông tin riêng tư được biến đổi thành một
cơ sở dữ liệu mới nhằm che giấu các thông tin riêng tư nhưng kết quả
của quá trình khai phá dữ liệu trên cơ sở dữ liệu ban đầu và cơ sở dữ
liệu sau khi đã được biến đổi là tương đồng hoặc độ chính xác có sự
sai lệch khơng đáng kể. Trong phương pháp biến đổi ngẫu nhiên, hai
kỹ thuật chính được sử dụng là biến đổi dữ liệu và ngẫu nhiên hóa dữ
liệu. Biến đổi dữ liệu là kỹ thuật thay thế mỗi bản ghi trong tập dữ liệu
gốc ban đầu bằng một bản ghi có cùng cấu trúc nhưng ẩn đi các giá trị
thực [18], [19], [20], [21]. Ngẫu nhiên hóa dữ liệu là kỹ thuật thêm các
giá trị nhiễu vào tập dữ liệu gốc nhưng vẫn đảm bảo phân bố dữ liệu
không thay đổi [22], [23], [24], [25].

Mặc dù phương pháp biến đổi ngẫu nhiên khá hiệu quả nhưng
các giải pháp PPDM theo hướng tiếp cận này phải đánh đổi giữa độ
chính xác về kết quả của bài tốn khai phá dữ liệu và tính riêng tư
[10], [29]. Nếu chúng ta yêu cầu tính riêng tư cao hơn đối với bài tốn
khai phá dữ liệu thì độ chính xác sẽ giảm xuống và ngược lại.
1.3.2. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư
dựa trên phương pháp ẩn danh


5
Một phương pháp đảm bảo quyền riêng tư cũng tương đối phổ
biến là ẩn danh (anonymity). Khác với kỹ thuật biến đổi ngẫu nhiên,
ẩn danh yêu cầu dữ liệu công bố có số lượng thuộc tính nhất định,
khiến những kẻ tấn cơng khơng tìm thấy thuộc tính cụ thể bằng thông
tin riêng tư và ngăn chặn thông tin riêng tư cá nhân bị rị rỉ. Do vậy,
phương pháp này có khả năng bảo vệ sự riêng tư của dữ liệu trong một
số trường hợp.
Mặc dù phương pháp k-ẩn danh có thể ngăn chặn nguy cơ định
danh người dùng từ dữ liệu công bố, tuy nhiên phương pháp này trong
thực tế vẫn không thể đáp ứng các nhu cầu khác nhau của chủ sở hữu
dữ liệu và nhà cung cấp theo mức độ đảm bảo quyền riêng tư. Một số
chứng minh cho thấy dữ liệu được xử lý bằng phương pháp này thường
không vượt qua được một số cuộc tấn công và dễ bị lừa đảo qua
internet [29].
1.3.3. Khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư
dựa trên phương pháp tính tốn bảo mật nhiều thành viên (SMC)
Các giao thức tính tốn bảo mật nhiều thành viên SMC cho phép
tính tốn giá trị của hàm số trong khi các bên tham gia vẫn giữ riêng
tham số đầu vào của mình. Nói một cách khác, các phương thức SMC
có thể bảo vệ dữ liệu riêng tư của bên sở hữu với mức độ an toàn cao

hơn so với hai phương pháp cịn lại. Chính vì thế, luận án này chỉ tập
trung vào các giải pháp PPDM dựa trên SMC.
1.3.3.1. Một số giải pháp PPDM cho mơ hình dữ liệu phân tán ngang
1.3.3.2. Một số giải pháp PPDM cho mơ hình dữ liệu phân tán dọc
1.4. Xác định các vấn đề luận án cần giải quyết
Như vậy, tính đến nay đã có nhiều giải pháp được đề xuất để
giải quyết các vấn đề trong khai phá dữ liệu từ nhiều nguồn có đảm
bảo tính riêng tư. Tuy nhiên, như đã trình bày và phân tích đánh giá ở
trên, các giải pháp PPDM hiện tại còn tồn tại nhiều hạn chế. Cụ thể là
những giải pháp dựa trên kỹ thuật biến đổi ngẫu nhiên tương đối hiệu
quả nhưng phải đánh đổi giữa độ chính xác về kết quả của bài tốn
khai phá dữ liệu với tính riêng tư của dữ liệu các bên tham gia, các
giải pháp tiếp cận theo phương pháp ẩn danh dễ dàng để triển khai


6
khơng đủ an tồn trước các cuộc tấn cơng trên mạng cơng khai (ví dụ:
Internet), và các giái pháp PPDM được xây dựng dựa trên những giao
thức SMC có khả năng bảo vệ dữ liệu riêng tư của các bên tham gia
nhưng thường có độ phức tạp tính tốn và truyền thơng lớn. Bên cạnh
đó, những ứng dụng PPDM triển khai thực tế cịn tương đối nghèo nàn.
Vì vậy, mục tiêu của luận án này hướng đến giải quyết một số
vấn đề sau:
1. Phát triển một số giao thức tính tốn nhiều thành viên đảm
bảo tính bảo mật và hiệu quả phù hợp áp dụng vào các giải pháp
PPDM, cụ thể là: giao thức tính tổng bảo mật nhiều thành viên, giao
thức tích ba véc tơ bảo mật, và giao thức tính độ hỗ trợ bảo mật.
2. Dựa trên các giao thức tính tốn bảo mật nhiều thành viên
được đề xuất, phát triển một số giải pháp khai phá dữ liệu có đảm bảo
tính riêng tư cho cả hai mơ hình dữ liệu phân mảnh theo chiều ngang

và chiều dọc có khả năng triển khai trong thực tế.
1.5. Kết luận chương
CHƯƠNG 2. PHÁT TRIỂN PHƯƠNG PHÁP TÍNH TỐN
BẢO MẬT NHIỀU THÀNH VIÊN
2.1. Giới thiệu chương
Trong chương này luận án trình bày một số giao thức tính tốn
bảo mật nhiều thành viên phổ biến và phân tích, đánh giá từng giao
thức. Từ những hạn chế của các giao thức này, luận án đề xuất một số
giao thức tính tốn bảo mật nhiều thành viên được cải tiến được trình
bày trong mục 2.4, trong đó:
- Mục 2.4.1 là giao thức Tổng bảo mật cải tiến [CT1]
- Mục 2.4.2 là giao thức tính Tổng bảo mật tổng quát [CT2]
- Mục 2.4.3 là giao thức Tích ba véc tơ bảo mật [CT3]
- Mục 2.4.4 và mục 2.4.5 là hai giao thức Tính tốn bảo mật độ
hỗ trợ của 3 thành viên [CT4], [CT5]
2.2. Một số khái niệm cơ bản
2.3. Một số giao thức tính toán bảo mật nhiều thành viên phổ biến


7
2.4. Phát triển một số một số giao thức tính toán bảo mật nhiều
thành viên
2.4.1. Giao thức tổng bảo mật cải tiến [CT1]
a. Giao thức
Lấy ý tưởng từ giao thức tổng bảo mật của [66] được trình bày
ở mục 2.3.1.3, giao thức tổng bảo mật cải tiến cũng gồm hai giai đoạn.
Tuy nhiên, việc cải tiến được tập trung chính trong giai đoạn 1 của
giao thức. Trong giai đoạn này của giao thức gốc [66], mỗi thành viên
𝑃𝑖 chia nhỏ ngẫu nhiên tổng của mình thành các thành phần 𝑣𝑖,𝑗 (𝑗 =
𝑖, 𝑖 + 1, … , 𝑛 − 1), giữ lại một phần 𝑣𝑖,𝑖 và gửi các phần còn lại cho

các thành viên 𝑃𝑖+1 , … , 𝑃𝑛−1. Sự khác biệt của giao thức đề xuất ở chỗ
𝑃𝑖 sẽ chọn ngẫu nhiên một số thành viên trong các thành viên cịn lại
để gửi thay vì gửi cho tất cả các thành viên. Chúng ta cùng xem xét mơ
hình tính tốn trong ví dụ có 6 thành viên 𝑃0 , 𝑃1 , 𝑃2 , 𝑃3 , 𝑃4 , 𝑃5 dưới đây.

Hình 2. 2. Giai đoạn 1, giao thức tổng bảo mật cải tiến có 6 thành viên
Trong ví dụ này, 𝑃1 chỉ chia sẻ dữ liệu với 𝑃3 và 𝑃5 ; 𝑃2 lại gửi
dữ liệu cho cả 𝑃3 , 𝑃4 , 𝑃5 ; 𝑃3 chỉ gửi dữ liệu cho 𝑃4 ; 𝑃4 chỉ gửi dữ liệu
cho 𝑃5 .
Nói một cách tổng quát, trong giai đoạn 1 của giao thức cải tiến
các thành viên 𝑃𝑖 khơng gửi các phần cịn lại cho các thành viên
𝑃𝑖+1 , … , 𝑃𝑛−1 , mà 𝑃𝑖 sẽ gửi ngẫu nhiên cho một số thành viên bất kỳ,
ngẫu nhiên ở đây được chia làm 2 loại:
- Ngẫu nhiên về số lượng: có nghĩa là số lượng thành viên mà
𝑃𝑖 sẽ gửi tới là ngẫu nhiên từ 1 đến M.


8
- Ngẫu nhiên về đối tượng: có nghĩa là khơng ai biết trước
thành viên nào sẽ được gửi tới.
Giai đoạn 2: thực hiện tương tự giai đoạn 2 của giao thức tổng
bảo mật gốc:
- Các 𝑃𝑖 tính 𝑉𝑖′ = 𝑣𝑖,𝑖 + ∑ 𝑣𝑖,𝑘 sau đó gửi cho 𝑃0
- 𝑃0 tính tổng 𝑉 = 𝑉0 + 𝑉1′ + 𝑉2′ + 𝑉3′ + 𝑉4′ + 𝑉5′
b. Đánh giá giao thức
- Tính riêng tư: mức độ đảm bảo tính riêng tư là 𝑀 − 2.
- Tính hiệu quả:
 Trường hợp xấu nhất là

𝑀(𝑀−1)

2

 Trường hợp tốt nhất là 2𝑀 − 3 thông điệp
Như vậy số thông điệp sẽ nằm trong khoảng [2𝑀 − 3,

𝑀(𝑀−1)
].
2

2.4.2. Giao thức tính tổng bảo mật tổng quát [CT2]
2.4.2.1. Đặt vấn đề
Giao thức tính tổng bảo mật tổng quát (gọi tắt là GSSP) được
đề xuất gồm hai pha chính như sau:
a. Pha 1: Mỗi thành viên 𝑃𝑖 (𝑖 = 1, 2, … , 𝑛) chia sẻ một phần
của giá trị bí mật 𝑆𝑖 cho t thành viên ngẫu nhiên (1 ≤ t < n)
- Bước 1: Mỗi thành viên 𝑃𝑖 chia giá trị bí mật 𝑆𝑖 thành (t+1)
phần bí mật 𝑆𝑖 = 𝑆𝑖0 + 𝑆𝑖1 + ⋯ + 𝑆𝑖𝑡 , 𝑃𝑖 giữ lại 𝑆𝑖0 .
- Bước 2: Mỗi thành viên 𝑃𝑖 lựa chọn ngẫu nhiên bí mật t số
khác nhau: ai1, ai2,…, ait (aij {2,…, n}\{i}) rồi gửi mỗi 𝑆𝑖𝑗
cho 𝑃𝑎𝑖𝑗 tương ứng.
b. Pha 2: Tính tổng bảo mật S
- Bước 1: Mỗi thành viên 𝑃𝑖 (i = 1, … , 𝑛) nhận được các giá
trị 𝑆𝑗𝑘 từ các thành viên 𝑃𝑗 khác, sau đó thành viên 𝑃𝑖 tính
giá trị Di = Si0 + ∑ 𝑺jk. Mỗi thành viên 𝑃𝑖 (i = 2, … , 𝑛) gửi Di
cho 𝑃1
- Bước 2: P1 tính D = ∑𝒏𝒊=𝟏 𝑫i = ∑𝒏𝒊=𝟏 𝑺i = S.


9


Hình 2.3. Mơ hình giai đoạn 1 của giao thức tính tổng bí mật tổng qt

Hình 2.4. Mơ hình giai đoạn 2 của giao thức tính tổng bí mật tổng quát
2.4.2.2. Đánh giá giao thức
a. Đánh giá độ chính xác
Giao thức GSSP tính tốn được S = ∑𝑛𝑖=1 𝑆i đáp ứng yêu cầu của
bài toán đã phát biểu ở mục 2.4.2.1.
b. Đánh giá tính riêng tư


Trường hợp 1: nếu k = 1 thì C(n, n-k) = 1 nghĩa là
GSSP khơng thể chống lại được n-1 thành viên thông
đồng với mọi t.


10



Trường hợp 2: nếu n-k < t+1 thì C(n, n-k) = 0 nghĩa là
GSSP luôn chống lại được (n-k) thành viên thơng đồng
Trường hợp 3: các trường hợp cịn lại

Xác suất của giải pháp này chống (n-k) thành viên thông đồng là:
P(n, n-k) = 1- C(n, n-k) = 1 -

𝒏−𝒌 (𝒏−𝒕−𝒌+𝟏)…(𝒏−𝒕−𝟏)
. (𝒏−𝒌+𝟏)…(𝒏−𝟏) .
𝒏


𝒕

(1- 𝒏−𝟏)k-1

c. Đánh giá tính hiệu quả
- Độ phức tạp tính tốn: Độ phức tạp tính tốn của giao thức
GSSP là O(tn).
- Chi phí truyền thơng: Chi phí truyền thông của giao thức GSSP
là cần truyền (t+1)n -1 thông điệp.
Một vài so sánh giữa GSSP và các giải pháp tính tổng bảo mật tương
tự được tổng hợp trong bảng dưới đây.
Bảng 2.1. So sánh giao thức GSSP với một vài giải pháp tổng bảo mật điển
hình
Giao thức

Tính riêng tư/ Khả năng
chống thơng đồng

Hiệu năng
Độ phức
tạp

Chi phí truyền thơng

SSP cơ bản

O(n)

nM


O(nM)

SSP-HE

O(H*n)

nM+(n-1)Mkey

O(nM)

SSP-CRDM

n-2

O(n2)

𝑛(𝑛−1)

M

O(n2M)

CFR-SSP

n-2

O(n2)

n(n+2)M


O(n2M)

CR-SSP

P(n, m) = 1
−∑m
k=t0 (Pr(k) ∗ p(m, k))

O(n)

(t0n+n)M+t0n

O(nM)

O(n)

(tn+n)M-M

O(nM)

O(n2)

n2M

O(n2M)

2

t0+1


t+1
GSSP

t<
P(n, n-k) = 1 (1-

t = n-1

𝑡
𝑛−1

n-2

𝑛−𝑘
𝑛

.

𝑡
𝐶𝑛−𝑘
𝑡
𝐶𝑛−1

.

)k-1

(O(H) là độ phức tạp tính tốn của HE, M là độ dài thơng điệp,
Mkey là độ dài khóa của HE, t0 << n-3)

11
d. Mối quan hệ giữa mức độ an toàn và hiệu năng của giao thức đề xuất
Vì giải pháp mà luận án đề xuất và giải pháp CR-SSP [78] đều
có chung ý tưởng xây dựng mơ hình tốn học mơ tả quan hệ giữa tính
riêng tư và hiệu năng, do đó luận án so sánh khả năng chống thơng
đồng của hai giải pháp này bằng cách lựa chọn các bộ tham số (n, k ,
P(n, n-k)) để xác định số thành viên t. Kết quả thực nghiệm được trình
bày ở bảng dưới đây.
Bảng 2. 2. Kết quả thực nghiệm khả năng chống thông đồng của
GSSP và CR-SSP

60
40
20
0
0

20

40

60

80 100

Số thành viên thông đồng
2

4

8

10

100
80
60
40
20
0

0
10
20
30
40
50
60
70
80
90
100

80

Số thành viên thông đồng

6

100
80
60
40
20
0
Số thành viên thông đồng

5

10

20

25

15

Khả năng chống thông đồng (%)

Khả năng chống thông đồng (%)

100

0
50
100
150
200

250
300
350
400
450
500

500

Khả năng chống thông đồng (%)

100

CR-SSP
Khả năng chống thông đồng (%)

GSSP

n

2

4

8

10

6

100
80
60
40
20
0

0
50
100
150
200
250
300
350
400
450
500

SSP

Số thành viên thông đồng

5

10

20

25

15


80
60
40
20
0
0

200 400 600 800 1000
Số thành viên thông đồng

5

10

20

25

100
80
60
40
20
0

15

0
100
200
300
400
500
600
700
800
900
1000

100
0

100

Khả năng chống thông đồng (%)

Khả năng chống thông đồng (%)

12

Số thành viên thơng đồng

5

10

20

25

15

Nhìn vào kết quả trên, chúng ta có thể dễ dàng thấy rằng:
- Khả năng chống thông đồng của hai giải pháp GSSP và CRSSP là hoàn toàn tương đồng nhau.
- Khả năng chống thông đồng của cả hai giao thức được so sánh
đều “đồng biến” với giá trị tham số 𝑡. Nghĩa là, khi t càng lớn thì khả
năng chống thơng đồng của cả hai giao thức càng cao và ngược lại.
Quan trọng hơn nữa, căn cứ vào những kết quả thực nghiệm ở trên,
bên phát triển ứng dụng có thể thiết lập các tham số phù hợp với yêu cầu
của từng bài toán thực tế.
2.4.3. Giao thức tích ba véc tơ bảo mật
2.4.3.1. Giao thức đánh giá đa thức bảo mật dựa trên hệ hệ mật
ElGamal
a. Giao thức đánh giá đa thức bảo mật [CT3]
Đầu vào: 𝐴 có giá trị 𝑎, 𝑏 và 𝐵 sở hữu 𝑥.
Đầu ra: 𝐵 thu được 𝑦 = 𝑎𝑥 + 𝑏, trong khi không biết giá trị 𝑎, 𝑏.
Bước 1. 𝐵 tạo cặp khóa cơng khai và bí mật (𝑘, g 𝑘 ) của hệ mã
ElGamal
Bước 2. 𝐵 chọn ngẫu nhiên bí mật 𝑟 và tính 𝐶 = (g 𝑟 , g 𝑥 g 𝑘𝑟 ) , sau
đó gửi cho 𝐴
Bước 3. 𝐴 chọn ngẫu nhiên bí mật 𝑐 rồi tính (g 𝑟 )𝑎 g 𝑐 và
𝑎

(g 𝑥 g 𝑘𝑟 ) g 𝑏 (g 𝑘 )𝑐 sau đó gửi 𝐵.

13
𝑎

Bước 4. 𝐵 tính ((g 𝑟 )𝑎 g 𝑐 )−𝑘 (g 𝑥 g 𝑘𝑟 ) g 𝑏 (g 𝑘 )𝑐 để thu được
𝑔ax + b. Sau đó 𝐵 sử dụng thuật tốn vét cạn hoặc Shank step-giantstep để tìm ra 𝑎𝑥 + 𝑏.
b. Phân tích giao thức
- Tính riêng tư: Giao thức đã đề xuất là đảm bảo tính riêng tư
dựa trên phương pháp mơ phỏng.
- Tính hiệu quả: Độ phức tạp tính tốn của mỗi thành viên tương
đương với một phép mũ module và một phép nhân module.
2.4.3.2. Giao thức tích ba véc tơ bảo mật [CT3]
a. Giao thức
⃗⃗, 𝑍⃗ t tương ứng.
Đầu vào: Ba thành viên 𝑃𝑎 , 𝑃𝑏 , 𝑃𝑐 , có ba véc tơ 𝑋⃗, 𝑌
Đầu ra: < 𝑋, 𝑌, 𝑍 >.
Bước 1. 𝑃𝑎 tạo ra một véc tơ ngẫu nhiên 𝑅 và sau đó tạo ra một
véc tơ đa thức tuyến tính. Mỗi phần tử của véc tơ 𝑅⃗⃗ phân phối ngẫu
nhiên trên trường do người dùng xác định.
Bước 2. 𝑃𝑎 và 𝑃𝑏 tham gia vào q trình tính tốn các 𝑄𝑖 (𝑦𝑖 ), (𝑖 =
⃗⃗ = 𝑄1 (𝑦1 ), 𝑄2 (𝑦2 ), … , 𝑄𝑚 (𝑦𝑚 ), trong
1 … 𝑚), trong đó 𝑃𝑏 thu được 𝑄
đó 𝑄𝑖 (𝑦𝑖 ) = 𝑥𝑖 𝑦𝑖 + 𝑟𝑖 .
Bước 3. 𝑃𝑎 và 𝑃𝑐 thực hiện giao thức tích vô hướng bảo mật [62]
với đầu vào 𝑃𝑎 là 𝑅⃗⃗ và 𝑃𝑐 là 𝑍⃗, trong đó 𝑃𝑐 thu được < 𝑅, 𝑍 >= ∑𝑚
𝑖=1 𝑟𝑖 𝑧𝑖
Bước 4. 𝑃𝑏 và 𝑃𝑐 thực hiện giao thức tích vơ hướng với đầu vào 𝑃𝑏
⃗⃗
là 𝑄 và 𝑃𝑐 là 𝑍⃗, trong đó 𝑃𝑏 thu được < 𝑄, 𝑍 >= ∑𝑚
𝑖=1 𝑥𝑖 𝑦𝑖 𝑧𝑖 + 𝑟𝑖 𝑧𝑖
Bước 5. 𝑃𝑏 tính < 𝑋, 𝑌, 𝑍 > = < 𝑄, 𝑍 > −< 𝑅, 𝑍 >.

Bước 6. 𝑃𝑏 gửi đến 𝑃𝑎 và 𝑃𝑐
b. Phân tích giao thức
Định lý 2.4: Giao thức tích ba véc tơ bảo mật tính được tích vơ
hướng trong khi bảo vệ được tính riêng tư cho từng thành viên.
Chi phí truyền thơng: Chi phí truyền thơng của giao thức tích
ba véc tơ bảo mật là 2𝐶𝑜𝑠𝑡(𝑚) + 𝐶𝑜𝑠𝑡′(𝑚).


14
2.4.4. Giao thức Bảo mật độ hỗ trợ
Trong trường hợp đặc biệt chỉ có ba thành viên, luận án đề xuất
một phương pháp khai phá tập phổ biến đảm bảo quyền riêng tư có
cùng chi phí truyền thơng với giao thức của Zhong, đảm bảo quyền
tính tư tốt hơn giao thức [60] và [79]. Giao thức được đề xuất có thể
bảo vệ quyền riêng tư của mỗi thành viên và chống được sự thông
đồng của 2 thành viên không trung thực.
2.4.4.1. Mơ hình tính tốn
2.4.4.2. Giao thức Bảo mật độ hỗ trợ [CT4]
a. Ý tưởng của giao thức
Giả sử 𝑋 là một tập phổ biến, ta có 𝑡 ≤ 𝑠 ≤ 𝑚, tồn tại giá trị
0 trong danh sách 𝜆 = {𝜆1 = 𝑠 − 1 − 𝑡, 𝜆2 = 𝑠 − 2 − 𝑡, . . . , 𝜆𝑘 = 𝑠 −
𝑘 − 𝑡}, trong đó 𝑘 = 𝑚 − 𝑡. Với mục đích giữ bí mật giá trị s, ý tưởng
cơ bản của giao thức như sau: Đặt 𝑝 và 𝑞 là hai số nguyên tố sao cho
𝑝 = 2𝑞 + 1, gọi 𝐺 là tập con của ℤ𝑝∗ và 𝑔 là phần tử sinh của 𝐺. Tất
cả các tính tốn trong phần này thực hiện trong ℤ𝑝 , giao thức được đề
xuất thực hiện chức năng sau:
(𝑈1 , 𝑈2 , 𝑈3 ) ↦ (𝑔𝑟1 𝜆𝜋(1) , 𝑔𝑟2 𝜆𝜋(2) , … . . , 𝑔𝑟𝑘 𝜆𝜋(𝑘) )
Trong đó (𝜆𝜋(1) , … , 𝜆𝜋(𝑘) ) là một hoán vị ngẫu nhiên của (λ1,...,
λm). Giả sử 𝑟𝑗 = ∑𝑛𝑗=1 𝑟𝑖𝑗 , trong đó 𝑟𝑖𝑗 được tạo ra ngẫu nhiên từ [1, 𝑞 −
1] bởi thành viên 𝑖. Sau đó, các thành viên có thể kiểm tra tồn tại 𝜆𝑗 =

0 tương đương với 𝑔𝑟𝑗 𝜆𝑗 = 𝑔0 = 1. Rõ ràng khi 𝜆𝑗 ≠ 0, 𝑔𝑟𝑗𝜆𝑗 là một
số ngẫu nhiên, do đó giao thức khơng tiết lộ bất kỳ thơng tin nào khác
ngoài kết quả cuối cùng.
b. Thiết kế giao thức
Ý tưởng của giao thức đề xuất bao gồm 4 giai đoạn:
Giai đoạn 1: Giai đoạn này thu được bản mã của tích vơ hướng
(độ hỗ trợ s) của tất cả các véc tơ từ các thành viên sử dụng tính chất
nhân đồng cấu của sơ đồ mã hóa.
Giai đoạn 2: Tạo ra bản mã hóa của các giá trị được che giấu
𝑟𝑗 𝑗 (𝑗 = {1, … , 𝑘}). Để thu được kết quả này, mỗi thành viên chia thành
phần đầu tiên của mã hóa s cho các giá trị {𝑔𝑡+1 , … , 𝑔𝑡+𝑘 } và ngẫu nhiên


15
hóa nó bằng các giá trị ngẫu nhiên 𝑟𝑖𝑗 . Sau đó, các thành viên thực hiện
lặp để kết nối tất cả các bản mã thu được bản mã hóa của 𝑟𝑗 𝑗 .
Giai đoạn 3: Các thành viên thực hiện n vịng lặp để hốn vị và
ngẫu nhiên tập bản mã bằng kỹ thuật tái ngẫu nhiên.
Giai đoạn 4: Các thành viên cùng giải mã các bản mã mới nhận
được, theo thứ tự độc lập của các bản mã ban đầu, sau đó kiểm tra bản
giải mã hiện tại có bằng 1 (g0) khơng.
Chi tiết về giao thức bảo mật độ hỗ trợ được trình bày như sau:
Đầu vào: Có 3 thành viên, mỗi thành viên 𝑃𝑖 có véc tơ riêng
⃗⃗⃗⃗
𝑈𝑖 = (𝑢𝑖1 , … , 𝑢𝑖𝑚 )
(𝑢𝑖𝑗 ∈ {0,1}; 𝑖 = 1, … , 3; 𝑗 = 1, … , 𝑚)
Đầu ra: Kiểm tra = True hoặc False.
Giai đoạn 1. Mã hóa
For j = 1,...,m
- For i = 1, …, 3

𝑃𝑖 tính 𝐶𝑖 (𝑗) = (𝑎𝑖𝑗 , ℎ𝑖𝑗 ) = (𝑦 𝛼𝑖𝑗 , 𝑔𝛼𝑖𝑗 ), trong đó 𝛼𝑖𝑗 được
chọn ngẫu nhiên từ [1, q - 1].
- 𝑃1 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑔𝑢1𝑗 𝑎1𝑗 , ℎ1𝑗 ), gửi 𝐶𝑗 đến 𝑃2 ,
𝑢

𝑢

𝑢

𝑢

- 𝑃2 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎𝑗 2𝑗 𝑎2𝑗 , ℎ𝑗 2𝑗 ℎ2𝑗 ), gửi 𝐶𝑗 đến 𝑃3 ,
- 𝑃3 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎𝑗 3𝑗 𝑎3𝑗 , ℎ𝑗 3𝑗 ℎ3𝑗 ), gửi 𝐶𝑗 đến 𝑃1 ,
𝑚
𝑃1 tính 𝐶 = (𝑎, ℎ) = (∏𝑚
𝑗=1 𝑎𝑗 , ∏𝑗=1 ℎ𝑗 ) gửi cho 𝑃2 và 𝑃3 .

Giai đoạn 2. Ngẫu nhiên hóa bản mã
For j = 1,..., k
- For i = 1,..., 3
𝑟

𝑃𝑖 tính 𝐶𝑖 (𝑗) = (𝑎𝑖𝑗 , ℎ𝑖𝑗 ) = ((𝑎⁄𝑔𝑡+𝑗 ) 𝑖𝑗 , ℎ𝑟𝑖𝑗 ), trong đó 𝑟𝑖𝑗
được chọn ngẫu nhiên từ [1, q - 1].
- 𝑃1 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎1𝑗 , ℎ1𝑗 ), gửi 𝐶𝑗 đến 𝑃2 ,
- 𝑃2 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎𝑗 𝑎2𝑗 , ℎ𝑗 ℎ2𝑗 ), gửi 𝐶𝑗 đến 𝑃3 ,


16
- 𝑃3 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎𝑗 𝑎3𝑗 , ℎ𝑗 ℎ3𝑗 ), gửi 𝐶𝑗 đến 𝑃1 .

Giai đoạn 3. Ngẫu nhiên và hoán vị
For i = 1,..., 3
For j = 1,..., k
- 𝑃𝑖

(1)

(2)

tính 𝑅𝑗 = (𝑅𝑗 , 𝑅𝑗 ) = (𝑎𝜋𝑖(𝑗) 𝑦 𝛿𝜋𝑖(𝑗) , ℎ𝜋𝑖(𝑗) 𝑔𝛿𝜋𝑖(𝑗) ).

Trong đó 𝜋𝑖 là một hốn vị trên {1,..., k} và 𝛿𝜋𝑖(𝑗) được chọn ngẫu
nhiên từ [1, q - 1].
- 𝑃𝑖 đặt 𝐶𝑗 = 𝑅𝑗 , sau đó gửi 𝐶𝑗 cho 𝑃𝑖+1(𝑚𝑜𝑑 𝑛)
Giai đoạn 4. Giải mã
For j = 1,..., k
- For i = 1, …, 3
𝑃𝑖 tính ℎ𝑖𝑗 = (ℎ𝑗 )𝑥𝑖
- 𝑃1 đặt ℎ𝑗 = ℎ1𝑗 sau đó gửi ℎ𝑗 cho 𝑃2
- 𝑃2 tính ℎ𝑗 = ℎ2𝑗 ℎ𝑗 sau đó gửi ℎ𝑗 cho 𝑃3
- 𝑃3 tính ℎ𝑗 = ℎ3𝑗 ℎ𝑗 sau đó gửi ℎ𝑗 cho 𝑃1
𝑃1 tính 𝑑𝑗 = 𝑎𝑗 ⁄ℎ𝑗 , nếu 𝑑𝑗 = 1 thì Kiểm tra = True, ngược lại
Kiểm tra = Flase.
Trả về giá trị Kiểm tra.
c. Phân tích tính chính xác
Định lý 2.5: Trong Giao thức Bảo mật độ hỗ trợ nếu được trình bày
ở mục b, nếu tồn tại một bản rõ “1” trong danh sách giải mã {d1,..., dm} thì
t ≤ s ≤ n. Nếu khơng có bản rõ “1” trong danh sách giải mã, thì s < t.
d. Phân tích tính riêng tư
Định lý 2.6: Giao thức Bảo mật độ hỗ trợ bảo được trình bày ở

mục b có khả năng bảo vệ tính riêng tư của mỗi thành viên trung thực
chống lại 2 thành viên thơng đồng.
e. Phân tích tính hiệu quả
- Chi phí truyền thơng:


17
Bảng 2.3. Chi phí truyền thơng
Số vịng lặp

9

Số thơng điệp

9(2m+6k)

Số bit

9(2m+6k)K

- Độ phức tạp tính tốn:
Bảng 2.4. Độ phức tạp tính tốn của giao thức Bảo mật độ hỗ trợ
Loại phép
toán

Phép lũy
thừa

Phép nhân

Phép nghịch
đảo

Số phép toán

3(2𝑚 + 4𝑘)

3(2𝑚 + 4𝑘)

6𝑘

Số vịng lặp

3

3

3

Như vậy, độ phức tạp tính tốn tổng thể của giao thức này cũng
tương đương với độ phức tạp của Zhong [63], nhưng thấp hơn nhiều
so với độ phức tạp của Vaidya và Clifton [60] và Li cùng cộng sự [79].
2.4.5. Giao thức Tính độ hỗ trợ bảo mật [CT5]
2.4.5.1. Tổng quan
2.4.5.2. Thiết kế giao thức
Ý tưởng của giao thức như sau: Với mỗi giá trị 𝑢𝑖𝑗 , thành viên
giữ 𝑢𝑖𝑗 mã hóa giá trị này bằng khóa cơng khai của mình. Lưu ý nếu
khơng có sự trợ giúp của tất cả các thành viên không một thành viên
nào có thể giải mã bất kỳ bản mã hóa nào. Bằng tính chất cộng đồng
cấu của sơ đồ Elgamal, các thành viên lặp n vòng để kết nối tất cả các

bản mã của các giá trị nhị phân 𝑢𝑖𝑗 để có được bản mã của ∑𝑛𝑖=1 𝑢𝑖𝑗 . Kết
thúc bước này, các thành viên thu được m mã hóa của 𝜆1 , ..., 𝜆𝑚 .
Các thành viên thực hiện lặp n vịng để hốn vị và ngẫu nhiên
tập các bản mã 𝜆1′ , … , 𝜆′𝑚 . Các thành viên cùng thực hiện giải mã các
bản mã mới nhận được, theo thứ tự độc lập của các bản mã ban đầu.
Sau đó đếm xem có bao nhiêu bản giải mã bằng 1 (𝑔0 ) (giá trị này
bằng với độ hỗ trợ).
Giao thức Tính độ hỗ trợ bảo mật:


18
Đầu vào: Có 3 thành viên, mỗi thành viên Pi có véc tơ riêng
⃗⃗⃗⃗
𝑈𝑖 = (𝑢𝑖1 , … , 𝑢𝑖𝑚 )
(𝑢𝑖𝑗 ∈ {0,1}; 𝑖 = 1, … , 3; 𝑗 = 1, … , 𝑚)
3
Đầu ra: 𝑠 = ∑𝑚
𝑗=1 ∏𝑖=1 𝑢𝑖𝑗

Giai đoạn 1. Mã hóa
For j = 1,...,m
- For i = 1, …, 3
𝑃𝑖 tính 𝐶𝑖 (𝑗) = (𝑎𝑖𝑗 , ℎ𝑖𝑗 ) = (𝑔𝑢𝑖𝑗 𝑦 𝛼𝑖𝑗 , 𝑔𝛼𝑖𝑗 ), trong đó 𝛼𝑖𝑗 được
chọn ngẫu nhiên từ [1, q - 1].
- 𝑃1 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑔−𝑛 𝑎1𝑗 , ℎ1𝑗 ), gửi 𝐶𝑗 đến 𝑃2 ,
- 𝑃2 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎𝑗 𝑎2𝑗 , ℎ𝑗 ℎ2𝑗 ), gửi 𝐶𝑗 đến 𝑃3 ,
- 𝑃3 tính 𝐶𝑗 = (𝑎𝑗 , ℎ𝑗 ) = (𝑎𝑗 𝑎3𝑗 , ℎ𝑗 ℎ3𝑗 ), gửi 𝐶𝑗 đến 𝑃1 .
Giai đoạn 2. Ngẫu nhiên hóa và hốn vị
For i = 1, ..., 3
For j = 1, ..., m

- 𝑃𝑖

(1)

(2)

tính 𝑅𝑗 = (𝑅𝑗 , 𝑅𝑗 ) = (𝑎𝜋𝑖(𝑗) 𝑦

𝛿𝜋 (𝑗)
𝛿
𝑖 , ℎ (𝑗) 𝑔 𝜋𝑖 (𝑗) ).
𝜋𝑖

Trong đó 𝜋𝑖 là một hốn vị trên {1, ..., m} và 𝛿𝜋𝑖 (𝑗) được chọn đồng
đều từ [1, q - 1].
- 𝑃𝑖 đặt Cj = Rj, sau đó gửi Cj cho 𝑃𝑖+1(𝑚𝑜𝑑 3)
Giai đoạn 3. Tính tốn các thành phần
For j = 1, ..., m
- For i = 1, …, 3
𝑃𝑖 tính ℎ𝑖𝑗 = (ℎ𝑗 )𝑥𝑖
- 𝑃1 đặt ℎ𝑗 = ℎ1𝑗 sau đó gửi ℎ𝑗 cho 𝑃2
- 𝑃2 tính ℎ𝑗 = ℎ𝑗 ℎ2𝑗 sau đó gửi ℎ𝑗 cho 𝑃3
- 𝑃3 tính ℎ𝑗 = ℎ𝑗 ℎ3𝑗 sau đó gửi ℎ𝑗 cho 𝑃1
Giai đoạn 4. Giải mã