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.3 Mã hóa và giải mã
Trong phần này, chúng tôi mô tả các mô đun mã hóa/ giải mã (E/D), chịu trách nhiệm mã hóa TDB và giải mã các kết quả khai thác đến từ máy chủ. Ý tưởng chung về phương pháp mã hóa/giải mã của chúng tôi được thể hiện trong một ví dụ ở Hình 3.5.
Khách hàng (chủ sở hữu) sẽ thay thế từng hạng mục bằng một chức năng 1—1 thay thế và bổ sung thêm các giao dịch giả để sao cho cơ sở dữ liệu theo cách mà đối với mỗi hạng mục (tập phổ biến) sẽ có ít nhất k-1 các hạng mục (tập phổ biến) khác có cùng số lần xuất hiện trong cơ sở dữ liệu. Sau đó, khách hàng sẽ gửi cơ sở dữ liệu đã sửa đổi cho máy chủ. Máy chủ, sau khi nhận được dữ liệu đã sửa đổi và các yêu cầu khai thác từ khách hàng, sẽ tính toán các tập phổ biến được mã hóa và gửi chúng cho khách hàng. Khách hàng đã biết các giao dịch giả và có thể giải mã để khôi phục lại các dữ liệu thực tế và các tập phổ biến với độ hỗ trợ thực sự.
Mã hóa 3.2.3.1
Hình 3.5 Qui trình mã hóa CSDL giao dịch
Mô đun mã hóa biến đổi một cơ sở dữ liệu ban đầu D thành phiên bản thay thế D*.
Mô đun sử dụng là tham số k > 0 và bao gồm ba bước chính:
(1) Sử dụng các mật mã thay thế 1—1 cho mỗi Item đơn.
(2) Sử dụng thuật toán nhóm các Item thành k nhóm.
(3) Sử dụng phương pháp bổ sung các giao dịch giả mới để đạt được k-bí mật.
Chương trình mã hóa là biện pháp đối phó với các cuộc tấn công vào mặt hàng và tập phổ biến được trình bảy trong phần 3.2.2. Vì kẻ tấn công biết chính xác sự hỗ trợ của mỗi mặt hàng nên chúng tôi tạo ra một k-bí mật trong D*, như vậy các mặt hàng mã hóa không thể bị phát hiện dựa vào độ hỗ trợ của chúng.
Phương pháp phân nhóm k: Cho bảng độ hỗ trợ của các mặt hàng đơn, một số chiến lược có thể được áp dụng để phân chia các mặt hàng vào trong k nhóm. Chúng tôi giả định rằng bảng độ hỗ trợ của các mặt hàng được sắp xếp theo thứ tự giảm dần và các mặt hàng được mã hóa theo thứ tự e1, e2, …, en. Như đã đề cập ở phần trên, các tập phổ biến s (các giao dịch) không thể bị tiết lộ với xác suất (freqD(s)) lớn hơn 1/k. Để đạt được điều này, chúng tôi chỉ cần sử dụng phương pháp phân nhóm cho các nhóm hạng mục không được hỗ trợ trong D. Xét dữ liệu như hình 3.6, chúng ta không thể sử dụng phương pháp phân nhóm để tạo ra nhóm {e2, e4} khi hai hạng mục này xuất hiện cùng nhau trong một giao dịch trong cơ sở dữ liệu ban đầu D được thể hiện trên hình 3.5. Chúng ta gọi phương pháp phân nhóm này là phương pháp thô.
Diễn giải 3. Cho một cơ sở dữ liệu giao dịch D và một phân nhóm G chứa các hạng mục xuất hiện trong D, G được gọi là nhóm thô đối với D khi và chỉ khi, đối với bất kỳ nhóm Gi nào của G, độ hỗ trợ của nhóm bằng 0 (GisuppD(Gi) = 0).
Diễn giải trên trực tiếp cho thấy quá trình kiểm tra xem liệu một phân nhóm G đưa ra đối với một cơ sở dữ liệu giao dịch ban đầu D có là nhóm thô hay không: điều này đủ để kiểm tra xem độ hỗ trợ trong D của mỗi nhóm Gi trong G là 0. Nếu trường hợp này xảy ra, việc phân nhóm có thể được sử dụng một cách an toàn để có được sự bảo vệ bí mật tối đa được bảo đảm bởi phương pháp của chúng tôi.
Hình 3.6 Phân nhóm với k=2
Hình 3.7 Tạo độ nhiểu cho các nhóm
Hình 3.8 Bảng băm
Diễn giải 4. Cho cơ sở dữ liệu giao dịch ban đầu D và bảng độ hỗ trợ mặt hàng của D theo thứ tự giảm dần, phương pháp phân nhóm của chúng tôi gồm 2 bước:
BƯỚC 1: nhóm các hạng mục mã hóa cùng nhau vào các nhóm hạng mục k liền kề bắt đầu từ hạng mục thường xuyên nhất e1, sẽ có được các nhóm G = (G1, …, Gm)
(tức là, G1 = {e1 … ek}, G2 = {ek+1, …, e2k} …).
Trong hình 3.6 với k=2 ta có 2 nhóm.
BƯỚC 2: thay đổi các nhóm G bằng cách lặp lại các thao tác sau, cho đến khi không có nhóm các mặt hàng nào được hỗ trợ trong D:
• Chọn j nhỏ nhất j ≥ 1 sao cho suppD(Gj) > 0
• Tìm hạng mục thường xuyên nhất i’ ∈ Gj sao cho hạng mục thường xuyên nhất i của Gj chúng ta có: suppD(Gj|{i} ∪ {i} ) = 0,
• Thay đổi i bằng i’ trong các nhóm.
Đầu ra của các nhóm có thể được thể hiện như là một bảng độ nhiễu. Nó mở rộng bảng độ hỗ trợ các mặt hàng thêm một cột độ nhiễu để cho thấy, sự khác biệt giữa độ hỗ trợ của tập mặt hàng phổ biến nhất trong nhóm với độ hỗ trợ của chính mặt hàng đó (xem bảng Noise Table trong hình 3.6). Chúng ta ký hiệu độ nhiễu của mặt hàng đã mã hóa e là N(e). Cột độ nhiễu chỉ ra rằng, đối với mỗi hạng mục mã hóa e, số lần xuất hiện của e là cần thiết trong D* để mang lại cho e độ hỗ trợ tương tự như mặt hàng xuất hiện thường xuyên nhất của nhóm e’. Như vậy, bảng độ nhiễu thể hiện công cụ để tạo ra các giao dịch
ảo được bổ sung vào D để đạt được D*. Đặc biệt, tổng kích thước của các giao dịch giả cần thiết chính là tổng của tất cả các giá trị trong cột độ nhiễu trên bảng độ nhiễu. Bảng độ nhiễu cung cấp một tóm tắt ngắn gọn (sử dụng không gian O(n), trong đó n là số lượng các hạng mục) có thể được lưu trữ trong mô đun E/D để hỗ trợ cho cả việc tạo ra các giao dịch giả (mã hóa) và cả cho bước giải mã.
Ví dụ, hãy xem xét ví dụ về D trong hình 3.5 và bảng hỗ trợ hạng mục (mật mã) liên kết của nó trong bảng (a) hình 3.6. Với k=2, phương pháp nhóm sẽ tạo ra hai nhóm:
{e2, e5} và {e4, e1, e3} bảng (b) trong hình 3.6, đó là một tập thô vì không nhóm nào trong hai nhóm được coi là tập phổ biến, được hỗ trợ bởi bất kỳ giao dịch nào trong D.
Các giao dịch giả. Cho một bảng xác định độ nhiễu N(e) cần thiết cho mỗi hạng mục mật mã e, chúng ta sẽ tạo ra các giao dịch giả như sau. Đầu tiên, chúng tôi đặt các mặt hàng với độ nhiễu bằng không, tương ứng với các mặt hàng có độ phổ biến cao nhất của mỗi nhóm với các hạng mục khác, có sự cân bằng về độ hỗ trợ với độ hỗ trợ tối đa của một nhóm (N(e)=độ hỗ trợ cao nhất của nhóm trừ đi độ hỗ trợ của chính e). Thứ hai, chúng tôi sắp xếp các mặt hàng còn lại theo thứ tự giảm dần về độ nhiễu. Để e’1, …, e’m thu được thứ tự của các hạng mục (còn lại) với độ nhiễu liên kết N(e1), . . . , N(em). Các giao dịch giả sau đây được tạo ra:
• N(e’1) – N(e’2) các biểu hiện của giao dịch {e’1}
• N(e’2) – N(e’3) các biểu hiện của giao dịch {e’1, e’2}
• …
• N(e’m-1) – N(e’m) các biểu hiện của giao dịch {e’1,…, e’m-1}
• N(e’m) các biểu hiện của giao dịch {e’1, …, e’m}
Tiếp theo, chúng tôi xem xét các dòng mà các mặt hàng đã mã hóa có độ nhiễu khác không trong bảng (c) hình 3.6. Hai giao dịch giả sau đây được tạo ra: 2 biểu hiện của giao dịch {e5, e3, e1} và một biểu hiện của giao dịch {e5}. Chúng tôi nhận thấy rằng các
giao dịch giả được giới thiệu bằng phương pháp này có thể dài hơn bất kỳ giao dịch nào trong cơ sở dự liệu giao dịch D ban đầu (xem hình 3.5), khi độ dài của giao dịch tối đa lmax
trong D là 2 và có các giao dịch giả có độ dài là 3. Vì vậy, chúng tôi xem xét để rút ngắn chiều dài của các giao dịch giả bổ sung sao cho chúng phù hợp với độ dài của giao dịch trong D. Trong hình 3.5 vì D chỉ gồm các giao dịch có độ dài 1 và 2, chúng tôi sẽ chia biểu hiện giao dịch {e5, e3, e1} thành hai biểu hiện giao dịch giả {e5, e3} và 2 biểu hiện {e1}. Vì vậy, chúng tôi sẽ có hai biểu hiện {e5, e3}, 2 biểu hiện {e1} và một biểu hiện {e5}.
Để thực hiện công việc một cách hiệu quả, chúng tôi sử dụng một bảng băm được tạo ra bởi một hàm băm hoàn hảo tối thiểu. Các hàm băm hoàn hảo tối thiểu được sử dụng rộng rãi và hiệu quả được lưu trữ trong bộ nhớ và có khả năng phục hồi nhanh chóng các mặt hàng từ các dữ liệu lưu trữ. Trong chương trình của chúng tôi, các hạng mục của bảng tiếng ồn ei với N(ei)>0 là chìa khóa của hàm băm hoàn hảo tối thiểu. Cho ei, chức năng h tính toán một số nguyên trong [0, . . ., n−1], biểu thị vị trí của bảng thuật toán lưu trữ gồm ba giá trị < ei, timesi, occi > với:
• timesi thể hiện số lần giao dịch giả mạo {e1, e2, …, ei} xảy ra trong tập hợp các giao dịch giả.
• occi là số lần ei xảy ra hoàn toàn trong các giao dịch giả mạo trong tương lai sau giao dịch {e1, e2, …, ei}.
Cho một bảng độ nhiễu với các hạng mục m với độ nhiễu khác rỗng, phương pháp tiếp cận của chúng tôi tạo ra bảng băm các nhóm mặt hàng. Mục thứ i của bảng băm bao gồm hạng mục ei có timesi = N(ei)−N(ei+1), occi = ∑ j=i+1, ..., g N(ej), với g là số lượng các hạng mục trong nhóm hiện tại. Lưu ý rằng mỗi bảng băm HT thể hiện chính xác các giao dịch giả liên quan đến tất cả và một số các mặt hàng trong một nhóm các mặt hàng g≤lmax. Các bảng băm dành cho các hạng mục có độ nhiễu khác không trong bảng (c) Hình 3.6 được thể hiện trong bảng (d) Hình 3.6. Cho rằng trong ví dụ của chúng tôi,
lmax=2, chúng ta cần phân 3 hạng mục e5, e3, và e1 không nhiễu trong Hình 3.6 thành hai tập hợp {e5, e3} và {e1}, mỗi tập hợp có các giao dịch giả liên kết, được mã hóa bởi hai bảng băm. Lưu ý rằng bất cứ mô hình nào bao gồm các mặt hàng từ các bảng băm khác nhau sẽ không được đưa vào một giao dịch giả.
Cuối cùng, chúng tôi sử dụng một chức năng thuật toán thông thường (cấp độ hai) H để lập biểu đồ mỗi hạng mục cho bảng thuật toán HT bao gồm e.
Các giao dịch giả được lập ra được bổ sung vào D (khi các hạng mục được thay thế bằng các hạng mục mật mã) để tạo thành D*, và được truyền đến máy chủ. Tất cả các giao dịch giả, tức là DF=D*/D, được lưu trữ bởi mô đun ED.
Giải mã 3.2.3.2
Hình 3.9 Qui trình giải mã CSDL giao dịch
Khi khách hàng gửi một yêu cầu thực hiện khai thác dữ liệu đến máy chủ và quy định một ngưỡng hỗ trợ tối thiểu σ (minsup= σ) cụ thể, máy chủ sẽ sử dụng các tập phổ biến được tính toán từ D*. Rõ ràng, đối với mỗi tập phổ biến S và tập phổ biến mã hóa tương ứng E của nó, chúng ta có suppD(S) ≤ suppD* (E). Do đó, chương trình mã hóa của chúng tôi đảm bảo rằng tất cả các tập phổ biến thường xuyên trong D sẽ được máy chủ trả lại trong phiên bản mật mã. Nhưng các tập phổ biến trong D* chứ không phải trong D,
cũng được trả lại. Đối với mỗi mô hình mật mã E được máy chủ trả lại cùng với suppD*(E), mô đun ED sẽ phục hồi một cách không đáng kể mô hình đơn tương ứng S như sau:
suppD(S) = suppD* (E) – suppD*\D(E)
Tính toán này được mô đun ED thực hiện một cách hiệu quả bằng cách sử dụng bảng tóm tắt các giao dịch giả trong D*\D được mô tả bên trên (xem kết quả hình 3.5).
Kết chương
Trong chương 3, chúng tôi đã nghiên cứu một phương pháp mã hóa và giải mã cơ sở dữ liệu ban đầu từ bên ngoài. Các giả thiết về đối tượng tấn công cũng đã được nêu và đảm bảo rằng, dữ liệu ban đầu sau khi đã được mã hóa vẫn được bảo đảm an toàn. Các kết quả khai thác là đáng tin cậy và được giải mã một cách dễ dàng tại đơn vị chủ sở hữu dữ liệu. Phần thực nghiệm, cài đặt thuật toán mã hóa và giải mã được trình bày ở chương 4.
CHƯƠNG 4