TL;DR
This paper introduces novel protocols for privacy-preserving range queries in tiered wireless sensor networks (WSNs) that specifically address the threat of node collusion. By employing a Bloom filter-based encoding scheme for data and queries, and a verification mechanism based on data ordering, the proposed methods ensure data privacy and result integrity while also resisting sophisticated collusion attacks.
What Problem Does This Paper Address?
Wireless Sensor Networks (WSNs) are crucial for the Internet of Things (IoT), but their widespread adoption is hindered by significant privacy concerns. Range queries, which retrieve data within a specified attribute range, are common in WSN applications like e-health. Existing privacy-preserving range query solutions for two-tiered WSNs (sensor nodes and master nodes) primarily focus on protecting data from compromised master nodes. However, they often overlook the critical threat of collusion, where sensor nodes and master nodes collaborate to compromise privacy. This paper addresses this gap by proposing protocols that are not only privacy-preserving and integrity-verifying but also robust against such collusion attacks, a problem largely unaddressed in prior work.
Methods
The core of the proposed solution lies in a novel encoding scheme using Bloom filters.
- Privacy Preservation:
- Data Encoding: Sensor nodes encode their data using a Bloom filter-based approach, creating a "BFcode." This encoding, along with encryption, hides sensitive information from master nodes.
- Query Encoding: Similarly, user queries are encoded into BFcodes, preventing master nodes from inferring the query range.
- Result Integrity Verification: A scheme is introduced to verify the correctness of query results. This involves checking the ordinal relationship among data points, allowing the sink to detect manipulated or incomplete results.
- Collusion Resistance (CPRQ Protocols): To counter collusion, the authors propose several protocols (c-CPRQ and u-CPRQ) that build upon the initial privacy-preserving range query (PRQ) protocol. The key innovation here is the use of diverse hash functions for different sensor nodes. This prevents a colluding master node from easily inferring data or queries even if it obtains the hash functions from a sensor node.
- Improvements: Two schemes are presented to enhance the protocols:
- Data Compression: Lossless compression techniques (absolute and differential 1-position compression) are applied to BFcodes to reduce communication costs.
- Multiple BFcodes: Constructing multiple BFcodes for a query range helps reduce false positives, thereby improving accuracy.
Datasets
The LUCE (Lausanne Urban Canopy Experiment) dataset was used for the experiments. This dataset comprises measurements from 97 sensor nodes collected from July 2006 to May 2007, providing real-world environmental data.
Key Insights and Ideas
- Collusion is a Major Threat: The paper highlights that existing privacy-preserving range query solutions are vulnerable to collusion attacks, which can be far more destructive than individual node compromises.
- Bloom Filters for Privacy and Integrity: Bloom filters are ingeniously adapted not only for privacy (hiding data/queries) but also for integrity verification through their probabilistic nature and efficient membership testing.
- Diverse Hash Functions for Collusion Resistance: The core idea for resisting collusion is to ensure that different sensor nodes use different sets of hash functions. This prevents a colluding adversary from easily reconstructing the original data or queries from BFcodes.
- Trade-offs in WSN Security: The paper demonstrates the inherent trade-offs in WSNs between privacy, accuracy, communication cost, and computational complexity, and proposes methods to navigate these.
Key Results
- PRQ Protocol: Achieves privacy preservation and result integrity against compromised master nodes.
- CPRQ Protocols (c-CPRQ, u-CPRQ): Successfully resist collusion attacks, a significant advancement over previous work.
- Efficiency: The proposed protocols, particularly u-CPRQ, demonstrate lower communication costs compared to existing methods like Encoding, ST-crosscheck, and SafeQ, especially under collusion scenarios.
- Accuracy: The use of multiple BFcodes in PRQ significantly reduces false positives, leading to high accuracy, comparable to SafeQ.
- Privacy: The protocols maintain strong data and query privacy, with negligible probabilities of master nodes guessing correct data or queries, especially when key lengths are sufficient and hash functions are diverse.
- Compression Benefits: Data compression schemes effectively reduce message sizes, leading to substantial savings in communication cost. Differential 1-position compression showed a higher compression ratio.
Limitations and Future Work
- False Positives in c-CPRQ: While c-CPRQ resists collusion, its relaxed membership test can lead to more false positives compared to PRQ and u-CPRQ.
- Computational Cost Growth: The computational cost for master nodes increases with the number of BFcodes used for query representation (w).
- Future Work: The authors plan to extend their research to privacy preservation for more complex queries, such as top-k and kNN queries, in two-tiered WSNs. They acknowledge that achieving accurate results for these queries without information leakage is challenging due to the reliance on global comparison information.
Summary updated