In many applications, hosts in a peer to peer network may wish to maintain their anonymity or the privacy of their queries. In some applications, an even stronger guarantee is desirable: hosts would like to prevent others from determining whether they participate in the network at all. Darknets, or friend-to-friend networks, are one approach to preventing the discovery of hosts within a peer to peer network [1]. In such a network, hosts only form Internet connections with and directly communicate with a small set of hosts whose operators are known and trusted a priori. That is, each user only connects to her friends, trusting that her friends will not reveal her identity or existence in the network.