Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Đề 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ư

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

11
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Đề 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ư" được nghiên cứu với mục tiêu là: Tổng quan về khai phá dữ liệu từ nhiều nguồn có đảm bảo tính riêng tư; 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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Đề 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 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
Công trình đượ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 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 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]. 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 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.
2 - 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. 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. 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 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 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 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.
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 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. - 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 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ậ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 toá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 toá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 toá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 toán bảo mật nhiều thành viên (SMC) Các giao thức tính toán bảo mật nhiều thành viên SMC cho phép tính toá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 toá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 toà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 toá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 toá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 toá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 TOÁ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 toá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 toá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 toá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 toá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ả: 𝑀(𝑀−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.
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 toá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à: 𝒏−𝒌 (𝒏−𝒕−𝒌+𝟏)…(𝒏−𝒕−𝟏) 𝒕 k-1 P(n, n-k) = 1- C(n, n-k) = 1 - 𝒏 . (𝒏−𝒌+𝟏)…(𝒏−𝟏) . (1- 𝒏−𝟏 ) c. Đánh giá tính hiệu quả - Độ phức tạp tính toán: Độ phức tạp tính toá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) 𝑛(𝑛−1) SSP-CRDM n-2 O(n2) 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 (Pr(k) ∗ p(m, k)) k=t0 t+1 𝑡 𝑛−𝑘 𝐶 𝑛−𝑘 t
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 toá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 Khả năng chống thông đồng (%) Khả năng chống thông đồng (%) 80 80 60 60 40 40 20 20 100 0 0 100 10 20 30 40 50 60 70 80 90 0 0 20 40 60 80 100 Số thành viên thông đồng Số thành viên thông đồng 2 4 6 2 4 6 8 10 8 10 100 100 Khả năng chống thông đồng (%) Khả năng chống thông đồng (%) 80 80 60 60 40 40 20 20 500 0 0 100 150 200 250 300 350 400 450 500 50 0 100 150 200 250 300 350 400 450 500 50 0 Số thành viên thông đồng Số thành viên thông đồng 5 10 15 5 10 15 20 25 20 25
12 100 100 Khả năng chống thông đồng (%) Khả năng chống thông đồng (%) 80 80 60 60 40 40 20 100 20 0 0 0 100 200 300 400 500 600 700 800 900 0 1000 0 200 400 600 800 1000 Số thành viên thông đồng 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à 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 toá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 toá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 toá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 𝑃 𝑏 ⃗⃗ và 𝑃𝑐 là ⃗, trong đó 𝑃 𝑏 thu được < 𝑄, 𝑍 >= ∑ 𝑖=1 𝑥 𝑖 𝑦 𝑖 𝑧 𝑖 + 𝑟𝑖 𝑧 𝑖 là 𝑄 𝑍 𝑚 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 toá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 toá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 để hoá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 hoá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 toán: Bảng 2.4. Độ phức tạp tính toá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 toán thừa đả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 toá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 để hoá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, … , 𝑚) Đầu ra: 𝑠 = ∑ 𝑗=1 ∏3 𝑢 𝑖𝑗 𝑚 𝑖=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à hoán vị For i = 1, ..., 3 For j = 1, ..., m (1) (2) 𝛿 𝜋 (𝑗) 𝛿 𝜋 (𝑗) - 𝑃𝑖 tính 𝑅 𝑗 = (𝑅 𝑗 , 𝑅 𝑗 ) = (𝑎 𝜋 𝑖(𝑗) 𝑦 𝑖 ,ℎ 𝜋 𝑖 (𝑗) 𝑔 𝑖 ). Trong đó 𝜋 𝑖 là một hoá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 toá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ã