Luận án Đề 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ư

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 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Ư LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - NĂM 2023 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 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 Mã số : Khoa học máy tính : 9480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS.TS. Trần Đức Sự 2. TS. Nguyễn Văn Tảo THÁI NGUYÊN - NĂM 2023 i LỜI CAM ĐOAN Tác giả xin cam đoan các kết quả nghiên cứu và các kết luận trong luận án này là trung thực, khách quan. Những nội dung trong luận án là kết quả nghiên cứu của bản thân tác giả. Các kết quả viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào nôi dung luận án. Việc tham khảo các nguồn tài liệu được trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định. Thái Nguyên, tháng 6 năm 2023 NCS Nguyễn Văn Chung ii LỜI CẢM ƠN Luận án này được hoà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 dưới sự hướng dẫn tận tình của thầy PGS. TS Trần Đức Sự và thầy TS Nguyễn Văn Tảo, tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới hai Thầy. Tác giả xin chân thành cảm ơn Ban lãnh đạo Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên, Ban Lãnh đạo khoa cùng toàn thể quý Thầy, Cô khoa Công nghệ thông tin đã quan tâm, giúp đỡ tác giả trong suốt thời gian nghiên cứu tại Trường. Tác giả xin chân thành cảm ơn Ban giám hiệu trường Cao đẳng Kinh tế - Kỹ thuật Vĩnh Phúc; cám ơn anh, chị, em và đồng nghiệp phòng Tổ chức - Hành chính, khoa Công nghệ thông tin đã tạo điều kiện, động viên giúp đỡ tác giả trong thời gian làm nghiên cứu sinh. Xin được cảm ơn anh, chị, em nghiên cứu sinh và bạn bè đồng nghiệp gần xa đã trao đổi, động viên, khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận án. Thái Nguyên, tháng 6 năm 2023 NCS Nguyễn Văn Chung iii MỤC LỤC MỤC LỤC ...................................................................................................... i DANH MỤC CÁC TỪ VIẾT TẮT ............................................................. vi DANH MỤC BẢNG ................................................................................... vii DANH MỤC HÌNH VẼ ............................................................................. viii MỞ ĐẦU ....................................................................................................... 1 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Ư ........................................................ 6 1.1. Giới thiệu chương ............................................................................... 6 1.2. Giới thiệu về khai phá dữ liệu có đảm bảo tính riêng tư .................... 6 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ư ......................................................................................... 9 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 .................................................................. 9 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 ................................................................................... 10 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 toán bảo mật nhiều thành viên (SMC) ........................... 12 1.4. Xác định các vấn đề luận án cần giải quyết ..................................... 16 1.5. Kết luận chương ............................................................................... 17 CHƯƠNG 2. PHÁT TRIỂN PHƯƠNG PHÁP TÍNH TOÁN BẢO MẬT NHIỀU THÀNH VIÊN ....................................................................................... 18 2.1. Giới thiệu chương ............................................................................. 18 2.2. Một số khái niệm cơ bản .................................................................. 19 2.2.1. Nhóm cyclic và phần tử sinh ..................................................... 19 2.2.2. Bài toán logarithm rời rạc trong nhóm cyclic và các giả thuyết Diffie-Hellman ............................................................................................. 21 2.2.3. Phát biểu bài toán tính toán bảo mật nhiều thành viên ................... 23 iv 2.2.4. Các tính chất cơ bản của một giao thức tính toán bảo mật nhiều thành viên ............................................................................................................... 25 2.2.5. Mô hình tính toán ...................................................................... 25 2.2.6. Biến thể của hệ mật ElGamal .................................................... 26 2.2.7. Mô hình bán trung thực ............................................................. 27 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 ....... 28 2.3.1. Giao thức tổng bảo mật ............................................................. 28 2.3.2. Giao thức tích vô hướng bảo mật .............................................. 31 2.3.3. Giao thức đánh giá đa thức bảo mật .......................................... 34 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 .... 36 2.4.1. Giao thức tổng bảo mật cải tiến [CT1] ...................................... 36 2.4.2. Giao thức tính tổng bảo mật tổng quát [CT2] ........................... 38 2.4.3. Giao thức tích ba véc tơ bảo mật ............................................... 45 2.4.4. Giao thức Bảo mật độ hỗ trợ ..................................................... 49 2.4.5. Giao thức Tính độ hỗ trợ bảo mật [CT5] ................................... 61 2.5. Kết luận chương ............................................................................... 68 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 TOÁN BẢO MẬT NHIỀU THÀNH VIÊN ............................................................................. 70 3.1. Giới thiệu chương ............................................................................. 70 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 .................................................. 70 3.2.1. Giới thiệu ................................................................................... 70 3.2.2. Bài toán phân lớp Naïve Bayes trong mô hình dữ liệu phân tán ngang có ràng buộc tính riêng tư ................................................................. 73 3.2.3. Giao thức phân lớp Naive Bayes có đảm bảo tính riêng tư ....... 75 3.2.4. Đánh giá giao thức đề xuất ........................................................ 76 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 ....................................................... 81 3.3.1. Đặt vấn đề .................................................................................. 81 v 3.3.2. Bài toá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 .................................................................................. 83 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 ................................................... 84 3.3.4. Đánh giá giao thức đề xuất ........................................................ 85 3.4. Kết luận chương ............................................................................... 91 KẾT LUẬN ................................................................................................. 92 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ............ 94 TÀI LIỆU THAM KHẢO ........................................................................... 95 PHỤ LỤC .................................................................................................. 105 A. Một số đoạn lệnh Python mẫu trong thực nghiệm của mục 3.2 ....... 105 B. Một số đoạn lệnh Python mẫu trong thực nghiệm của mục 3.3 ....... 106 vi DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tên đầy đủ CR-SSP Efficient Collusion-Resisting Secure Sum Protocol DDH Decisional Diffie–Hellman DDM Distributed Data Mining GSSP General Secure Sum Protocol HE Homomorphic Encryption DM Data Mining PPDM Privacy-Preserving Data Mining SMC Secure Multyparty Computation SSL/TLS Secure Sockets Layer/ Transport Layer Security SSP Secure Sum Protocol OPE Oblivious polynomial evaluation vii DANH MỤC BẢNG 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 ...................................................................................................................... 43 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 ................................................................................................................ 44 Bảng 2.3. Chi phí truyền thông ................................................................... 60 Bảng 2.4. Độ phức tạp tính toán của giao thức tính độ hỗ trợ bảo mật ...... 61 Bảng 2.5. Chi phí truyền thông ................................................................... 68 Bảng 2.6. Độ phức tạp tính toán của giao thức tính độ hỗ trợ bảo mật ...... 68 Bảng 3.1. Thông tin bộ dữ liệu thực nghiệm .............................................. 77 Bảng 3.2. Kết quả thực nghiệm chương trình huấn luyện mô hình Naïve Bayes có đảm bảo tính riêng tư trên bộ dữ liệu tin nhắn .................................... 80 Bảng 3.3. Các thông tin cơ bản của bộ dữ liệu thực nghiệm ...................... 87 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 ........................................................... 88 Bảng 3.5. Các luật được khai phá trên bộ dữ liệu giỏ hàng ........................ 89 viii DANH MỤC HÌNH VẼ Hình 1.1. Khai phá dữ liệu đảm bảo quyền riêng tư trên mô hình phân mảnh dữ liệu .................................................................................................................. 13 Hình 2.1. Mô hình toán toán bảo mật nhiều thành viên .............................. 24 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 .... 36 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 ... 39 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 ... 40 Hình 3.1. Ví dụ về mô hình dữ liệu phân tán ngang ................................... 72 Hình 3.2. Mô hình dữ liệu phân tán dọc ba thành viên ............................... 83 Hình 3.3 Ví dụ về bộ dữ liệu mẫu ............................................................... 87 1 MỞ ĐẦU 1. Tính cấp thiết Ngày nay, sự phát triển của các hệ thống thông tin và ứng dụng web tạo ra lượng dữ liệu lớn. 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], ví dụ như: ra quyết định kinh doanh, am hiểu sở thích của khách hàng, giảm chi phí vận hành. 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 bởi một là, do lo ngại bị xâm phạm tới quyền riêng tư hoặc bị ràng buộc về chính sách bảo vệ quyền riêng tư nên bên sở hữu không sẵn sàng cung cấp dữ liệu thật cho bên khai phá; hai là, tiến trình khai phá dữ liệu có thể làm lộ ra ngoài những thông tin nhạy cảm của các tổ chức, cá nhân. 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 toà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]. Với những ý nghĩa như đã phân tích, luận án này lựa chọn đề tài “Đề 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ư”. 2. Mục tiêu nghiên cứu Mục tiêu tổng quát của luận án này là nghiên cứu nâng cao tính an toàn và hiệu quả cho một số giải pháp khai phá dữ liệu đảm bảo tính riêng tư (PPDM) dựa trên tính toán bảo mật nhiều thành viên trong mô hình dữ liệu phân tán. Để hiện thực hóa mục tiêu này, luận án tập trung nghiên cứu ba vấn đề chính sau đây: 2 - 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 toá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 toá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 toá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 toán bảo mật nhiều thành viên. - Phạm vi nghiên cứu của luận án tập trung vào bài toá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. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán, so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu. 3 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 toán bảo mật nhiều thành viên. Các giao thức này cho phép các thành viên tham gia tính toán và nhận được kết quả tính toán chính xác mà không tiết lộ thông tin riêng tư của thành viên này cho mỗi thành viên khác: giao thức thứ nhất tính tổng bảo mật cải tiến quá trình gửi và nhận dữ liệu của mỗi thành viên với nhau bằng cách thực hiện ngẫu nhiên hóa về số lượng thành viên gửi và ngẫu nhiên về giá trị gửi; giao thức thứ hai tính tổng bảo mật tổng quát cho phép các nhà phát triển ứng dụng có thể tùy chọn các mức độ bảo vệ tính riêng tư và yêu cầu về tính hiệu quả phù hợp với ngữ cảnh bài toán ứng dụng; giao thức thứ ba cho phép tính toá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 toá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. Trong trường hợp dữ liệu phân mảnh ngang, luận án áp dụng giao thức tính tổng bảo mật tổng quát đã đề xuất nhằm nâng cao hiệu quả cho quá trình phân lớp dữ liệu Naive Bayes có đảm bảo tính riêng tư trên tập dữ liệu phân tán ngang. Các đánh giá về lý thuyết và thực nghiệm đã cho thấy thuật toán đề xuất bảo toàn được độ chính xác của kết quả phân lớp và thời gian thực thi tương đối thấp. Với dữ liệu phân mảnh dọc, dựa trên giao thức tính tích vô hướng bảo mật ba thành viên đã đề xuất, luận án phát triển kỹ thuật khai phá luật kết hợp đảm bảo tính riêng tư cho phép ba thành viên hợp tác mà không tiết lộ dữ liệu của mỗi thành viên cho các thành viên khác. Luận án chỉ ra giao thức đề xuất an toàn hơn các giao thức hiện có để chống lại sự thông đồng, mức độ thông đồng là hai thành viên không trung thực, nghĩa là trong ba thành viên tham gia tính toán thì hai thành viên thông đồng với nhau cũng không 4 thể tìm ra dữ liệu riêng tư của thành viên còn lại. Đồng thời, các thí nghiệm trên bộ 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 toán bảo mật nhiều thành viên an toà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. 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. Ngoà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 toá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ế. 7. Bố cục luận án Bố cục của luận án gồm phần mở đầu và ba chương nội dung, phần cuối là kết luận của luận án tóm tắt những kết quả đạt được và những vấn đề cần nghiên cứu tiếp theo và danh mục các tài liệu tham khảo. - 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 toá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 toá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 toá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 toán ba thành viên. 5 - Chương 3 đề xuất các giải pháp khai phá dữ liệu đảm bảo tính riêng tư cho mô hình dữ liệu phân tán dựa trên các giao thức tính toán bảo mật nhiều thành viên mới được trình bày trong chương 2. Trong trường hợp dữ liệu phân mảnh ngang: luận án đề xuất giao thức tính tổng bảo mật tổng quát nhằm nâng cao hiệu quả trong phân lớp dữ liệu Naive Bayes có đảm bảo tính riêng tư. Với dữ liệu phân mảnh dọc, luận án đề xuất giải pháp khai phá luật kết hợp đảm bảo tính riêng tư trong kịch bản ba thành viên hợp tác về mặt dữ liệu dựa trên giao thức tính tích vô hướng bảo mật của ba thành viên đã phát triển. 6 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 toá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