Computer Science Department
School of Computer Science, Carnegie Mellon University


Authenticated Communication and Computation in
Known-Topology Networks with a Trusted Authority

Haowen Chan

September 2009

Ph.D. Thesis


Keywords: Secure aggregation, sensor networks, data aggregation, authenticated communication, known topology networks

We show that two distinguishing properties of sensor networks, i.e., the presence of a trusted base station, and the pre-knowledge of the fixed network topology, can yield security protocols that are both communication-efficient and highly general. We show new protocols for broadcast authentication, credential dissemination and node-to-node signatures. For securing in-network distributed computations, we show an algorithm for securely computing the sum of sensor readings in the network, which we can generalize to tree computations for any combination of continuous real-valued functions. Each of these primitives involves per-node communication costs that scale logarithmically with the number of nodes in the network, do not require public key cryptography, and are secure against arbitrary coalitions of malicious nodes. The broadcast authentication scheme achieves better properties with fewer assumptions than existing work, and the other new protocols have no known previous approach that do not require either expensive network-wide unicast or public key cryptography. 150 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by