In this paper, we propose two efficient and privacy-preserving data aggregation protocols for WSNs: PASKOS (Privacy preserving based on Anonymously Shared Keys and Omniscient Sink) and PASKIS (Privacy preserving based on Anonymously Shared Keys and Ignorant Sink) - requiring low overhead. Both protocols guarantee privacy preservation and a high data-loss resilience. In particular, PASKOS effectively protects the privacy of any node against other nodes, by requiring O(log N) communication cost in the worst case and O(1) on average, and O(1) as for memory and computation. PASKIS can even protect a node's privacy against a compromised sink, requiring only O(1) overhead as for computation, communication, and memory; however, these gains in efficiency are traded-off with a (slightly) decrease in the assured level of privacy. A thorough analysis and extensive simulations demonstrate the superior performance of our protocols against existing solutions in terms of privacy-preserving effectiveness, efficiency, and accuracy of computed aggregation. © 2011 The Author(s).