1

Sybil attacks present a significant threat to many Internet systems and applications, in which a single adversary in-serts multiple colluding identities in the system to compro-mise its security and privacy. Recent work has advocated the use of social-network-based trust relationships to defend against Sybil attacks. However, most of the prior security analyses of such systems examine only the case of social net-works at a single instant in time. In practice, social network connections change over time, and attackers can also cause limited changes to the networks. In this work, we focus on the temporal dynamics of a variety of social-network-based Sybil defenses. We describe and examine the effect of novel attacks based on: (a) the attacker’s ability to modify Sybil-controlled parts of the social-network graph, (b) his abilit