CHƯƠNG 3 MÃ HÓA VÀ GIẢI MÃ DỮ LIỆU
3.2 MÃ HÓA VÀ GIẢI MÃ DỮ LIỆU THUÊ NGOÀI
3.2.2 Mô hình bảo mật
Chúng tôi cho D là biểu thị TDB ban đầu mà chủ sở hữu có. Để bảo vệ việc nhận dạng các hạng mục riêng, chủ sở hữu áp dụng chức năng mã hóa cho D và biến đổi D thành D*, cơ sở dữ liệu đã được mã hóa. Chúng tôi đề cập đến các hạng mục trong D như các hạng mục đơn giản và các hạng mục trong D* là hạng mục mã hóa. Mặc định là hạng
mục thuật ngữ có nghĩa là hạng mục đơn giản. Các khái niệm về bộ phổ biến đơn giản, các giao dịch đơn giản, các mô hình đơn giản, và các bản mật mã của chúng được xác định một cách rõ ràng. Chúng tôi sử dụng I để biểu thị tập hợp các hạng mục đơn và E để biểu thị các hạng mục mã hóa.
Kiến thức của đối thủ. Máy chủ hoặc một kẻ tấn công có quyền truy cập vào một phần CSDL và có thể có một số kiến thức cơ bản mà họ có thể sử dụng để tiến hành các cuộc tấn công trên cơ sở dữ liệu D* đã được mã hóa để đưa ra các suy luận.
Chúng tôi áp dụng một mô hình bảo thủ và giả định rằng kẻ tấn công biết chính xác tập các hạng mục (đơn) I trong cơ sở dữ liệu giao dịch D ban đầu và độ hỗ trợ thực tế của chúng trong D, nghĩa là, suppD(i), i ∈ I. Kẻ tấn công có thể truy cập vào các dữ liệu tương tự từ một công ty cạnh tranh, có thể đọc các báo cáo đã công bố, .v.v. Hơn nữa, chúng tôi giả định rằng kẻ tấn công có thể truy cập vào cơ sở dữ liệu đã mã hóa D*. Do đó, anh ta cũng biết tập hợp các mục mật mã và hỗ trợ của chúng trong D*, tức là suppD∗ (e), e ∈ E.
Trong đây, chúng tôi đề xuất một chương trình mã hóa dựa trên: (i) việc thay thế mỗi mục đơn trong D bằng một mật mã thay thế 1—1 (ii) bổ sung các giao dịch giả vào cơ sở dữ liệu. Đặc biệt, không có hạng mục mới nào được thêm vào. Chúng tôi giả định rằng kẻ tấn công biết điều này và do đó anh ta biết rằng |E| = |I|. Chúng tôi cũng giả định rằng kẻ tấn công biết chi tiết về các thuật toán mã hóa của chúng tôi.
Mô hình tấn công. Chủ sở hữu của dữ liệu (tức là doanh nghiệp) xem nhận dạng thực tế của: (1) tất cả các mục mã hóa (2) tất cả các giao dịch mã hóa, và (3) tất cả các tập mục thường xuyên được mã hóa là sở hữu trí tuệ cần được bảo vệ. Nếu các hạng mục mã hóa bị bẻ gẫy, nghĩa là nhận dạng thực tế của chúng bị kẻ tấn công tìm ra, thì rõ ràng là các giao dịch mã hóa và các mô hình mã hóa cũng sẽ bị bẻ gẫy, cho nên chúng cũng vẫn cần được bảo vệ. Mô hình tấn công gồm hai phần:
• Tấn công vào hạng mục: đối với mỗi hạng mục mã hóa e ∈ E, kẻ tấn công xây dựng một tập hợp các hạng mục đơn tiềm năng Cand(e) ⊂ I. Xác suất để hạng mục mã hóa e có thể bị bẻ gẫy là prob(e) = 1/ |Cand(e)|.
• Tấn công vào tập hợp: Đưa ra một tập phổ biến mã hóa E, kẻ tấn công sẽ xây dựng một tập hợp các tập phổ biến đơn tiềm năng Cand(E), trong đó mỗi X ∈ Cand(E), X ⊂ I, và |X| = |E|. Xác suất để tập phổ biến mã hóa E có thể bị bẻ gẫy là prob(E) = 1/ |Cand(E)|.
Chúng tôi đưa ra prob(e) và prob(E) là các xác suất bị tiết lộ. Từ quan điểm của chủ dữ liệu, giảm thiểu các xác suất bị tiết lộ là điều họ mong muốn. Bằng trực giác, Cand(e) và Cand(E) càng lớn càng tốt. Lý tưởng nhất là Cand(e) nên là toàn bộ các hạng mục thô.
Điều này có thể có được nếu chúng ta đưa mỗi mục mã hóa vào cùng một mức hỗ trợ, ví dụ như hỗ trợ hạng mục thường xuyên nhất trong D. Không may là lựa chọn này là không thực tế vì điều này sẽ dẫn đến việc kích thước của D* tăng rất nhiều so với D, tức là các giao dịch giả tăng lên rất nhiều. Điều này lần lượt dẫn đến sự bùng nổ mạnh mẽ các tập phổ biến, gây ra việc khai thác trên máy chủ không thể thực hiện được. Đây là điều dẫn đến buộc phải nới lỏng ràng buộc hỗ trợ tương đường và đưa ra k-ẩn danh như một giải pháp thỏa hiệp.
Diễn giải 1 (hạng mục k-ẩn danh). Cho D là một cơ sở dữ liệu giao dịch và D* là phiên bản mã hóa của nó. Chúng ta cho rằng D* đáp ứng các thuộc tính của mục k-ẩn danh được cung cấp cho mỗi mục mã hóa e ∈ E, nếu có ít nhất k-1 ngoài các mục mã hóa riêng biệt khác e1, . . . , ek−1∈ E mà suppD*(e) = suppD*(ei), 1 ≤ i ≤ k − 1.
Hình 3.4 cho thấy tác dụng của việc đưa các hạng mục mã hóa vào các nhóm hạng mục k. Đối với một giá trị của k, việc phân phối độ hỗ trợ giống như bậc thang đi xuống.
Với k nhỏ, đồ thị có xu hướng phân phối độ hỗ trợ ban đầu tại D; trong khi nếu k tăng lên, đồ thị lại gần với trục hoành đã nói bên trên. Khi kích thước của D* giống như trong biểu
đồ bên dưới, chúng ta có thể kiểm soát kích thước của D* bằng cách lựa chọn một k thích hợp.
Hình 3.4 Phân phối hỗ trợ hạng mục trên TDB đã mã hóa với k=10, 20,…, 50 [6]
Để định lượng sự bảo đảm bí mật của cơ sở dữ liệu đã mã hóa, chúng tôi đưa ra khái niệm sau:
Diễn giải 2 (k-bí mật). Cho một cơ sở dữ liệu D và phiên bản D* đã được mã hóa của nó, chúng tôi thấy rằng D* là k-bí mật nếu:
a. Đối với mỗi hạng mục mã hóa e ∈ D∗, prob(e) ≤ 1/k; và
b. Đối với mỗi tập phổ biến mã hóa E với hỗ trợ suppD∗(E) > 0, prob(E) ≤ 1/k.
Diễn giải này không hạn chế khả năng tiết lộ các tập phổ biến mã hóa mà không thỏa ngưỡng độ hỗ trợ minsup trong D*. Bằng trực giác, các tập phổ biến mã hóa như vậy không thú vị. Điều này sẽ là định hướng phát triển của luận văn. Vấn đề mà chúng tôi chính thức nghiên cứu là:
Nghiên cứu với một cơ sở dữ liệu đơn D, xây dựng một cơ sở dữ liệu mã hóa k-bí mật D* bằng cách sử dụng các mật mã thay thế và bổ sung thêm các giao dịch giả sao cho từ tập các mô hình mật mã thường xuyên và độ hỗ trợ của chúng trong D* được gửi tới
chủ sở hữu qua máy chủ, chủ sở hữu có thể tạo lại các mô hình thường xuyên thật sự của D và sự hỗ trợ chính xác của chúng. Ngoài ra, chúng tôi muốn giảm bớt không gian và thời gian phát sinh cho chủ sở hữu trong quá trình khai thác và các chi phí khai thác phát sinh bởi máy chủ.