posted on 2006-01-01, 00:00authored byHaowen Chan, Adrian Perrig, Dawn Song
In-network aggregation is an essential primitive for performing
queries on sensor network data. However, most aggregation algorithms assume that all intermediate nodes are trusted. In contrast,
the standard threat model in sensor network security assumes that
an attacker may control a fraction of the nodes, which may misbehave in an arbitrary (Byzantine) manner.
We present the first algorithm for provably secure hierarchical
in-network data aggregation. Our algorithm is guaranteed to detect
any manipulation of the aggregate by the adversary beyond what is
achievable through direct injection of data values at compromised
nodes. In other words, the adversary can never gain any advantage from misrepresenting intermediate aggregation computations.
Our algorithm incurs only O(∆ log2 n) node congestion, supports
arbitrary tree-based aggregator topologies and retains its resistance
against aggregation manipulation in the presence of arbitrary numbers of malicious nodes. The main algorithm is based on performing the S UM aggregation securely by first forcing the adversary to
commit to its choice of intermediate aggregation results, and then
having the sensor nodes independently verify that their contributions to the aggregate are correctly incorporated. We show how to
reduce secure MEDIAN, COUNT, and AVERAGE to this primitive.