A registration of identities is necessary in a wide array of systems, from online forums to smart environments. While pseudonyms are, in most cases, sufficient, mechanisms must be put in place to prevent malicious adversaries from registering great numbers of sybil identities. Preventing such sybil attacks becomes an especially significant challenge when the existence of a trusted party cannot be assumed. Several countermeasures against sybil attacks on decentralized systems have been proposed that are based on leveraging information from the social graph between participating users. While promising, existing solutions typically require knowledge of the complete social graph, which is a privacy issue, or are tailored towards specific applications like distributed hash tables. In this paper, we propose an approach for registering general-purpose pseudonyms in a completely decentralized manner while keeping social relationships private. Joining users collect confirmations from a fraction of already registered users while being aware only of their own neighbors in the social graph. Using the presented SybilHedge algorithm, sybil attackers are limited in the number of confirmations they can collect. We present an evaluation of the algorithm and discuss its practical application.