<p>Secure multi-party computation (MPC) enables mutually distrusting parties to compute securely over their private data. It is a natural approach for building distributed applications with strong privacy guarantees, and it has been used in more and more real-world privacy-preserving solutions such as privacy-preserving machine learning, secure financial analysis, and secure auctions.</p> <p><br></p> <p>The typical method of MPC is to represent the function with arithmetic circuits or binary circuits, then MPC can be applied to compute each gate privately. The practicality of secure multi-party computation (MPC) has been extensively analyzed and improved over the past decade, however, we are hitting the limits of efficiency with the traditional approaches as the circuits become more complicated. Therefore, we follow the design principle of identifying and constructing fast and provably-secure MPC protocols to evaluate useful high-level algebraic abstractions; thus, improving the efficiency of all applications relying on them. </p> <p><br></p> <p>To begin with, we construct an MPC protocol to efficiently evaluate the powers of a secret value. Then we use it as a building block to form a secure mixing protocol, which can be directly used for anonymous broadcast communication. We propose two different protocols to achieve secure mixing offering different tradeoffs between local computation and communication. Meanwhile, we study the necessity of robustness and fairness in many use cases, and provide these properties to general MPC protocols. As a follow-up work in this direction, we design more efficient MPC protocols for anonymous communication through the use of permutation matrices. We provide three variants targeting different MPC frameworks and input volumes. Besides, as the core of our protocols is a secure random permutation, our protocol is of independent interest to more applications such as secure sorting and secure two-way communication.</p> <p><br></p> <p>Meanwhile, we propose the solution and analysis for another useful arithmetic operation: secure multi-variable high-degree polynomial evaluation over both scalar and matrices. Secure polynomial evaluation is a basic operation in many applications including (but not limited to) privacy-preserving machine learning, secure Markov process evaluation, and non-linear function approximation. In this work, we illustrate how our protocol can be used to efficiently evaluate decision tree models, with both the client input and the tree models being private. We implement the prototypes of this idea and the benchmark shows that the polynomial evaluation becomes significantly faster and this makes the secure comparison the only bottleneck. Therefore, as a follow-up work, we design novel protocols to evaluate secure comparison efficiently with the help of pre-computed function tables. We implement and test this idea using Falcon, a state-of-the-art privacy-preserving machine learning framework and the benchmark results illustrate that we get significant performance improvement by simply replacing their secure comparison protocol with ours.</p> <p><br></p>

Ce travail de thèse a pour objectif de renforcer la protection de la vie privée dans l'édition collaborative de documents dématérialisés. Une première partie de notre travail a consisté en l'élaboration d'un modèle sécurisé d'éditeur collaboratif de documents. La confidentialité des documents est assurée grâce à un contrôle d'accès décentralisé. Une seconde partie a été de protéger l'identité des utilisateurs communicants en assurant leur anonymat lors de l'édition des documents. Notre concept d'éditeur collaboratif est fondé sur l'utilisation d'ensembles de modifications apportées à un document, que nous nommons deltas, lesquels définissent des versions du document. Les deltas permettent de conserver l'historique des modifications successives. Lorsqu'une nouvelle version d'un document apparait, seul le nouveau delta qui en découle doit être transmis et stocké : les documents sont ainsi distribués à travers un ensemble de sites de stockage. Cela permet, d'une part, d'alléger la charge du gestionnaire des versions des documents, et d'autre part, d'améliorer la sécurité générale. La récupération décentralisée d'une nouvelle version nécessite seulement celle des deltas manquants par rapport à une version précédente; elle est donc moins coûteuse que la récupération du document en entier. L'information du lien entre les deltas est enregistrée directement avec les deltas et non dans une table ou dans un objet de métadonnées ce qui améliore leur sécurité. La gestion des versions est faite afin de maintenir une cohérence entre les versions. / This thesis aims to strengthen the protection of privacy of authors in collaborative editing of electronic documents. The first part of our work consisted in the design a secured model for a collaborative document editor. Documents' confidentiality is ensured through a decentralized access control mechanism. A second part of the work was to protect the identity of communicating users by ensuring their anonymity during collaborative document editing. Our concept of collaborative editor is based on the use of sets of modifications for a document, which we call textit{deltas}. Thus, deltas define versions of the document and they can keep the history of subsequent modifications. When a new version of a document appears, only the new delta that results must be transmitted and stored : documents are thus distributed across a set of storage sites (servers). We show how this allows, first, to reduce the load of document version control system, and secondly, to improve overall security of the collaborative system. Decentralized recovery of a new version requires only recovery of appropriate deltas against a previous version and is therefore more efficient than recovering the entire document. The information of the link between deltas is stored directly with deltas and not in a table or a metadata object, that improves their security. The version control system maintains consistency between versions. Once a user has retrieved versions, she holds them in local, and the history can be accessed at any time without being necessary to connect to the central server. Deltas can be identified, indexed and maintained their integrity through the use of hash functions.