Đề 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ư

Nội dung tài liệu: Đề 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ư

1. ĐẠ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Ư Chuyên 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
2. 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:
3. 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.
4. 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 tồ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 Nạ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.
5. 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à
6. 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
7. 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 tồ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
8. 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 tốn bảo mật nhiều thành viên phổ biến
9. 7 2.4. Phát triển một số một số giao thức tính tố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.
10. 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ả: ( −1) . Trường hợp xấu nhất là 2 . Trường hợp tốt nhất là 2 − 3 thơng điệp ( −1) Như vậy số thơng điệp sẽ nằm trong khoảng [2 − 3, ]. 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.
11. 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 quát 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 tố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.
12. 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 Hiệu năng Tính riêng tư/ Khả năng Giao thức Độ phức chống thơng đồng Chi phí truyền thơng tạp 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) 2 CFR-SSP n-2 O(n2) n(n+2)M O(n2M) t0+1 CR-SSP P(n, m) = 1 O(n) (t0n+n)M+t0n O(nM) m −∑k=t0 (Pr(k) ∗ p(m, k)) t+1 푡 푛− 푛− t<<n P(n, n-k) = 1 - . 푡 . O(n) (tn+n)M-M O(nM) GSSP 푛 푛−1 푡 k-1 (1- ) 푛−1 t = n-1 n-2 O(n2) n2M O(n2M) (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)
13. 11 d. Mối quan hệ giữa mức độ an tồ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 SSP GSSP CR-SSP n 100 100 80 80 60 60 40 40 20 20 100 0 0 0 20 30 40 50 60 70 80 90 0 20 40 60 80 100 10 100 Số thành viên thơng đồng Khả năng chống(%) đồng thơng năng Khả Số thành viên thơng đồng (%) đồng thơng chống năng Khả 2 4 6 2 4 6 8 10 8 10 100 100 80 80 60 60 40 40 20 20 500 0 0 0 0 50 50 100 150 200 250 300 350 400 450 500 100 150 200 250 300 350 400 450 500 Số thành viên thơng đồng Số thành viên thơng đồng Khả năng chống(%) đồng thơng năng Khả Khả năng chống thơng đồng (%) đồng thơng chống năng Khả 5 10 15 5 10 15 20 25 20 25
14. 12 100 100 80 80 60 60 40 40 20 100 20 0 0 0 0 200 300 400 500 600 700 800 900 0 200 400 600 800 1000 100 1000 Khả năng chống(%) đồng thơng năng Khả Số thành viên thơng đồng (%) đồng thơng chống năng Khả Số thành viên thơng đồng 5 10 15 5 10 15 20 25 20 25 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à CR- SSP là hồn tồ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 tố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 .
15. 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-giant- step để 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 Đầu vào: Ba thành viên 푃 , 푃 , 푃 , cĩ ba véc tơ ⃗, 푌⃗⃗, 푍⃗ t tương ứng. Đầ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 quá trình tính tốn các 푄푖( 푖), (푖 = 1 ), trong đĩ 푃 thu được 푄⃗⃗ = 푄1( 1), 푄2( 2), , 푄 ( ), trong đĩ 푄푖( 푖) = 푖 푖 + 푖. 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 표푠푡( ) + 표푠푡′( ).
16. 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휆 (1) 2휆 (2) 휆 ( ) (푈1, 푈2, 푈3) ↦ ( , , . . , ) Trong đĩ (휆 (1), , 휆 ( )) là một hố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 푗휆푗 0 tương đương với = = 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 ngồ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
17. 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푗 - 푃1 tính 푗 = ( 푗, ℎ푗) = ( 1푗, ℎ1푗), gửi 푗 đến 푃2, 2푗 2푗 - 푃2 tính 푗 = ( 푗, ℎ푗) = ( 푗 2푗, ℎ푗 ℎ2푗), gửi 푗 đến 푃3, 3푗 3푗 - 푃3 tính 푗 = ( 푗, ℎ푗) = ( 푗 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,
18. 16 - 푃3 tính 푗 = ( 푗, ℎ푗) = ( 푗 3푗, ℎ푗ℎ3푗), gửi 푗 đến 푃1. Giai đoạn 3. Ngẫu nhiên và hố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:
19. 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 Phép lũy Phép nhân Phép nghịch tốn thừa đảo Số phép tố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:
20. 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ã
21. 19 푃1 tính: - s = 0 - For j = 1, , m + 푗 = 푗⁄ℎ푗 + Nếu 푗 = 1 thì s = s + 1 - Trả về giá trị s. 2.4.5.3. Đánh giá tính chính xác Định lý 2.7: Trong giao thức Tính độ hỗ trợ bảo mật được trình bày ở mục 2.4.5.2, số lượng bản rõ “1” trong danh sách giải mã { 1, 2, , } chính là độ hỗ trợ. 2.4.5.4. Phân tích tính riêng tư Định lý 2.8: Giao thức Tính độ hỗ trợ bảo mật được trình bày ở mục 2.4.5.2 cĩ khả năng bảo vệ quyền 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. 2.4.5.5. Đánh giá tính hiệu quả Chi phí truyền thơng. Bảng 2.5. Chi phí truyền thơng Số vịng lặp 푛 Số thơng điệp 18 Số bit 18 퐾 Độ phức tạp tính tốn. Bảng 2.6. Độ phức tạp tính tốn của giao thức tính độ hỗ trợ bảo mật Loại phép Phép lũy Phép Phép nghịch tốn thừa nhân đảo Số phép tốn 15 15 Số vịng lặp 3 3 1 2.5. Kết luận chương
22. 20 CHƯƠNG 3. ĐỀ XUẤT MỘT SỐ GIẢI PHÁP KHAI PHÁ DỮ LIỆU 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 3.1. Giới thiệu chương Trong chương này, luận án áp dụng một số giao thức đã đề xuất ở chương 2 để 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ư dựa trên phương pháp tính tốn bảo mật nhiều thành viên. Mục 3.2 là giải pháp phân lớp dữ liệu Nạve Bayes cho mơ hình dữ liệu phân mảnh ngang cĩ bảo tồn tính riêng tư và Mục 3.3 là giải pháp khai phá luật kết hợp trong mơ hình dữ liệu phân mảnh dọc ba thành viên cĩ bảo tồn tính riêng tư của các bên tham gia khai phá. 3.2. Xây dựng giải pháp phân lớp dữ liệu Naive Bayes cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân tán ngang 3.2.1. Giới thiệu 3.2.2. Bài tốn phân lớp Nạve Bayes trong mơ hình dữ liệu phân tán ngang cĩ ràng buộc tính riêng tư 3.2.3. Giao thức phân lớp Naive Bayes cĩ đảm bảo tính riêng tư Trong nội dung này, luận án xây dựng giải pháp phân lớp dữ liệu Naive Bayes cĩ đảm bảo tính riêng tư an tồn theo mơ hình bán trung trực (semi-honest model) phổ biến. Mỗi thành viên tham gia vào mơ hình được giả sử là bán trung thực, nĩi một cách tường minh thì các thành viên này thực hiện theo hướng dẫn của giao thức nhưng khi kết thúc thì một số thành viên nguy hại cĩ thể thơng đồng để khai thác thơng tin riêng tư của những thành viên trung thực. Như đã đề cập ở trên, để xây dựng được mơ hình phân lớp dữ liệu Naive Bayes cĩ đảm bảo tính riêng tư, các bên cùng nhau tính tốn các giá trị cần thiết bằng cách triển khai giao thức tính tổng bảo mật nhiều thành viên đã được đề xuất trong [CT2] và trình bày ở mục 2.4.2. Giao thức được trình bày như sau:. Giao thức phân lớp Naive Bayes cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân tán ngang: . Đầu vào: 푛 bản ghi dữ liệu được phân tán tại 푙 bên sở hữu dữ liệu
23. 21 푠 . Đầu ra: Các giá trị 푛[ ], 푛[푗 , ] với (푗 = ̅1̅̅,̅ ̅̅, 푠 = 1̅̅̅,̅ ̅푗, = 1̅̅,̅ ̅) . Bước 1: Mỗi bên sở hữu dữ liệu 푈푖 ∈ {푈1, , 푈푙} chuẩn bị các giá trị đầu vào riêng tư từ tập bản ghi của mình. 푛푖[ ]: số bản ghi 푈푖 sở hữu mà cĩ nhãn là 퐿 ( = 1̅̅,̅ ̅). 푠 푛푖[푗 , ]: số bản ghi 푈푖 sở hữu mà cĩ đặc trưng của thuộc 푠 ̅̅̅̅̅̅ ̅̅̅̅̅ tính thứ 푗 là 푗 và mang nhãn 퐿 (푗 = 1, , 푠 = 1, 푗, = 1̅̅,̅ ̅). . Bước 2: Các bên cùng thực thi giao thức GSSP tính các giá trị 푙 푠 푙 푠 ̅̅̅̅̅̅ 푛[ ] = ∑푖=1 푛푖[ ], 푛[푗 , ] = ∑푖=1 푛푖[푗 , ] (푗 = 1, , 푠 = 1̅̅̅,̅ ̅푗, = 1̅̅,̅ ̅). . Bước 3: Bộ phân lớp Nạve Bayes được xây dựng dựa trên các giá 푛[ ] 푛[푗푠, ] trị xác suất: [ ] = , [푗푠, ] = (푗 = 1̅̅̅,̅ ̅̅, 푛 푛[ ] 푠 = 1̅̅̅,̅ ̅푗, = 1̅̅,̅ ̅). 3.2.4. Đánh giá giao thức đề xuất 3.2.4.1. Tính chính xác 3.2.4.2. Tính riêng tư 3.2.4.3. Tính hiệu quả Để chỉ ra tính hiệu quả của giải pháp phân lớp Nạve Bayes đề xuất, luận án xem xét ứng dụng giải pháp này cho bài tốn thực tế xây dựng mơ hình phát hiện tin nhắn rác (spam) với ràng buộc đảm bảo sự riêng tư của dữ liệu tin nhắn của những người cung cấp. Ngữ cảnh bài tốn này được phát biểu như sau: - Giả sử cĩ 10 nhà mạng {푈1, , 푈10}, trong đĩ mỗi nhà mạng sẵn sàng sử dụng tập 500 tin nhắn ngắn bao gồm cả tin nhắn thơng thường và tin nhắn rác. Cụ thể, mỗi nhà mạng dành 350 tin nhắn cho quá trình huấn luyện mơ hình và 150 tin nhắn cho quá trình kiểm thử. - Các nhà mạng này mong muốn phát triển cơng cụ phát hiện tin nhắn rác bằng mơ hình phân lớp Nạve Bayes được xây dựng dựa
24. 22 trên tập tất cả các tin nhắn trên, trong khi mỗi nhà mạng khơng cung cấp tập tin nhắn của khách hàng của họ. a. Mơ tả dữ liệu thực nghiệm Bộ dữ liệu thực nghiệm là 5000 tin nhắn tiếng Anh được lấy ra từ tập tin nhắn cơng khai trên Kaggle [92]. Tập dữ liệu này được tập hợp từ các nguồn: Web site Grumbletext của Anh [93], Đại học Quốc gia Singapore [94], và luận án tiến sĩ của Caroline Tag [95] tại Đại học Birmingham, và kho lưu trữ tin nhắn [96]. Mỗi tin nhắn trong bộ dữ liệu bao gồm hai thành phần chính: nội dung tin nhắn và nhãn tin nhắn (thơng thường/rác). Bảng 3.1. Thơng tin bộ dữ liệu thực nghiệm Tổng số tin nhắn sử dụng 5000 Số tin nhắn thơng thường 4311 Số tin nhắn rác 689 Như đã đề cập ở trên, 5000 tin nhắn này giả sử được lưu trữ phân tán tại cơ sở dữ liệu riêng của 10 nhà mạng {푈1, , 푈10}. b. Tiền xử lý dữ liệu c. Thiết kế và kịch bản thực nghiệm d. Kết quả thực nghiệm *Thời gian thực thi Bảng 3.2. Kết quả thực nghiệm chương trình huấn luyện mơ hình Nạve Bayes cĩ đảm bảo tính riêng tư trên bộ dữ liệu tin nhắn Thời gian tính tốn của Ui (i=2, Tham số Thời gian tính , 10) t tốn của U1 Trường hợp Trường hợp xấu nhất tốt nhất 2 1.679 1.757 0.491 4 2.030 2.054 0.932 6 2.296 2.296 1.118
25. 23 8 2.748 2.615 1.433 Chúng ta cĩ thể dễ dàng thấy rằng, thời gian thực thi của hai nhĩm nhà mạng là 푈1 và 푈푖(푖 = 2, , 10) tương đối nhỏ. Cụ thể là, trong trường hợp tham số 푡 = 2 thì tổng thời gian tính tốn của nhà mạng 푈1 chưa tới 2 giây, cịn thời gian tính tốn của từng nhà mạng 푈푖(푖 = 2, , 10) trong trường hợp xấu nhất và tốt nhất tương ứng là 1.757 giây và 0.491 giây. Thậm chí ngay cả khi tham số 푡 lên tới giá trị 8 thì thời gian tính tốn của nhà mạng 푈1 và thời gian này của từng nhà mạng 푈푖 (푖 = 2, , 10) trong trường hợp xấu nhất chưa tới 3 giây. Như vậy, cĩ thể kết luận rằng giao thức phân lớp Nạve Bayes được đề xuất trong phần này tương đối hiệu quả và hồn tồn cĩ khả năng triển khai ứng dụng thực tế. * Độ chính xác phân lớp Khi thử nghiệm mơ hình phân lớp tìm được trên bộ dữ liệu kiểm thử (1500 tin nhắn), luận án thống kê các chỉ số độ chính xác thơng thường (accuracy), độ chính xác cân bằng (balanced_accuracy), và chỉ số F1_score lần lượt tương ứng là 0.97, 0.92, và 0.93. Kết quả trên hồn tồn tương đương khi thực thi kỹ thuật phân lớp Nạve Bayes truyền thống với dữ liệu đầu vào là bộ dữ liệu tin nhắn được tiền xử lý tương tự như ở mục b. Điều này hồn tồn lơ gic với những phân tích đánh giá lý thuyết ở mục 3.2.4.1. 3.3. Giải pháp khai phá luật kết hợp cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân mảnh dọc trên ba thành viên 3.3.1. Đặt vấn đề 3.3.2. Bài tốn khai phá luật kết hợp trong mơ hình dữ liệu phân mảnh dọc trên ba thành viên 3.3.3. Giao thức khai phá luật kết hợp đảm bảo tính riêng tư cho mơ hình dữ liệu phân mảnh dọc trên ba thành viên Giao thức khai phá luật kết hợp cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân mảnh dọc trên ba thành viên: . Đầu vào: Ba thành viên 푃1, 푃2, 푃3 cĩ ba tập dữ liệu tương ứng 1, 2, 3, 푖푛_푠 , 푖푛_ 표푛 .
26. 24 . Đầu ra: L các tập phổ biến của tập dữ liệu = 1, 2, 3 . Pha 1: Khai phá tập phổ biến Bước 1: Mỗi thành viên 푃푖 xác định tập phổ biến 1- Itemset (퐿1) . Duyệt trong 푖 để tính độ hỗ trợ 푆 của từng ứng viên của tập 1- Itemset (퐿1) . Nếu 푆 >= 푖푛_푠 thì đưa vào tập 1- Itemset (퐿1), ngược lại thì loại bỏ . Cơng bố tập phổ biến 1- Itemset (퐿1) Bước 2. Mỗi thành viên xác định tập phổ biến k - Itemset (퐿 ) với = 2, 3, . Sinh các tập ứng viên k-Itemset dựa vào tập phổ biến (k-1)- Itemset (퐿 −1) . Xét từng ứng viên: o Nếu các Item một thành viên 푃푖(푖 = 1,2,3), thực hiện tính độ hỗ trợ 푆 bằng cách duyệt CSDL. o Nếu các Item hai thành viên khác nhau, sử dụng tích vơ hướng hai thành viên [62] để thực hiện tính độ hỗ trợ 푆 = . o Nếu các Item ba thành viên khác nhau, sử dụng tích vơ hướng ba thành viên để thực hiện tính độ hỗ trợ 푆 = . o Nếu 푆 >= 푖푛_푠 thì đưa vào tập k- Itemset (퐿 ), cịn ngược lại thì loại Bước 3. Lặp lại từ bước 2 cho đến khi khơng tìm thấy tập phổ biến nào khác. . Pha 2: Phát hiện luật kết hợp Bước 1: Sinh ra tập luật ứng viên từ các tập phổ biến Bước 2: Xác định luật kết hợp . Xét từng luật ứng viên: o Tính độ tin cậy của mỗi luật ứng viên dựa trên các độ hỗ trợ 푆 đã cĩ
27. 25 Nếu >= 푖푛_ 표푛 thì bổ sung ứng viên vào tập luật kết hợp 3.3.4. Đánh giá giao thức đề xuất 3.3.4.1. Tính chính xác và tính riêng tư 3.3.4.2. Tính hiệu quả Ngữ cảnh bài tốn này cụ thể như sau: - Giả sử cĩ một trung tâm thương mại cho ba cơng ty A, B, C thuê gian hàng tại tầng siêu thị để bày bán các sản phẩm, trong đĩ: cơng ty A chuyên bán thực phẩm thịt và cá, cơng ty B cung cấp rau và trái cây, và cơng ty C chuyên bán bánh kẹo và đồ uống. - Ba cơng ty A, B, C mong muốn sắp xếp các kệ loại hàng xen kẽ nhằm hỗ trợ lẫn nhau để tăng doanh thu. Do đĩ, ba cơng ty này thực hiện khai phá luật kết hợp từ dữ liệu mua sắm của khách hàng của họ, tuy nhiên mỗi cơng ty lại khơng muốn tiết lộ dữ liệu giỏ hàng của khách hàng của mình. a. Mơ tả bộ dữ liệu thực nghiệm Bộ dữ liệu thực nghiệm là 500 bản ghi được lấy tại [100]. Mỗi bản ghi dữ liệu trong bộ này chứa thơng tin sản phẩm tương ứng của giỏ hàng trong một lần mua sắm của khách hàng. Các sản phẩm được phân loại thành ba nhĩm: thực phẩm thịt và cá, rau và trái cây, và bánh kẹo & đồ uống. Bảng 3.3. Các thơng tin cơ bản của bộ dữ liệu thực nghiệm Tổng số bản ghi 500 Tổng số sảm phẩm 20 Tổng số nhĩm sản phẩm 3 b. Tiền xử lý dữ liệu c. Thiết kế và kịch bản thực nghiệm d. Kết quả thực nghiệm Các tham số mật mã p và q được thiết lập trong phần thực nghiệm này cĩ kích thước lần lượt là 1024 và 160 bits. Ngồi ra, thí
28. 26 nghiệm này cũng thiết lập các giá trị ngưỡng lần lượt là 푖푛_푠 = 0.2 và 푖푛_ 표푛 = 0.5. Bảng 3.4. Kết quả thực nghiệm chương trình khai phá luật kết hợp cĩ đảm bảo tính riêng tư trên bộ dữ liệu giỏ hàng Tác vụ Số tập Số lần thực Số lần thực Số lần thực Thời tính phổ thi giao thức thi giao thức thi giao thức gian tốn biến (1) (2) (3) (phút) L1 19 20 0 0 ~0 L2 21 52 119 0 2.6 L3 3 40 240 84 14.0 L4 0 1 18 16 2.1 Các kết quả thực nghiệm được trình bày trong bảng 3.4 trên đây. Nhìn vào bảng này chúng ta cĩ thể thấy rằng: Tổng thời gian thực thi của giao thức đề xuất trên bộ dữ liệu thử nghiệm (khơng bao gồm thời gian trễ và thời gian truyền thơng) là khoảng 18.7 phút. Thời gian này khơng phải quá nhỏ nhưng ở mức cĩ thể chấp nhận được. Ngồi ra, tập các luật được tìm ra từ 43 tập phổ biến ở trên cùng với độ tin cậy tương ứng được 3.4. Kết luận chương
29. 27 KẾT LUẬN Trong cuộc cách mạng cơng nghiệp lần thứ tư đang diễn ra, khai phá dữ liệu đã và đang đem lại nhiều lợi ích to lớn với tất cả chúng ta. Đảm bảo tính riêng tư trong quá trình khai phá dữ liệu sẽ giúp cho các tổ chức, cá nhân cĩ thể tìm kiếm ra tri thức và thơng tin hữu ích tiềm ẩn trong dữ liệu mà khơng lo ngại vấn đề quyền riêng tư bị xâm phạm. Qua việc nghiên cứu các giải pháp khai phá dữ liệu từ nhiều nguồn cĩ đảm bảo tính riêng tư, đặc biệt trên hai ngữ cảnh phân mảnh dữ liệu: theo chiều ngang và chiều dọc, luận án đạt được những kết quả chính như sau: 1. Phát triển hai giao thức tính tổng bảo mật nhiều thành viên, một giao thức đánh giá đa thức bảo mật, một giao thức tích vơ hướng bảo mật ba thành viên và hai giao thức tính độ hỗ trợ. 2. Đề xuất các giải pháp phân lớp Nạve Bayes cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân mảnh theo chiều ngang và khai phá luật kết hợp trong mơ hình dữ liệu phân mảnh theo chiều dọc ba thành viên. Các giao thức và giải pháp đề xuất đều được đánh giá về mức độ bảo đảm quyền riêng tư, tính chính xác, tính hiệu quả và khả năng ứng dụng trong thực tế. Kết quả đánh giá đã cho thấy rằng những giao thức, giải pháp này phù hợp với mục tiêu luận án đã đặt ra. Những kết quả mà luận án đã đạt được 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. Ngồi ra, các giao thức và giải pháp được đề xuất trong luận án cĩ thể được kết hơp, áp dụng để tạo ra những giải pháp PPDM cho nhiều bài tốn khai phá dữ liệu từ nhiều nguồn cĩ đảm bảo tính riêng tư khác nhau trong thực tế. Tuy luận án đã đề xuất được một số giao thức khai phá dữ liệu cĩ đảm bảo tính riêng tư và xây dựng hai giải pháp khai phá dữ liệu 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, nhưng phần thực nghiệm của giải pháp khai phá luật kết hợp cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân mảnh dọc trên ba thành viên hạn chế về thời gian khi kích thước, số chiều dữ liệu đầu vào lớn.
30. 28 Trong thời gian tới, luận án sẽ tiếp tục nghiên cứu cải thiện thời gian tính tốn của giải pháp khai phá luật kết hợp cĩ đảm bảo tính riêng tư cho mơ hình dữ liệu phân mảnh dọc trên ba thành viên. Tương lai các phương thức học máy an tồn (safe machine learning) sẽ được lựa chọn để nghiên cứu về cả măt lý thuyết và ứng dụng. Đây được xem là xu hướng mới nổi được lai hĩa giữa hai lĩnh vực rất quan trọng là học máy và an tồn thơng tin.
31. 29 DANH MỤC CÁC CƠNG TRÌNH KHOA HỌC ĐÃ CƠNG BỐ [CT1] Nguyễn Văn Chung, Nguyễn Văn Tảo, Trần Đức Sự (2019), “Phát hiện tấn cơng cĩ đảm bảo tính riêng tư từ các nguồn dữ liệu mạng phân tán”, Tạp chí Khoa học và Cơng nghệ, Chuyên san Khoa học Tự nhiên Kỹ thuật Đại học Thái Nguyên, ISSN 1859-2171, tập 200, số 07, trang 19-24. [CT2] Van Chung Nguyen (2022), “A general secure sum protocol”, Journal of Science and Technology, Le Quy Don Technical University, ISSN 1859-0209, Vol. 11, No. 01, pp. 50-59. [CT3] Nguyễn Văn Chung, Trần Đức Sự, Cao Minh Tuấn, Phạm Minh Thuấn (2019), “Khai phá luật kết hợp cĩ đảm bảo tính riêng tư trên dữ liệu phân tán dọc”, Tạp chí Nghiên cứu KH&CN quân sự, ISSN 1859-1043, Số Đặc san ATTT 08, trang 140-146. [CT4] Nguyễn Văn Chung (2020), “Một giải pháp khai phá tập phổ biến đảm bảo tính riêng tư trên dữ liệu phân mảnh dọc ba thành viên”, Kỷ yếu Hội thảo quốc gia lần thứ XXIII: một số vấn đề chọn lọc của cơng nghệ thơng tin và truyền thơng, Quảng Ninh, 2020, trang 208-214. [CT5] Nguyễn Văn Chung, Trần Đức Sự (2022), “Khai phá tập phổ biến đảm bảo tính riêng tư cho dữ liệu phân mảnh dọc sử dụng hệ mật ElGamal”, Tạp chí Khoa học - Cơng nghệ trong lĩnh vực An tồn thơng tin, Số 1.CS (16), trang 81-88.