## 4 Classification of PPDA Protocols
### Homogenous protocols
#### 4.2.1 Perturbation  
Perturbation technique is also known as data customization. In this technique, every sensor node uses encryption key and/or private or public seeds generated by randomization techniques [25, 26], in order to hide the sampled data before transmitting them to a parent node. The perturbation-based protocols include CPDA, [PERSON] _et al._'s scheme, DADPP and PHA. **CPDA:** [PERSON] _et al._ proposed the Cluster-based Private Data Aggregation (CPDA) [17] to achieve privacy-preserving data aggregation for WSNs. In the CPDA, sensor nodes are randomly grouped into clusters for creating an aggregation tree. Each cluster leverages the additive property of polynomials to calculate the desired aggregate value. At the same time, it guarantees that no individual node can know the data values of other nodes. The intermediate aggregate values in each cluster will be further aggregated on the way to the data sink along the aggregation tree. First, every sensor node in each cluster customizes its private data into polynomial form of order \(k-1\), where \(k\) is the total number of nodes in a cluster using shared (non-private) seeds and random numbers (private). Secondly, each sensor node encrypts its customized value by using a unique shared key between a sensor node and the other sensor nodes of the cluster. Thirdly, all nodes from the same cluster exchange their encrypted customized data with each other. Each sensor node has to encrypt and decrypt _O(N\({}_{c}\))_ messages, where \(N_{c}\) is the number of sensor nodes in a cluster. Each node assembles all the data including its own by using the additive property of polynomials and sends them to their respective cluster leaders. After that, the cluster leaders deduce the aggregate value by computing the inverse of an \(M\times M\) matrix where \(M\) is the number of cluster nodes. Finally, each cluster leader routes the derived sum of the cluster back towards the query server through the TAG routing tree [10]. Figure 2 shows message exchange within a cluster for the CPDA where there is a cluster leader \(A\) and two sensor nodes \(B\) and \(C\). However, since sensor nodes are resource-constrained, particularly in terms of the limited power and processing speed and the CPDA suffers from high communication and computation overheads. In addition, the CPDA can only tolerate the collusion to a certain threshold _i.e._, the number of sensor  
Figure 2: Message exchange within a cluster in the CPDA for (a) public seed broadcasting (b) customized data encryption & sending (c) assembled information broadcasting  
nodes in a cluster minus two. If the number of colluding sensor nodes exceeds the threshold, the sensor nodes may collaboratively reveal the private information of some of the others. Although the threshold can be increased by expanding the size of the clusters, this will further increase communication overhead. **[PERSON] _et al. 's_ scheme:** The privacy-preserving data aggregation scheme by [PERSON] _et al._[19] first establishes twin keys for different pairs of sensor nodes in a network. Twin key establishment is an anonymous process that prevents each node in a pair from deriving the identity of the other node with which it is sharing a twin key. Then, for each aggregation phase, it uses an anonymous liveness announcement protocol to declare the liveness of each twin key. In the end, during the aggregation phase, each node encrypts its own value by adding shadow values computed from the lively twin keys it holds. In this way, the contribution of the shadow values for each twin key will cancel out each other and the correct aggregated result is finally obtained. There are three major steps on the scheme: _local cluster formation, twin-key establishment_ and _data aggregation_. In the first step, nodes are grouped into several clusters and each cluster forms a different logical Hamiltonian circuit [27]. Each pair of neighboring nodes in the circuit shares a pair-wise key.