{'fraction_non_alphanumeric': 0.018497757847533634, 'fraction_numerical': 0.002055306427503737, 'mean_word_length': 5.282863849765258, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Polling Problem for Decentralized Social Networks. (Problème de Sondage dans les Réseaux Sociaux Décentralisés )

The recent years have witnessed the explosion of online social networks (OSNs). For instance, Facebook has more than 1.32 billion active users and 829 million daily active users on average. OSN allows participants to do anything for a variety of purposes concerning business, entertainment, world’s events and culture such as getting friendship, publishing and sharing information, exchanging documents, and expressing opinions in politics. Yet, in the existing OSNs like Facebook, all user data or computations on such platforms are stored and processed by the central authority that has the full knowledge and control over the network. This poses potential server failures and particularly severe privacy problems. To overcome these problems, OSN decentralization allows for users to keep control on their own data and perform computations in a distributed way without the existence of central server. One of the current practical, useful but sensitive topic in OSNs is the polling problem. In general, polling is the way to determine the most favourite choice amongst some options from the participants. For example, one company of mobile phone has just launched a new product and may want to ask customers whether or not its features are comfortable, and user will choose one option between “Yes” or “No”. Currently, there are some studies and solutions for this problem in centralized networks, such as FacebookPoll and Doodle. The challenge in studying this problem is to devise a decentralized polling protocol (without resorting for a central authority) such that it can perform a secure and accurate process to sum up the initial votes with the presence of dishonest users, who try to bias the outcome and disclose the votes of honest ones. Recently, Guerraoui et al. proposed polling protocols based on simple secret sharing scheme and without requiring any central authority or cryptography system. However these protocols can be deployed safely and efficiently provided that, inter alia, the social graph structure should be transformed into a ring structure-based overlay and the number of participating users is perfect square. Consequently, designing secure and efficient polling protocols regardless these constraints remains a challenging problem. In this thesis, we are interested in polling protocols based on decentralized OSNs. More precisely, we address the problem of deploying these protocols for general social graphs and how to transform these graphs in order to increase the privacy and/or accuracy properties. Our contribution is therefore twofold. As a first contribution, we propose three simple decentralized polling protocols that rely on the current state of social graphs. The first polling protocol uses synchronous communication model in which all connection delays are bounded, and the system is driven with the presence of global clock. Furthermore, to prevent user misbehaviours, we introduce verification procedures based on shortest path scheme and routing tables. The second polling algorithm is the enhanced version of the first one. It runs in the asynchronous network model where the arrival order of messages is unpredictable. Unlike the first protocol, we propose verification process without requiring the user’s knowledge of shortest path lengths. The third polling protocol is an asynchronous one that does not require any verification procedures and contains a method for efficiently broadcasting message under a family of social graphs satisfying what we call the m-broadcasting property. We show that, despite the use of richer social graph structures, the communication and spatial complexities of this protocol are close to being linear. To evaluate the correctness of these protocols, we carry out extensive experiments under the network of 1000 nodes. The experimental result demonstrates that the dishonest coalition never affects the outcome of the poll outside the theoretical bounds. As a second contribution, to securely perform these large-scale computations without requiring any central authority, current protocols use a simple secret sharing scheme, which enables users to obfuscate their inputs. Nevertheless, these protocols require the minimum degree of the social graph should not be smaller than a given threshold. This condition is not often satisfied by all social graphs. In this thesis we formalize the “adding friends” problem such that we can reuse the social graphs after some minimum structural modifications consisting in adding new friendship relations. We also devise algorithms for solving this problem in centralized and decentralized networks. We validate our solution with a performance evaluation on real-world social graphs, which shows that our protocols are accurate, and inside the theoretical bounds. Finally, the results obtained in this thesis encourage further researches of polling protocols without using some overlay structures. In future, we plan to implement our suggested polling algorithms as a plug-in over a distributed P2P social networks such as Diaspora, Friendica and Tent, and study the polling problem with the presence of Byzantine nodes. This adversary model will be stronger than the one we considered in this thesis.