Observable Non-Sybil Quorums Construction in One-Hop Wireless Ad Hoc Networks.

D. Mónica, J. Leitão, L. Rodrigues, and C. Ribeiro.

Selected sections of this report were published in the Proceedings of the 40th IEEE/IFIP International Conference on Dependable Systems and Networks, Chicago, Illinois, USA, June, 2010.


The Sybil Attack is a serious threat to the secure and dependable operation of wireless ad hoc networks. This paper proposes an algorithm to provide each correct node in an one-hop wireless network with a quorum of non-Sybil identities from the neighbourhood. The quorums provided to different correct nodes may differ, but their intersection is composed by a majority of correct identities, with an arbitrarily close to 1 probability. Therefore, the quorums may be used for different purposes, such as voting. The algorithm is based on the combination of different resource tests, to efficiently detect (and exclude) Sybil identities.

Also available extended report (pdf)

Luís Rodrigues