The iTrust system is a decentralized and distributed information publication, search and retrieval system, whose objective is to prevent censorship and filtering of information accessed over the Internet. In iTrust, metadata describing information are randomly distributed to multiple participating nodes. Similarly, requests containing keywords are randomly distributed to multiple participating nodes. If a participating node receives a request and the keywords in the request match the metadata it holds, the participating node sends the URL for the information to the requesting node. The requesting node then can retrieve the information from the source node. In this paper, we present the iTrust messaging and membership protocols. We establish lower bounds for the probabilities of a match if all of the participating nodes are operational and if a proportion of the participating nodes are non-operational or subverted. We provide probabilistic results for n participating nodes, where the metadata and the requests are distributed to a multiple of the square root of n nodes. These results show that distribution of the metadata and the requests to relatively few nodes suffices to achieve a high probability of a match, even if some of the nodes are non-operational or subverted.