Today popular centralized Online Social Networks (OSN) such as Facebook or Twitter process massive amounts of information associated with user content in their platforms. Their approach creates several threats for the privacy of users. Firstly, user data can leak to authorized (e.g., advertising) or unauthorized third parties (external entities). Secondly, centralized OSN are prone to censorship. On the other hand, future decentralized OSN (DOSN) remove the central authority for data management and so effectively such threats. However, they require careful routing to be resilient to failures, access control and data storage at the peer level. This thesis investigates privacy-preserving protocols that aid in detecting and discouraging abusive behavior in future DOSN. In such settings, less metadata is available to participants for analysis. However, to detect abuse we may need to make use of metadata that represents neighborhood knowledge, namely a social graph or network size/structure. Thus we need to provide privacy-preserving protocols that protect such metadata and are compatible with decentralized settings. We first analyze abusive behavior in Twitter, an existing centralized, subscription based OSN platform. The data model of Twitter is a publish-subscribe messaging infrastructure that allows participants publishing and subscribing to various types of notifications (e.g., news, sports). At the individual level, we conjecture that attackers may be more likely to abuse potential victims if they can address them via the OSN interface with tools as mentions (e.g., tagging) in Twitter. To verify abuse at the individual level, we start collecting messages directed to potential victims using a data mining framework we build and that programmatically crawls Twitter APIs. We managed to retrieve in the order or hundreds of thousands of tweets and metadata of millions of social relationships from Twitter. Then, we extract a number of features, namely individual measurable properties related to the dataset. To obtain abuse ground truth, we develop a light-weight web platform that provides effective and customizable crowdsourcing of label annotation for a sample of our dataset. The sample contains messages directed towards potential victims of abuse and we ask humans to label the nature of messages following a set of abuse guidelines that provide a non-binary classification choice (undecided, abusive, acceptable). Initially, we consider the problem of abuse classification in a centralized OSN (Twitter). Next, we abstract from the Twitter model and consider DOSN where locally, users only have access to a partial view of the metadata available in the network to perform abuse detection. In turn, we analyze the impact of enforcing privacy into features involving neighborhood knowledge, which requires collection and computation of social graph metadata that is not available to the user locally. In order to use these features in DOSN, we design a signed Private Set Intersection (PSI) protocol that protects participant metadata collected and computed by the PSI. In addition, we analyze the resistance of our protocol against adversaries trying to tamper with the value of the PSI features. Finally, we perform data minimization by approximating PSI features and testing supervised learning algorithms for abuse detection. Our results show that approximation of the neighborhood fingerprint that PSI features use for abuse detection is still useful and compatible with DOSN.