Nhận xét về phương pháp Sheng-Li

20 CHƯƠNG 3. PHƯƠNG PHÁP ĐỀ NGHN 3.1. Nhận xét về phương pháp Sheng-Li Bên cạnh dữ liệu cần truyền, các nút cảm ứng phải truyền thêm các dữ liệu để chống lại khả năng nút lưu trữ trả lời không đủ câu truy vấn của trạm chính. Thực vậy, giả sử nút cảm ứng thứ i có k dữ liệu phân bố vào p nhãn (tag) trong tập [T1,…,Tq] với q > p thì: (i) nút i phải truyền thêm q - p thông điệp để kiểm tra dữ liệu trong (q-p) nhãn (tag) còn lại là rỗng (ii) hơn nữa, nút i còn phải truyền thêm một số dữ liệu padding khi mã hóa. Vấn đề này làm cho nút cảm ứng tốn chi phí lớn cho truyền thông tin (chi phí truyền thường cao hơn rất nhiều chi phí tính toán) Vấn đề có thể nghiêm trọng hơn khi hệ thống có thể bị tấn công “dần dần” khi nút lưu trữ tự nó/ hoặc bị khống chế để khai thác tính thường trực của dữ liệu trên hệ thống. Với một thuật toán mã hóa khối, kích thước bản mã thường bằng với kích thước bản rõ. Như vậy nếu kích thước bản mã lớn, có thể suy ra kích thước bản rõ lớn, đồng nghĩa với số lượng dữ liệu nhiều. Bên cạnh đó, kích thước giá trị sau khi băm có số bit cố định, nên hoàn toàn xác định được tag nào không có dữ liệu. Hơn nữa, các tag là cố định nên có thể dò ra gần đúng biên của các đoạn dữ liệu (bucket) ứng với các tag. Như vậy, do dữ liệu thường trực trên hệ thống, theo thời gian hoàn toàn có thể suy ra hoặc xấp xỉ được phân phối của dữ liệu thật sự. Khi biết được phân phối, các giá trị min, max, trung bình, phương sai,… hoàn toàn có thể xấp xỉ được, nhất là đối với phân phối đều. Ngoài ra, nút lưu trữ có thể đóng vai trò người dùng, thực hiện câu truy vấn và gửi đến trạm chính (như vậy nút lưu trữ có bản rõ). Trạm chính sẽ gửi yêu cầu đến nút lưu trữ và nút lưu trữ trả về tập các dữ liệu và nhãn tương ứng (như vậy nút lưu trữ có bản mã). Khi đó, nút lưu trữ có thể thực hiện tấn công khi biết bản rõ và bản mã. Vì vậy phương pháp Sheng-Li rủi ro cao với tấn công khi biết bản rõ và bản mã, mà thực ra là tấn công tự điển. 21 Bên cạnh đó, một đặc điểm khác của phương pháp Sheng-Li là: nếu cùng một giá trị xuất hiện nhiều lần, thì các giá trị đó được xem như là các giá trị phân biệt. Từ các hạn chế trên của phương pháp Sheng-Li, chúng tôi muốn đề nghị một hướng cải tiến phương pháp nhằm chống lại tấn công bản rõ/ bản mã, đồng thời đưa ra một hướng tiếp cận khác có thể khắc phục hai hạn chế trên (tuy nhiên hướng tiếp cận này cũng có một số hạn chế nhất định). 3.2. Hướng cải tiến phương pháp Sheng-Li 3.2.1. Mô tả phương pháp đề xuất Trong phương pháp Sheng-Li, các nút cảm ứng trực tiếp mã hóa dữ liệu và gửi bản mã của dữ liệu đến các nút lưu trữ, nên trong trường hợp nút lưu trữ bị khống chế, nó có thể khai thác được các giá trị bản mã đang được lưu thường trực trên nó. Vì vậy, chúng tôi muốn thay đổi giá trị gửi đi từ nút cảm ứng. Giá trị gửi đi sẽ là một giá trị có thể bao gồm trong đó thông tin về giá trị dữ liệu thật sự, và số lần xuất hiện dữ liệu. Hướng tiếp cận của chúng tôi là áp dụng định lý số dư Trung Hoa để tìm ra giá trị đó. Giả sử tại thời điểm t, nút cảm ứng thứ i cần gửi m giá trị sau {d1,d2,…,dm}. Giá trị dj xuất hiện fj lần trong tập {d1,d2,…,dm}. Khi đó, áp dụng định lý số dư Trung Hoa để giải hệ phương trình đồng dư sau có thể tìm được giá trị xj đại diện cho cặp {dj, fj} xj = dj mod mi,1 xj = fj mod mi,2 với mi,1, mi,2 là hai số nguyên tố cùng nhau (điều kiện để hệ có nghiệm duy nhất) chia sẻ giữa nút thứ i và trạm chính. Gọi Di là miền giá trị của dữ liệu ghi nhận ở nút cảm ứng thứ i. Khi đó, để đảm bảo cho hệ có nghiệm với mọi dj thuộc miền Di và với mọi fj, mi,1 và mi,2 cần lớn hơn mọi dj và mọi fj. Nói cách khác mi,1, mi,2 ≥ max(Di) và mi,1, mi,2 ≥ m (m là số lượng dữ liệu cần gửi tại một thời điểm). 22 Các giá trị xj chính là các giá trị bao gồm trong nó thông tin về dữ liệu gốc (dj) và tần số xuất hiện (fj). Nút cảm ứng sau đó thực hiện mã hóa với khóa chia sẻ ki,t (hoặc có thể không cần mã hóa) các giá trị xj và gửi đi kèm với các nhãn (tag). Lưu ý là cách gán nhãn vẫn theo phương pháp Sheng-Li, nghĩa là gán nhãn dựa trên dữ liệu gốc ban đầu. Khi trạm chính nhận được kết quả truy vấn, trạm chính hoàn toàn có thể khôi phục lại các giá trị dj và tần số fj từ các xj, vì mi,1, mi,2 được chia sẻ giữa trạm chính và nút cảm ứng i với mọi i. q Ví dụ: Giả sử D = {1,…,30} được phân hoạch thành các vùng rời nhau (hội các vùng này chính xác là D) [05] và các tag tương ứng như sau: T1 T2 T3 T4 T5 [1, 5] [6, 15] [16, 23] [24, 28] [28, 30] Nút cảm ứng i cần gửi tập dữ liệu gồm 9 giá trị (m=9): {3, 3, 7, 1, 7, 7, 28, 29, 28} Chọn 2 số nguyên tố cùng nhau m1, m2 (nhằm thỏa điều kiện để áp dụng định lý số dư Trung Hoa) với m1, m2 ≥ max(D, m) = max{[1,30],9} = 30. Ví dụ chọn m1 = 31, m2 = 33 Các giá trị 3, 1 nằm trong khoảng [1,5] nên gán nhãn T1, 7 nằm trong [6,15] nên gán nhãn T2, 28 và 29 nằm trong [28,30] nên gán nhãn T5. Theo phương pháp Sheng- Li, dữ liệu cần gửi đi là: t, {T1, {3,3,1}}, {T2, {7,7,7}}, {T3, num(i||3||t)}, {T4, num(i||4||t)}, {T5, {28,28,29}} 23 Các giá trị đại diện xj được tính như sau: Giá trị 3 1 7 28 29 Số lần xuất hiện 2 1 3 2 1 Nhãn T1 T1 T2 T5 T5 Giá trị xj Giải hệ x=3 mod m1 x=2 mod m2 x= x1 Giải hệ x=1 mod m1 x=1 mod m2 x= x2 Giải hệ x=7 mod m1 x=3 mod m2 x= x3 Giải hệ x=28 mod m1 x=2 mod m2 x = x4 Giải hệ x=29 mod m1 x=1 mod m2 x= x5 Dữ liệu thực sự được mã hóa và gửi đi đến nút lưu trữ là các giá trị đại diện: t, {T1, {x1, x2}}, {T2, {x3}}, {T3, num(i||3||t)}, {T4, num(i||4||t)}, {T5, {x4, x5}} Dữ liệu x1 x2 x3 x4 x5 Nhãn (tag) T1 T1 T2 T5 T5 24 3.2.2. Thuật toán Bảng 3-1 Thuật toán cải tiến CRT Thuật toán cải tiến CRT Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng m = số dữ liệu gửi mỗi lần Tập bucket và các tag tương ứng. {B1, T1} … {Bk, Tk} m1, m2: hai số nguyên tố cùng nhau, m1, m2 > max(D), m1, m2 > m m1 -1 mod m2, m2-1 mod m1 Output Các giá trị đại diện và nhãn tương ứng. Thực hiện For x thuộc X f(x) = tan so cua x p = xm2m2 -1 mod m1 + fm1m1 -1 mod m2 (mod m1 m2) Gan nhan cho x End for 25 3.2.3. Phân tích phương pháp đề xuất Sau đây là các nhận xét của chúng tôi về các khác biệt trong hướng tiếp cận dựa vào định lý số dư Trung Hoa (CRT) so với phương pháp Sheng-Li. Để cho dễ theo dõi, chúng tôi tạm gọi tên các giá trị xj được tìm dựa vào định lý số dư Trung Hoa như trên là ‘giá trị đại diện’, và gọi hướng tiếp cận này là hướng tiếp cận CRT. Thứ nhất, theo hướng tiếp cận này, các giá trị được lưu giữ thường trực trên các nút lưu trữ là bản mã của các giá trị đại diện hoặc chính các giá trị đại diện (trường hợp không thực hiện mã hóa). Đồng thời, giá trị đại diện phụ thuộc vào dữ liệu gốc và tần số xuất hiện nên nếu cùng một giá trị, nhưng tại thời điểm t1 dữ liệu có số lần xuất hiện khác với thời điểm t2, thì giá trị đại diện tại thời điểm t1 cũng khác với thời điểm t2. Thứ hai, mỗi giá trị đại diện đã bao gồm thông tin về dữ liệu và tần số xuất hiện dữ liệu đó. Nghĩa là nếu một dữ liệu xuất hiện nhiều lần, dữ liệu đó vẫn chỉ được đặc trưng bởi một giá trị đại diện duy nhất. Như vậy, các giá trị giống nhau được xem như là một giá trị duy nhất (phương pháp Sheng-Li xem các giá trị này như các giá trị phân biệt) và chỉ gửi đi một lần. Nhờ đó, trong trường hợp dữ liệu không rải đều mà tập trung vào một số giá trị, chi phí truyền tải được tiết kiệm đáng kể. Ngược lại, nếu dữ liệu rải đều thì tùy thuộc vào tần số của từng giá trị dữ liệu. Nếu tần số cao thì chi phí giảm so với phương pháp Sheng-Li. Nếu tần số thấp thì chi phí có thể cao hơn. Thông thường, dữ liệu phân phối chuNn, dữ liệu thường tập trung vào các giá trị nằm trong vùng gần đỉnh (vùng có xác suất cao), nên cách này thường có thể giúp cải tiến chi phí đường truyền. Ngoài ra, các ứng dụng mà vấn đề thời gian thực là không quan trong, có thể chủ động kéo dài khoảng thời gian định kỳ (epoch) ra nhằm tích lũy dữ liệu nhiều hơn trước khi gửi đi. Khi đó thì các giá trị dữ liệu có khả năng có tần số xuất hiện cao nên chi phí truyền tải sẽ giảm. Đồng thời, số lần truyền tải giảm (do khoảng thời gian định kỳ tăng) nên chi phí cũng được giảm. Cụ thể, chi phí truyền tải dữ liệu có thể ước lượng như sau: Nếu mỗi giá trị dj thuộc D được biểu diễn bởi b byte thì m1, m2 cần (b+1) byte để biểu diễn, vì m1, m2 ≥ max(D). Giá trị đại diện xj thuộc Zm1×m2 nên 26 mỗi giá trị xj cần 2(b+1) byte. Do đó, nếu tập dữ liệu cần gửi là tập {d1, d2,.., dk} giá trị phân biệt với tần số xuất hiện tương ứng là {f1, f2, …, fk} (lưu ý là f1 + f2 + … + fk = m = số dữ liệu gửi mỗi thời điểm) thì số byte cần để biểu diễn cho k giá trị đại diện tương ứng là 2×k×(b+1) trong khi số byte biểu diễn tập dữ liệu gốc là m×b. Rõ ràng nếu dữ liệu cần gửi chỉ tập trung ở một số giá trị, k sẽ nhỏ hơn hẳn m, khi đó 2×k×(b+1) sẽ nhỏ hơn hẳn m×b. Cuối cùng, tuy có khả năng giảm chi phí truyền tải, hướng tiếp cận này cần tốn chi phí thực hiện giải hệ phương trình đồng dư (gồm hai phương trình) cho mỗi giá trị dữ liệu. Tuy nhiên, giá trị mi,1, mi,2 (ứng với mỗi nút i) là biết trước nên ta có thể lưu giữ luôn các giá trị mi,1-1, m i,2-1 và không cần tính lại mỗi lần giải hệ đồng dư. Khi đó, giả sử mỗi thời điểm t, nút cảm ứng i gửi đi k giá trị thì chi phí để giải các hệ phương trình đồng dư tại nút đó là O(k). Ngoài các khác biệt trên, hướng tiếp cận CRT còn giữ lại các hạn chế khác của phương pháp Sheng-Li, do đó chưa giải quyết được trọn vẹn các tấn công dựa vào tính thường trực của dữ liệu trên nút lưu trữ. Chính vì vậy, trong trường hợp kích thước miền dữ liệu nhỏ, chúng tôi đưa ra một hướng tiếp cận khác, tạm gọi là phương pháp Histogram, có thể tránh được tấn công khai thác vào tính thường trực của dữ liệu. 3.3. Phương pháp Histogram 3.3.1. Mô tả phương pháp Histogram Trong phương pháp Sheng-Li, sau mỗi khoảng thời gian cố định (epoch), nút cảm ứng gửi dữ liệu đã mã hóa, đồng thời gửi các con số định danh (encoding-number) cho các đoạn giá trị (bucket) không có dữ liệu. Biên của các đoạn dữ liệu (bucket) là bí mật. Tuy nhiên, theo thời gian, nút lưu trữ bị khống chế có khả năng dò ra được các biên đó. Vì vậy, một hướng tiếp cận khác, thay vì giấu dữ liệu (bằng mã hóa) và biên 27 của các bucket, chúng tôi công khai miền giá trị dữ liệu, nhưng giấu tần số xuất hiện của từng giá trị. Một giá trị có thể không xuất hiện, xuất hiện một lần, hai lần,… Nói cách khác, trong hướng tiếp cận này, nút cảm ứng sẽ gửi histogram của dữ liệu đi. Để đảm bảo tính bí mật của histogram, chúng tôi sử dụng các giá trị ngẫu nhiên để làm biến đổi histogram. Giá trị ngẫu nhiên được sinh ra bởi hàm băm với tham số thay đổi theo thời gian. Gọi Di là miền rời rạc các giá trị của dữ liệu có khả năng ghi nhận ở nút cảm ứng i. Không mất tính tổng quát, giả sử Di = {1,…,n}. Tại thời điểm t, nút i cần gửi {d1,…,dk} với tần số xuất hiện tương ứng là {f1,…,fk}. Gọi x là giá trị thuộc Di, f(x) là tần số xuất hiện của x trong tập dữ liệu cần gửi ở nút i. h(x) = hash(x||ki,t) nếu x không thuộc {d1,…,dk} h(x) = f(x) + hash(x||ki,t) nếu x thuộc {d1,…,dk}. Trong đó, f(x) là một trong các giá trị thuộc {f1,…,fk} (ký hiệu || là phép kết nối) Có thể gom hai công thức trên thành: h(x) = f(x) + hash(x||ki,t) với f(x) là số lần x xuất hiện trong tập dữ liệu cần gửi đi {d1,…,dk} h(x) được tính với mọi giá trị x thuộc Di. Nút cảm ứng sẽ gửi tất cả các giá trị h(x) này đến nút lưu trữ. q Ví dụ: Với D = {1,…,5}, m = 6. Tập dữ liệu cần gửi là {4, 2, 3, 4, 3, 4}, tương ứng với histogram như sau: 28 Hình 3-1 Ví dụ - Histogram của dữ liệu ban đầu Các giá trị h(x) được tính như sau: h(x) = f(x) + hash(x||ki,t) Giả sử các giá trị hash đã được tính rồi và có giá trị như trong bảng. 1 2 3 4 5 hash(x||ki,t) 4 0 3 2 1 f(x) 0 1 2 3 0 h(x) 4 1 5 5 1 Nút cảm ứng sẽ gửi tập dữ liệu {4,1,5,5,1} đến nút lưu trữ. Histogram của dữ liệu sau khi biến đổi như sau: Hình 3-2 Ví dụ - Histogram của dữ liệu sau khi biến đổi 29 3.3.2. Thuật toán Sau đây là thuật toán theo phương pháp histogram. Thuật toán này nhận các giá trị đầu vào là dữ liệu cần gửi từ một nút cảm ứng đến nút lưu trữ, sau đó thực hiện tính histogram và biến đổi histogram. Kết quả đầu ra là dữ liệu sẽ được gửi đi. Bảng 3-2 Thuật toán histogram-1 Thuật toán histogram - 1 Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng Output Histogram đã được biến đổi {h(d)} = { h(d) = giá trị tần số của d sau khi bị biến đổi } với mọi d thuộc D. Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for For x thuộc X h(x) = h(x) + 1 ; End for Sau đây là hai biến thể của thuật toán Histogram, giúp bảo toàn tính toàn vẹn dữ liệu trong trường hợp nút cảm ứng bị khống chế. 30 Bảng 3-3 Thuật toán histogram-2 Thuật toán histogram - 2 Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng Output Histogram đã được biến đổi: {h(d)} = { h(d) = giá trị tần số sau khi bị biến đổi } với mọi d thuộc D Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for For x thuộc X h(x) = h(x) + (1 + hash(x||ki,t)); End for 31 Bảng 3-4 Thuật toán histogram-3 Thuật toán histogram - 3 Input D = miền giá trị của dữ liệu X = tập dữ liệu cần gửi của nút cảm ứng Output Histogram đã được biến đổi: {h(d)} = { h(d) = giá trị tần số của d sau khi bị làm nhiễu } với mọi d thuộc D Thực hiện For d thuộc D h(d) = hash(d||ki,t); End for For x thuộc X h(x) = h(x) + 1 ; End for For x thuộc X h(x) = Encki,t(h(x)); End for 3.3.3. Phân tích phương pháp Histogram Sau đây là một số đánh giá của chúng tôi về hướng tiếp cận Histogram. Kết quả trả về cho câu truy vấn khoảng trong phương pháp Sheng-Li là kết quả gần đúng, vì đơn vị nhỏ nhất được trạm chính sử dụng để truy vấn là các tag (ứng với các bucket). Sau khi nhận kết quả trả về từ nút lưu trữ, trạm chính mới thực hiện giải mã dữ liệu để loại bỏ các giá trị thừa. Còn trong phương pháp Histogram, đơn vị nhỏ 32 nhất là các giá trị, nên kết quả truy vấn trả về là kết quả chính xác. Trạm chính chỉ thực hiện biến đổi để đưa về dữ liệu gốc trước khi gửi kết quả cho người dùng. q Ví dụ: Nếu trạm chính cần truy vấn khoảng [3,5] thì các nút lưu trữ sẽ trả về chính xác các giá trị {h(3), h(4), h(5)} Phương pháp Sheng-Li xem các giá trị trùng nhau như các giá trị phân biệt. Trong khi đó, với mỗi giá trị trùng nhau, phương pháp Histogram chỉ cần tăng tần số xuất hiện của giá trị đó lên, cùng với giá trị băm của nó. Vì vậy, tương tự như trong phần nhận xét phương pháp CRT, tính chất này giúp cải tiến chi phí truyền tải. Sau mỗi khoảng thời gian cố định, nút cảm ứng phải gửi toàn bộ histogram đến nút lưu trữ. Nghĩa là ngay cả với giá trị x không có dữ liệu, nút cảm ứng cũng phải gửi giá trị h(x) của nó đi. Còn phương pháp Sheng-Li, mặc dù cũng phải gửi một con số định danh cho các bucket không chứa dữ liệu, nhưng số lượng bucket nhỏ hơn so với số lượng giá trị thực sự, nên chi phí truyền tải sẽ nhỏ hơn. Vì vậy, phương pháp Histogram chỉ thích hợp với lượng dữ liệu nhỏ và số lần truyền thông tin ít, nhưng mỗi lần truyền nhiều dữ liệu cùng lúc. Phương pháp Sheng-Li chủ yếu hỗ trợ câu truy vấn dạng khoảng. Tiếp cận dựa vào histogram cũng có thể trả lời câu truy vấn dạng khoảng nhưng đồng thời cũng hỗ trợ truy vấn count, sum, average. Trạm chính có thể yêu cầu tính tổng toàn bộ các dữ liệu, hoặc chỉ tính tổng các giá trị trong một khoảng giá trị nào đó. Đối với câu truy vấn count, trạm chính khi nhận được kết quả trả về, chỉ cần trừ đi tổng các giá trị hash(x||ki,t) (trạm chính biết được ki,t nên hoàn toàn có thể tính được giá trị băm). Đối với câu truy vấn sum, đầu tiên cần tính các giá trị s(x) = h(x) – hash(x||ki,t) với mọi x, sau đó chỉ cần cộng các giá trị s(x) lại với nhau. Có thể thực hiện mã hóa các giá trị h(x) trước khi gửi đi, nhằm chống lại tấn công vào tính toàn vẹn của giá trị h(x) [ 33 Bảng 3-4 Thuật toán histogram-3]. Một cách khác cũng giúp chống lại tấn công vào tính toàn vẹn của h(x) là thay vì sử dụng công thức tính h(x) như trên, có thể áp dụng công thức sau: h(x) = f(x)×(1+ hash(x||ki,t)) + hash(x||ki,t) [ 34 Bảng 3-3 Thuật toán histogram-2]. Giá trị hash(x||ki,t) được cộng dồn phía sau nhằm tránh trường hợp nếu không có dữ liệu, h(x) = 0 thì sẽ dễ dàng biết được. Theo công thức đó, f(x) = (h(x) - hash(x||ki,t))÷(1+hash(x||ki,t)), nên khi trạm chính nhận được h(x), nếu như (h(x) - hash(x||ki,t)) không chia hết cho (1+ h(x) - hash(x||ki,t)), có thể suy ra giá trị h(x) không toàn vẹn. Mặc dù hạn chế bởi phương pháp Histogram chỉ thích hợp với lượng dữ liệu nhỏ, và số lần truyền thông tin ít, nhưng mỗi lần truyền nhiều dữ liệu cùng lúc, nhưng trên thực tế, trong nhiều ứng dụng các giá trị do nút cảm ứng ghi nhận cũng có miền biến thiên không lớn, không không yêu cầu tính thời gian thực cao (ví dụ: nhiệt độ, chỉ số nước). Trong trường hợp lượng dữ liệu lớn, hoặc ứng dụng yêu cầu thời gian thực, hoặc mỗi lần truyền các dữ liệu phân bố rộng, không tập trung vào một số giá trị, phương pháp Histogram bộc lộ nhiều hạn chế về chi phí truyền tải. Hướng tiếp cận sau đây cũng dựa trên histogram nhưng thông tin truyền đi được giảm kích thước (nên tạm thời chúng tôi gọi là phương pháp Nén Histogram), làm giảm đáng kể chi phí truyền tải. Tuy nhiên, chúng tôi chỉ mới trình bày phương pháp này như là một hướng phát triển trong tương lai, vì hiện tại vẫn còn tồn tại một số vấn đề mà chúng tôi chưa giải quyết được trọn vẹn. 35 3.4. Phương pháp Nén Histogram 3.4.1. Mô tả phương pháp Nén Histogram Giả sử miền giá trị dữ liệu ở tất cả các nút cảm ứng đều như nhau (giả thiết này cũng phù hợp với thực tế vì các nút cảm ứng thường được gắn trong một khu vực hoặc nhiều khu vực để đo cùng một đại lượng quan tâm, chẳng hạn nhiệt độ. Và miền giá trị của đại lượng đó ở các khu vực là hoàn toàn xác định). Không mất tính tổng quát, giả sử miền giá trị dữ liệu là D = {1,2,…,n}, số lượng nút cảm ứng cùng gửi dữ liệu đến nút lưu trữ là l, lần lượt có các định danh là {1,…,l} Phương pháp này sử dụng các đa thức để nén histogram cần gửi đi. Số biến của đa thức bằng lực lượng của miền giá trị dữ liệu (|D| = n). Gọi k là số lượng đa thức sử dụng (k ≤ n), và x = (x1,x2,…,xn) là vec-tơ n thành phần. P1 (x) = a11x1 + a12x2 + … + a1nxn P2 (x) = a21x1 + a22x2 + … + a2nxn … Pk (x) = ak1x1 + ak2x2 + … + aknxn Với bộ hệ số a11 a12 … a1n a21 a22 … a2n … ak1 ak2 … akn trên là ta có thể biểu diễn lại k đa thức gốc. Bộ hệ số này sẽ được chia sẻ giữa các nút cảm ứng và trạm chính. 36 Ký hiệu vec-tơ n thành phần hi = {hi1, hi2, …, hin} là histogram của dữ liệu nút cảm ứng i muốn gửi tới (hij là tần số xuất hiện của giá trị j tại nút i, với 1≤ j ≤ n). Pi1 là giá trị đa thức P1 khi thế giá trị histogram của nút i vào. Pi1 (hi) = a11hi1 + a12hi2 + … + a1nhin … Pik (hi) = ak1hi1 + ak2hi2 + … + aknhin Với hi là vec-tơ n thành phần. Nút cảm ứng i sẽ tính giá trị các đa thức, và gửi đi tập giá trị này {Pi1,…,Pik} đến nút lưu trữ. Khi trạm chính gửi câu truy vấn dữ liệu tại thời điểm t (truy vấn khoảng giá trị, truy vấn count, average hay sum) , nút lưu trữ cộng các giá trị Pi1 lại với nhau (với mọi i), cộng các giá trị Pi2 lại với nhau, …, cộng các giá trị Pik lại với nhau. Ký hiệu P’1,P’2,…,P’n là kết quả cộng dồn. Sau đó nút lưu trữ gửi tập dữ liệu { P’1,P’2,…,P’n} trả về cho trạm chính. Rõ ràng: P’1 =∑Pi1 = a11∑hi1 + a12∑hi2 …+ a1n∑hin = a11h’1 + a12h’2 + … + a1nh’n= P1(h’) … P’ k = ∑Pik =ak1∑hi1 + ak2∑hi2 …+ akn∑hin = ak1h’1 + ak2h’2 + … + aknh’n = Pk(h’) với h’ = (h’1,h’2,…,h’n) là vec-tơ n thành phần và h’1 = ∑h