Fault tolerant and secure distributed data storage systems typically require that only up to a threshold of storage nodes can ever be compromised or fail. In proactively-secure systems, this requirement is modified to hold only in a time interval (also called epoch), resulting in increased security. An attacker or adversary could compromise distinct sets of nodes in any two time intervals. This attack model is also called the mobile adversary model. Proactively-secure systems require all nodes to "refresh" themselves periodically to a clean state to maintain the availability, integrity, and confidentiality properties of the data storage service. This dissertation investigates the design of a proactively-secure distributed data storage system. Data can be stored at storage servers using encoding schemes called secret sharing, or encryption-with-replication. The primary challenge is that the protocols that the servers run periodically to maintain integrity and confidentiality must scale with large amounts of stored data. Determining how much data can be proactively-secured in practical settings is an important objective of this dissertation. The protocol for maintain the confidentiality of stored data is developed in the context of data storage using secret sharing. We propose a new technique called the GridSharing framework that uses a combination of XOR secret sharing and replication for storing data efficiently. We experimentally show that the algorithm can secure several hundred GBs of data. We give distributed protocols run periodically by the servers for maintaining the integrity of replicated data under the mobile adversary model. This protocol is integrated into a document repository to make it proactively-secure. The proactively-secure document repository is implemented and evaluated on the Emulab cluster (http://www.emulab.net). The experimental evaluation shows that several 100 GBs of data can be proactively-secured. This dissertation also includes work on fault and intrusion detection - a necessary component in any secure system. We give a novel Byzantine-fault detection algorithm for quorum systems, and experimentally evaluate its performance using simulations and by deploying it in the AgileFS distributed file system.

This thesis describes methods of secret communication based on latin squares and their close relative, quasigroups. Different types of cryptosystems are described, including ciphers, public-key cryptosystems, and cryptographic hash functions. There is also a chapter devoted to different secret sharing schemes based on latin squares. The primary objective is to present previously described cryptosystems and secret sharing schemes in a more accessible manner, but this text also defines two new ciphers based on isotopic latin squares and reconstructs a lost proof related to row-latin squares. / Denna uppsats beskriver kryptosystem och metoder för hemlighetsdelning baserade på latinska kvadrater och det närliggande konceptet kvasigrupper. Olika sorters chiffer, både symmetriska och asymmetriska, behandlas. Dessutom finns ett kapitel tillägnat kryptografiska hashfunktioner och ett tillägnat metoder för hemlighetsdelning. Huvudsyftet är att beskriva redan existerande metoder för hemlig kommunikation på ett mer lättillgängligt sätt och med nya exempel, men dessutom återskapas ett, till synes, förlorat bevis relaterat till rad-latinska kvadrater samt beskrivs två nya chiffer baserade på isotopa latinska kvadrater.

Secret sharing is critical to most applications making use of security and remains one of the most challenging research areas in modern cryptography. In this thesis, we propose a novel efficient multi-secret sharing scheme based on the Chinese remainder theorem (CRT) with two verification methods, while the previous works are mostly based on the Lagrange polynomial. Key management schemes play an important role in communication security in Wireless Sensor Networks (WSNs). While the previous works mainly targeting on two different types of WSNs: distributed and hieratical, in this thesis, we propose our flexible WSN key management scheme, which is based on (n,t,n) multi-secret sharing technique, to provide a key management solution for heterogeneous architecture. The powerful key managers are responsible for most of the communicational and computational workload. They can provide Peer-to-Peer pair-wise keys for a pair of sensors to establish a secure communication session, and in the same time, they can also form communication clusters as cluster heads according to different application requirements. Internet of Things (IoT) becomes more and more popular and practical in recent years. Considering the diversity of the devices and the application scenarios, it is extremely hard to couple two devices or sub-networks with different communication and computation resources. In this thesis, we propose novel key agreement schemes based on (n,t,n) multi-secret sharing techniques for IoT in order to achieve light weighted key exchange while using Host Identity Protocol (HIP). We refer the new schemes as HIP-MEXs with different underlying multi-secret sharing techniques. We analyzed the computational and communication costs of the extremely resource constrained device which is referred to as Initiator, and CRT based HIP-MEX successfully outsource the heavy workload to the proxy, which are considered more powerful, when establishing new secret key.

La cryptographie a été un facteur clé pour permettre la vente de services et du commerce par Internet. Le cloud computing a amplifié cette révolution et est devenu un service très demandé grâce à ses avantages comme : puissance de calcul importante, services à bas coûts, rendement, évolutivité, accessibilité et disponibilité. Parallèlement à la hausse de nouveaux business, des protocoles pour des calculs sécurisés ont aussi émergé. Le but de cette thèse est de contribuer à la sécurité des protocoles d’Internet existants en fournissant une analyse de la source aléatoire de ces protocoles et en introduisant des protocoles mieux adaptés pour les environnements des cloud computing. Nous proposons de nouvelles constructions en améliorant l'efficacité des solutions actuelles afin de les rendre plus accessibles et pratiques. Nous fournissons une analyse de sécurité détaillée pour chaque schéma avec des hypothèses raisonnables. Nous étudions la sécurité du cloud computing à différents niveaux. D'une part, nous formalisons un cadre pour analyser quelques-uns des générateurs de nombres pseudo-aléatoires populaires à ce jour qui sont utilisés dans presque chaque application cryptographique. D'autre part, nous proposons deux approches efficaces pour des calculs en cloud. Le premier permet à un utilisateur de partager publiquement son secret de haute entropie avec des serveurs différents pour plus tard le récupérer par interaction avec certains de ces serveurs en utilisant seulement son mot de passe et sans données authentifiées. Le second permet à un client d'externaliser à un serveur une base de données en toute sécurité, qui peut être recherchée et modifiée ultérieurement. / Cryptography has been a key factor in enabling services and products trading over the Internet. Cloud computing has expanded this revolution and it has become a highly demanded service or utility due to the advantages of high computing power, cheap cost of services, high performance, scalability, accessibility as well as availability. Along with the rise of new businesses, protocols for secure computation have as well emerged. The goal of this thesis is to contribute in the direction of securing existing Internet protocols by providing an analysis of the sources of randomness of these protocols and to introduce better protocols for cloud computing environments. We propose new constructions, improving the efficiency of current solutions in order to make them more accessible and practical. We provide a detailed security analysis for each scheme under reasonable assumptions. We study the security in a cloud computing environment in different levels. On one hand, we formalize a framework to study some popular real-life pseudorandom number generators used in almost every cryptographic application. On the other, we propose two efficient applications for cloud computing. The first allows a user to publicly share its high-entropy secret across different servers and to later recover it by interacting with some of these servers using only his password without requiring any authenticated data. The second, allows a client to securely outsource to a server an encrypted database that can be searched and modified later.

The fourth generation cellular mobile broadband, Long-Term Evolution (LTE), provides high speed Internet via Internet Protocol (IP). Today’s wireless infrastructure paves the way to a connected society where high speed Internet is seamlessly available at all times for anyone to use. To achieve this, a mobile service subscriber can no longer be bound to a single network provided by a single operator. Thus, roaming constitutes a key pillar in shaping the connected society Local Breakout (LBO) Voice over Long-Term Evolution (VoLTE) roaming enables a mobile service subscriber to breakout from its home network, and to use network services in a visited network. LBO requires control signalling and user data to be routed over several Public Land Mobile Networks (PLMNs), thus making mobile service subscriber’s the subject of Lawful Intercept (LI) across multiple networks. This thesis project investigates the possibility of using Multimedia Internet KEYing (MIKEY) and Secure Real-Time Transport Protocol (SRTP) to encrypt the payload of VoLTE media packets. More specifically, a Law Enforcement Monitoring Provider (LEMP) is designed, implemented, and evaluated. LEMP is deployed within a cell phone and serves to distribute cryptographic key shares to Trusted Third Parties (TTPs), i.e. multiple escrow agents, entrusted to store these cryptographic key shares. The result preserves the requirements for LI despite the fact that there may be multiple network operators involved. Moreover, the experiments show that the distribution time depends primarily on network latency rather than the time required to split the cryptographic key in chunks; hence the approach is usable in practice. / Den fjärde generationens mobila bredband, Long-Term Evolution (LTE), möjliggör användandet av höghastighetsinternet över Internet Protocol (IP). Dagens trådlösa infrastrukturer banar väg för ett fritt och lättillgängligt digitalt samhälle där alla kan vara uppkopplade samtidigt. För att uppnå global trådlös infrastruktur måste mobilabonnenten ha möjlighet att utnyttja flera andra trådlösa nätverk än det nätverk som teleoperatören binder dem till. Därför utgör fri roaming en viktig del i utvecklingen av framtidens globala trådlösa infrastrukturer. Local Breakout (LBO) Voice over Long-Term Evolution (VoLTE) är en roamingarkitektur som gör det möjligt för en mobilabonnent att kopplas upp från en teleoperatörs nät till en annans. LBO kräver att kontrollsignaler och användardata skickas mellan flera operatörer innan trafiken når sitt mål, och därmed utsätts mobilabonnenten för laglig avlyssning av elektronisk information på flera platser samtidigt. Det här examensarbetet undersöker möjligheten att använda Multimedia Internet KEYing (MIKEY) och Secure Real-Time Transport Protocol (SRTP) för att kryptera mediatrafik i VoLTE. Under arbetets gång utvecklas och utvärderas en Law Enforcement Monitoring Provider (LEMP). LEMP är placerad i en mobiltelefon och distribuerar delar av krypteringsnycklar till flera betrodda tredje parter (till flera escrow agents). Detta gör det möjligt att uppfylla kraven för laglig avlyssning av elektronisk information även när flera teleoperatörer avlyssnar användardata och kontrollsignaler. Resultatet visar att distribueringstiden primärt beror på nätverkslatens, och inte på den tid det tar att fördela krypteringsnyckeln i mindre delar. Därför kan den här metoden användas i praktiken.

<p>Secure computation allows mutually distrusting parties to compute over private data. Such collaborations have widespread applications in social, scientific, commercial, and security domains. However, the overhead of achieving security is a major bottleneck to the adoption of such technologies. In this context, this thesis aims to design the most secure protocol within budgeted computational or network resources by mathematically formulating it as an optimization problem. </p> <p>With the rise in CPU power and cheap RAM, the offline-online model for secure computation has become the prominent model for real-world security systems. This thesis investigates the above-mentioned optimization problem in the information-theoretic offline-online model. In particular, this thesis presents the following selected sample of our research in greater detail. </p> <p>Round and Communication Complexity: Chor-Kushilevitz-Beaver characterized the round and communication complexity of secure two-party computation. Since then, the case of functions with randomized output remained unexplored. We proved the decidability of determining these complexities. Next, if such a protocol exists, we construct the optimal protocol; otherwise, we present an obstruction to achieving security. </p> <p>Rate and Capacity of secure computation: The efficiency of converting the offline samples into secure computation during the online phase is essential. However, investigating this ``production rate'' for general secure computations seems analytically intractable. Towards this objective, we introduce a new model of secure computation -- one without any communication -- that has several practical applications. We lay the mathematical foundations of formulating rate and capacity questions in this framework. Our research identifies the first tight rate and capacity results (a la Shannon) in secure computation. </p> <p>Reverse multiplication embedding: We identify a new problem in algebraic complexity theory that unifies several efficiency objectives in cryptography. Reverse multiplication embedding seeks to implement as many (base field) multiplications as possible using one extension field multiplication. We present optimal construction using algebraic function fields. This embedding has subsequently led to efficient improvement of secure computation, homomorphic encryption, proof systems, and leakage-resilient cryptography. </p> <p>Characterizing the robustness to side-channel attacks: Side-channel attacks present a significant threat to the offline phase. We introduce the cryptographic analog of common information to characterize the offline phase's robustness quantitatively. We build a framework for security and attack analysis. In the context of robust threshold cryptography, we present a state-of-the-art attack, threat assessment, and security fix for Shamir's secret-sharing. </p> <p><br></p>

No / The Versatile and Ubiquitous Secret Sharing System, a cloud data repository secure access and a web based authentication scheme. It is designed to implement the sharing, distribution and reconstruction of sensitive secret data that could compromise the functioning of an organisation, if leaked to unauthorised persons. This is carried out in a secure web environment, globally. It is a threshold secret sharing scheme, designed to extend the human trust security perimeter. The system could be adapted to serve as a cloud data repository and secure data communication scheme. A secret sharing scheme is a method by which a dealer distributes shares of a secret data to trustees, such that only authorised subsets of the trustees can reconstruct the secret. This paper gives a brief summary of the layout and functions of a 15-page secure server-based website prototype; the main focus of a PhD research effort titled ‘Cryptography and Computer Communications Security: Extending the Human Security Perimeter through a Web of Trust’. The prototype, which has been successfully tested, has globalised the distribution and reconstruction processes. / Petroleum Technology Development Fund

Dans ce mémoire, nous nous pencherons tout particulièrement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre étude par la présentation d’un nouveau protocole de partage de secret quantique nécessitant un nombre minimal de parts quantiques c.-à-d. une seule part quantique par participant. L’ouverture de notre étude se fera par la présentation dans le chapitre préliminaire d’un survol des notions mathématiques sous-jacentes à la théorie de l’information quantique ayant pour but primaire d’établir la notation utilisée dans ce manuscrit, ainsi que la présentation d’un précis des propriétés mathématique de l’état de Greenberger-Horne-Zeilinger (GHZ) fréquemment utilisé dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous l’avons mentionné plus haut, c’est le domaine cryptographique qui restera le point focal de cette étude. Dans le second chapitre, nous nous intéresserons à la théorie des codes correcteurs d’erreurs classiques et quantiques qui seront à leur tour d’extrême importances lors de l’introduction de la théorie quantique du partage de secret dans le chapitre suivant. Dans la première partie du troisième chapitre, nous nous concentrerons sur le domaine classique du partage de secret en présentant un cadre théorique général portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples présentés pour leurs intérêts autant historiques que pédagogiques. Ceci préparera le chemin pour notre exposé sur la théorie quantique du partage de secret qui sera le focus de la seconde partie de ce même chapitre. Nous présenterons alors les théorèmes et définitions les plus généraux connus à date portant sur la construction de ces primitives en portant un intérêt particulier au partage quantique à seuil. Nous montrerons le lien étroit entre la théorie quantique des codes correcteurs d’erreurs et celle du partage de secret. Ce lien est si étroit que l’on considère les codes correcteurs d’erreurs quantiques étaient de plus proches analogues aux partages de secrets quantiques que ne leur étaient les codes de partage de secrets classiques. Finalement, nous présenterons un de nos trois résultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole sécuritaire et minimal de partage de secret quantique a seuil (les deux autres résultats dont nous traiterons pas ici portent sur la complexité de la communication et sur la simulation classique de l’état de GHZ). / In this thesis, we will focus on a cryptographic primitive known as secret sharing. We will explore both the classical and quantum domains of such schemes culminating our study by presenting a new protocol for sharing a quantum secret using the minimal number of possible quantum shares i.e. one single quantum share per participant. We will start our study by presenting in the preliminary chapter, a brief mathematical survey of quantum information theory (QIT) which has for goal primarily to establish the notation used throughout the manuscript as well as presenting a précis of the mathematical properties of the Greenberger-Horne-Zeilinger (GHZ)-state, which is used thoroughly in cryptography and in communication games. But as we mentioned above, our main focus will be on cryptography. In chapter two, we will pay a close attention to classical and quantum error corrections codes (QECC) since they will become of extreme importance when we introduce quantum secret sharing schemes in the following chapter. In the first part of chapter three, we will focus on classical secret shearing, presenting a general framework for such a primitive all the while illustrating the abstract concepts with examples presented both for their historical and analytical relevance. This first part (chapters one and two) will pave the way for our exposition of the theory of Quantum Secret Sharing (QSS), which will be the focus of the second part of chapter three. We will present then the most general theorems and definitions known to date for the construction of such primitives putting emphasis on the special case of quantum threshold schemes. We will show how quantum error correction codes are related to QSS schemes and show how this relation leads to a very solid correspondence to the point that QECC’s are closer analogues to QSS schemes than are the classical secret sharing primitives. Finally, we will present one of the three results we have in A. Broadbent, P.-R. Chouha, A. Tapp (2009) in particular, a secure minimal quantum threshold protocol (the other two results deal with communication complexity and the classical simulation of the GHZ-state).

Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication . / There are seemingly impossible problems to solve without a trusted third-party. How can two millionaires learn who is the richest when neither is willing to tell the other how rich he is? How can satellite collisions be prevented when the trajectories are secret? How can researchers establish correlations between diseases and medication while respecting patient confidentiality? How can an organization insure that the government does not abuse the knowledge that it possesses even though such an organization would be unable to control that information? Secure computation, a branch of cryptography, is a eld that studies how to generate protocols for realizing such tasks without the use of a trusted third party. There are certain goals that such protocols should achieve. The rst concern is privacy: players should learn no more information than what a trusted third party would give them. The second main goal is correctness: players should only receive what a trusted third party would give them. The protocols should also be efficient. Another important property is robustness, the protocols should not abort even if a small set of players is cheating. Secure computation has four basic building blocks : Oblivious Transfer, secret sharing, commitment schemes, and garbled circuits. Protocols can be built based only on these building blocks or alternatively, they can be constructed from specific computational assumptions. Protocols constructed solely from these primitives are flexible and are not as vulnerable to technological or algorithmic improvements. Many protocols are nevertheless based on computational assumptions. It is important to ask if efficiency requires computational assumptions. We show that this is not the case by building efficient protocols from these primitives. It is the conclusion of this thesis that building protocols from black-box primitives can also lead to e cient protocols. This thesis is a collection of four articles written in collaboration with other researchers. This constitutes the mature part of my investigation and is my main contributions to the field during that period of time. In the first work presented in this thesis we study the commitment capacity of noisy channels. We first show a tight lower bound that implies that in contrast to Oblivious Transfer, there exists no constant rate protocol for bit commitments. We then demonstrate that by restricting the way the commitments can be opened, we can achieve better efficiency and in particular cases, a constant rate. This is done by exploiting the notion of cover-free families. In the second article, we show that for certain problems, there exists a trade-off between robustness, correctness and privacy. This is done by using verifiable secret sharing, zero-knowledge, the concept of ghosts and a technique which we call \balls and bins". In our third contribution, we show that many protocols in the literature based on specific computational assumptions can be instantiated from a primitive known as Verifiable Oblivious Transfer, via the concept of Generalized Oblivious Transfer. The protocol uses secret sharing as its foundation. In the last included publication, we construct a constant-round protocol for secure two-party computation that is very efficient and only uses black-box primitives. The remarkable efficiency of the protocol is achieved by replacing the core of a standard protocol by a faulty but very efficient primitive. The fault is then dealt with by a non-trivial use of privacy amplification.

Un des thèmes pratiques, mais hautement sensibles, est le problème de sondage dans les réseaux sociaux où le caractère secret des informations sélectionnées et la réputation de l’utilisateur sont très critiques. En effet, les utilisateurs désirent préserver la confidentialité de leurs votes et dissimuler, le cas échéant, leurs mauvais comportements. Récemment, Guerraoui et al. ont propose des protocoles de sondage basés sur la partage de secret et ne nécessitant aucune infrastructure cryptographique. Néanmoins, ces protocoles ne sont applicables que si le graphe social a une structure d’anneau et le nombre d’utilisateurs est un carré parfait. Dans cette thèse, nous traitons, d’une part, du problème du déploiement décentralisé des protocoles de sondage qui sont basés sur des graphes sociaux ayant des structures générales, et d’autre part, du problème de transformation des graphes sociaux pour augmenter les propriétés de vie privée et de précision, nécessaires au déroulement sûr et rentable du sondage décentralisé. Premièrement, nous proposons trois protocoles décentralisés qui s’appuient sur l’état originel (sans transformation) des graphes sociaux. Les deux premiers protocoles utilisent respectivement des modèles de communication synchrone et asynchrone, et manipulent des procédures de vérification pour détecter les utilisateurs malhonnêtes. Quant au troisième protocole, il est asynchrone et ne nécessite pas de procédures de vérification. Pour que ce protocole permette une diffusion efficace de messages, nous avons défini une propriété sur les graphes sociaux, appelée “m-broadcasting”. Dans la deuxième partie de la thèse, nous formalisons le problème de “l’ajout des amis” qui consiste à trouver une transformation optimale des graphes sociaux pour les adapter au partage de secret. Pour résoudre ce problème, nous présentons deux algorithmes selon deux approches différentes: centralisée et décentralisée. Une évaluation expérimentale montre que nos protocoles sont précis et restreints aux bornes théoriques / One of the current practical, useful but sensitive topic in social networks is polling problem where the privacy of exchanged information and user reputation are very critical. Indeed, users want to preserve the confidentiality of their votes and to hide, if any, their misbehaviors. 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 the social graph structure should be transformed into a ring structure-based overlay and the number of participating users is perfect square. In this thesis, we address the problem of deploying decentralized polling protocols for general social graphs and how to transform these graphs in order to increase the privacy and/or accuracy properties. First, we propose three simple decentralized polling protocols that rely on the current state of social graphs. The two first protocols use synchronous and asynchronous models and verification procedures to detect the misbehaving users. The third 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. Second, 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 solutions with some performance evaluations which show that our protocols are accurate, and inside the theoretical bounds