Achieving O(log3n) Communication-Efficient Privacy-Preserving Range Query in Fog-Based IoT

The advance of Internet-of-Things (IoT) techniques has promoted an increasing number of organizations to explore more mission-critical solutions. However, the response latency, bandwidth usage, and reliability are still challenging issues in the traditional IoT. To tackle these challenges, the fog-based IoT has become popular and the range query is one of the most frequently used operations in fog-based IoT, where given a range query, a fog node will return the aggregated data from IoT devices to the query user. Because the fog nodes are not fully trusted, there is a desire to design a privacy-preserving range query scheme in the fog-based IoT. However, most of existing privacy-preserving range query schemes are not efficient in terms of communication overhead, especially for a large-size range. Therefore, it is still a challenging issue to design a communication-efficient range query in fog-based IoT. Aiming at this challenge, in this article, we propose a new privacy-preserving range query scheme in the fog-based IoT. Specifically, we first devise an efficient homomorphic encryption scheme for maintaining data privacy and security in a range query. Then, we present a novel range decomposition technique to compile the range query, which can transform a given range query [L, U], where 0 <= L <= U <= n - 1, into a semi-triangular structure, and enable our proposed scheme to achieve O(log(3)n) communication efficiency. The detailed security analysis shows that our proposed scheme is really privacy preserving, and the extensive performance evaluation demonstrates that our proposed scheme is efficient in terms of low communication overhead and the computational cost.