Oblivious Transfer (OT) is one of the most fundamental cryptographic primitives with wide-spread application in general secure multi-party computation (MPC) as well as in a number of tailored and special-purpose problems of interest such as private set intersection (PSI), private information retrieval (PIR), contract signing to name a few. Often the instantiations of OT require prohibitive communication and computation complexity. OT extension protocols are introduced to compute a very large number of OTs referred as extended OTs at the cost of a small number of OTs referred as seed OTs. We present a fast OT extension protocol for small secrets in active setting. Our protocol when used to produce 1-out-of-n OTs outperforms all the known actively secure OT extensions. Our protocol is built on the semi-honest secure extension protocol of Kolesnikov and Kumaresan of CRYPTO'13 (referred as KK13 protocol henceforth) which is the best known OT extension for short secrets. At the heart of our protocol lies an efficient consistency checking mechanism that relies on the linearity of Walsh-Hadamard (WH) codes. Asymptotically, our protocol adds a communication overhead of O( log ) bits over KK13 protocol irrespective of the number of extended OTs, where and refer to computational and statistical security parameter respectively. Concretely, our protocol when used to generate a large enough number of OTs adds only 0:011-0:028% communication overhead and 4-6% runtime overhead both in LAN and WAN over KK13 extension. The runtime overheads drop below 2% when in addition the number of inputs of the sender in the extended OTs is large enough. As an application of our proposed extension protocol, we show that it can be used to obtain the most efficient PSI protocol secure against a malicious receiver and a semi-honest sender.

My research investigates three questions: How do we customize protocols and implementations to account for the unique requirement of each setting and its target community, what are necessary steps that we can take to transition secure computation tools into practice, and how can we promote their adoption for users at large? In this dissertation I present several of my works that address these three questions with a particular focus on one of them. First my work on "Hecate: Abuse Reporting in Secure Messengers with Sealed Sender" designs a customized protocol to protect people from abuse and surveillance in online end to end encrypted messaging. Our key insight is to add pre-processing to asymmetric message franking, where the moderating entity can generate batches of tokens per user during off-peak hours that can later be deposited when reporting abuse. This thesis then demonstrates that by carefully tailoring our cryptographic protocols for real world use cases, we can achieve orders of magnitude improvements over prior works with minimal assumptions over the resources available to people. Second, my work on "Batched Differentially Private Information Retrieval" contributes a novel Private Information Retrieval (PIR) protocol called DP-PIR that is designed to provide high throughput at high query rates. It does so by pushing all public key operations into an offline stage, batching queries from multiple clients via techniques similar to mixnets, and maintain differential privacy guarantees over the access patterns of the database. Finally, I provide three case studies showing that we cannot hope to further the adoption of cryptographic tools in practice without collaborating with the very people we are trying to protect. I discuss a pilot deployment of secure multi-party computation (MPC) that I have done with the Department of Education, deployments of MPC I have done for the Boston Women’s Workforce Council and the Greater Boston Chamber of Commerce, and ongoing work in developing tool chain support for MPC via an automated resource estimation tool called Carousels.

安全多方計算是資訊安全研究裡的一個重要主題，其概念為多方在不洩漏各自私有資訊下能一起完成某種函式的計算。在安全多方計算研究領域裡，有一種作法是以scalar product來當作計算的基礎演算邏輯單元，重而建構其他更複雜的安全多方計算。本論文首先針對scalar product發展一套平行性實作架構，藉此我們再實作出多個不同演算法之comparison計算，其中包含了循序演算法以及平行演算法。我們透過實驗來找出適當的平行計算基礎架構與影響執行時間效能的主要因子，並以執行時間效能上的分析來推導相關時間公式。由上述實證研究我們對於不同演算法之comparison計算來作執行時間效能的預測，從實驗結果可以得知我們推導出來之時間公式極為準確，希望能給予使用者在執行comparison計算有所考量，使其在不同執行環境執行comparison計算能有最佳的執行時間效能。 / Loosely speaking, secure multi-party computation (SMC) involves computing functions with inputs from two or more parties in a distributed network while ensuring that no additional information, other than what can be inferred from each participant’s input and output, is revealed to parties not privy to that information. This thesis concerns the parallel implementation of SMC using a scalar-product (SP) based approach. In this approach, SP is considered as the basic building block for constructing more complex SMC. My thesis first develops a concurrent architecture for implementing two-party scalar product computation. Then it implements several algorithms of secure comparison. Finally, a series of experiments are conducted to collect performance statistics for building time functions that can predict the execution time of comparison computation based on that of the scalar product and other parameters, such as CPU core numbers. From the experimental results, we find that these time functions are very accurate. Hence we argue that these time functions can assist users to obtain the better runtime performance for comparison protocols under their specific execution environments.

Dans un monde de plus en plus connecté, la question de la confiance dans les sys-tèmes d’information qui nous entourent devient primordiale, et amène naturellement à des interrogations quant à leur sécurité. Les enjeux de cette dernière concernent autant la confidentialité des données individuelles que la protection des architectures critiques, notamment déployées dans le domaine de l’énergie et du transport. Dans cette thèse, nous abordons trois problématiques liées aux architectures de sécurité des systèmes d’information. Tout d’abord, nous proposons une architecture pour un module de rupture protocolaire, fournissant une protection face aux attaques utilisant le réseau comme vecteur. Grâce à l’isolation et le filtrage des échanges qu’il réalise, nous montrons que ce nouvel équipement est particulièrement adapté à la sécurisation des systèmes de contrôle-commandes. Nous abordons ensuite le thème de la sécurité des utilisateurs finaux ou objets connectés, par la définition d’une Infrastructure de Gestion de Clefs (IGC) centrée sur ces derniers, dénommée LocalPKI. Elle repose sur l’utilisation de certificats auto-signés, et son objectif est d’allier la simplicité des IGC pair-à-pair avec la sécurité des IGC hiérarchiques.Enfin, nous nous intéressons à l’amélioration du mécanisme des ancres de confiance pour les autorités de certification, utilisé par exemple dans PKIX et LocalPKI. A cet égard, nous commençons par définir des protocoles multi-parties permettant de calculer des produits scalaires et matriciels, préservant la confidentialité des données. Nous montrons finalement comment les appliquer dans le cadre de l’agrégation de confiance, et par conséquent à la réputation des autorités de certification / In a increasingly connected world, trust in information systems is essential. Thus, many questions about their security arise. Topics of these questions include individual data confidentiality as well as protection of Industrial Critical Systems(ICS). For instance, ICS are deployed in sectors including energy or transportation where security is of high importance. In this thesis, we address three problems related to the security architecture of information systems. We first propose an architecture for a protocol splitting device. This provides protection against networkattacks by isolating and filtering data exchanges. We show that this new security equipment is well suited for ICS. Then, we focus on end-user security. We define a user-centric Public Key Infrastructure (PKI) called LocalPKI. By using self-signed certificates, this infrastructure combines the user-friendliness of PGP-based PKI and the security of hierarchical PKI. Finally, we improve the trust anchormechanism. It is employed by Certification Authorities (CA) and especially used in PKIX or LocalPKI. In that respect, we first define multi-party protocols to securely compute dot and matrix products. Then, we explain how to apply them on trust aggregations and thus on the reputation of certification authorities.

Une large quantité de données personnelles sont partagées en temps réel par des utilisateurs en ligne, utilisant de plus en plus des terminaux mobiles avec connexion sans-fil. L'industrie s'efforce d'accumuler et d'analyser ces données pour fournir de nouveaux services ou des améliorations. La recherche fournit un effort équivalent pour permettre de traiter ces données de façon sécurisée et protectrice de la vie privée. Les problèmes de performance des communications temps réels sur terminaux mobiles sur un canal sans-fil sont aussi étudiés. Les codes à effacement sont un moyen courant d'améliorer ces performances. Le secret sharing est un mécanisme permettant de partager des données privées, ne les révélant qu'à un groupe d'utilisateur choisi. Dans cette thèse, nous lions théoriquement les secret sharing schemes et les codes à effacement, pour fournir une source plus riche de solutions aux deux problèmes. Notre objectif est de fournir des solutions ayant le niveau de sécurité souhaité, tout en restant efficace et implémentable. Les contributions de cette thèse sont les suivantes. Nous évaluons l'applicabilité d'une nouvelle classe de codes à effacements à Maximum Distance Séparable (MDS) pour transférer du contenu temps réel à des terminaux mobiles, et nous démontrons que le code systématique réduit grandement la complexité d'exécution et la taille nécessaire des tampons en comparaison du code non systématique, faisant de lui un bon candidat pour une application mobile. Nous proposons un nouveau Layered secret sharing scheme pour le partage en temps réel de données sur des réseaux sociaux (OSNs pour Online Social Network). Le procédé permet de partager automatiquement un profile dans un groupe défini dans un OSN, en utilisant un multi-secret sharing scheme formé de multiples couches. Le procédé ne dépend nullement d'un tiers de confiance. Comparé à un partage simple de chaque attributs (pouvant être un texte, une image ou une vidéo), le procédé ne divulgue aucune information à propos de ce qui est partagé, pas même le nombre de ceux-ci, et il induit une augmentation relativement faible du temps de calcul et des données à envoyer. Finalement, nous étudions les liens entre les codes MDS et les secret sharing schemes, ayant pour motivation l'inefficacité du très populaire Shamir secret sharing scheme. Nous établissons les liens théoriques entre les deux domaines et nous proposons une nouvelle construction de strong ramp schemes à partir de codes MDS. Ceci permet d'utiliser les codes MDS existants et efficaces pour des applications de partage de secret et de calculs distribués et sécurisés. Nous évaluons et montrons une réduction significative de temps de calcul et du coût de communication en utilisant un strong ramp scheme, en comparaison avec le procédé de Shamir. / Data from both individuals and companies is increasingly aggregated and analysed to provide new and improved services. There is a corresponding research effort to enable processing of such data in a secure and privacy preserving way, in line with the increasing public concerns and more stringent regulatory requirements for the protection of such data. Secure Multi-Party Computation (MPC) and secret sharing are mechanisms that can enable both secure distribution and computations on private data. In this thesis, we address the inefficiencies of these mechanisms by utilising results from a theoretically related rich area, erasure codes. We derive links between erasure codes and secret sharing, and use Maximum Distance Separable (MDS) codes as a basis to provide real-time applications relying on private user's data, revealing this data only to the selected group (which can be empty). The thesis has three contributions. A new class of erasure code called on-the-fly coding, have been introduced for their improvements in terms of recovery delay and achievable capacity. However little is known about the complexity of the systematic and non-systematic variants of this code, notably for live multicast transmission of multimedia content which is their ideal use case. The evaluation of both variants demonstrate that the systematic code outperforms the non-systematic one in regard to both the buffer sizes and the computation complexity. Then, we propose a new Layered secret sharing scheme and its application to Online Social Network (OSN). In current OSN, access to the user's profile information is managed by the service provider based on a limited set of rules. The proposed scheme enables automated profile sharing in OSN's groups with fine grained privacy control, via a multi-secret sharing scheme comprising of layered shares, without relying on a trusted third party. We evaluate the security of the scheme and the resulting profile's level of protection in an OSN scenario. Finally, after showing that erasure codes are efficient for real-time applications and that the security offered by secret sharing schemes can be applied to real-case applications, we derive the theoretical links between MDS codes and secret sharing to enable the implementation of efficient secret sharing scheme built from MDS codes. To illustrate this efficiency, we implement two of these schemes and evaluate their benefits in regard to computation and communication costs in an MPC application.

Le chiffrement homomorphe est une branche de la cryptologie, dans laquelle les schémas de chiffrement offrent la possibilité de faire des calculs sur les messages chiffrés, sans besoin de les déchiffrer. L’intérêt pratique de ces schémas est dû à l’énorme quantité d'applications pour lesquels ils peuvent être utilisés. En sont un exemple le vote électronique, les calculs sur des données sensibles, comme des données médicales ou financières, le cloud computing, etc..Le premier schéma de chiffrement (complètement) homomorphe n'a été proposé qu'en 2009 par Gentry. Il a introduit une technique appelée bootstrapping, utilisée pour réduire le bruit des chiffrés : en effet, dans tous les schémas de chiffrement homomorphe proposés, les chiffrés contiennent une petite quantité de bruit, nécessaire pour des raisons de sécurité. Quand on fait des calculs sur les chiffrés bruités, le bruit augmente et, après avoir évalué un certain nombre d’opérations, ce bruit devient trop grand et, s'il n'est pas contrôlé, risque de compromettre le résultat des calculs.Le bootstrapping est du coup fondamental pour la construction des schémas de chiffrement homomorphes, mais est une technique très coûteuse, qu'il s'agisse de la mémoire nécessaire ou du temps de calcul. Les travaux qui on suivi la publication de Gentry ont eu comme objectif celui de proposer de nouveaux schémas et d’améliorer le bootstrapping pour rendre le chiffrement homomorphe faisable en pratique. L’une des constructions les plus célèbres est GSW, proposé par Gentry, Sahai et Waters en 2013. La sécurité du schéma GSW se fonde sur le problème LWE (learning with errors), considéré comme difficile en pratique. Le bootstrapping le plus rapide, exécuté sur un schéma de type GSW, a été proposé en 2015 par Ducas et Micciancio. Dans cette thèse on propose une nouvelle variante du schéma de chiffrement homomorphe de Ducas et Micciancio, appelée TFHE.Le schéma TFHE améliore les résultats précédents, en proposant un bootstrapping plus rapide (de l'ordre de quelques millisecondes) et des clés de bootstrapping plus petites, pour un même niveau de sécurité. TFHE utilise des chiffrés de type TLWE et TGSW (scalaire et ring) : l’accélération du bootstrapping est principalement due à l’utilisation d’un produit externe entre TLWE et TGSW, contrairement au produit externe GSW utilisé dans la majorité des constructions précédentes.Deux types de bootstrapping sont présentés. Le premier, appelé gate bootstrapping, est exécuté après l’évaluation homomorphique d’une porte logique (binaire ou Mux) ; le deuxième, appelé circuit bootstrapping, peut être exécuté après l’évaluation d’un nombre d'opérations homomorphiques plus grand, pour rafraîchir le résultat ou pour le rendre compatible avec la suite des calculs.Dans cette thèse on propose aussi de nouvelles techniques pour accélérer l’évaluation des calculs homomorphiques, sans bootstrapping, et des techniques de packing des données. En particulier, on présente un packing, appelé vertical packing, qui peut être utilisé pour évaluer efficacement des look-up table, on propose une évaluation via automates déterministes pondérés, et on présente un compteur homomorphe appelé TBSR qui peut être utilisé pour évaluer des fonctions arithmétiques.Pendant les travaux de thèse, le schéma TFHE a été implémenté et il est disponible en open source.La thèse contient aussi des travaux annexes. Le premier travail concerne l’étude d’un premier modèle théorique de vote électronique post-quantique basé sur le chiffrement homomorphe, le deuxième analyse la sécurité des familles de chiffrement homomorphe dans le cas d'une utilisation pratique sur le cloud, et le troisième ouvre sur une solution différente pour le calcul sécurisé, le calcul multi-partite. / Fully homomorphic encryption is a new branch of cryptology, allowing to perform computations on encrypted data, without having to decrypt them. The main interest of homomorphic encryption schemes is the large number of practical applications for which they can be used. Examples are given by electronic voting, computations on sensitive data, such as medical or financial data, cloud computing, etc..The first fully homomorphic encryption scheme has been proposed in 2009 by Gentry. He introduced a new technique, called bootstrapping, used to reduce the noise in ciphertexts: in fact, in all the proposed homomorphic encryption schemes, the ciphertexts contain a small amount of noise, which is necessary for security reasons. If we perform computations on noisy ciphertexts, the noise increases and, after a certain number of operations, the noise becomes to large and it could compromise the correctness of the final result, if not controlled.Bootstrapping is then fundamental to construct fully homomorphic encryption schemes, but it is very costly in terms of both memory and time consuming.After Gentry’s breakthrough, the presented schemes had the goal to propose new constructions and to improve bootstrapping, in order to make homomorphic encryption practical. One of the most known schemes is GSW, proposed by Gentry, Sahai et Waters in 2013. The security of GSW is based on the LWE (learning with errors) problem, which is considered hard in practice. The most rapid bootstrapping on a GSW-based scheme has been presented by Ducas and Micciancio in 2015. In this thesis, we propose a new variant of the scheme proposed by Ducas and Micciancio, that we call TFHE.The TFHE scheme improves previous results, by performing a faster bootstrapping (in the range of a few milliseconds) and by using smaller bootstrapping keys, for the same security level. TFHE uses TLWE and TGSW ciphertexts (both scalar and ring): the acceleration of bootstrapping is mainly due to the replacement of the internal GSW product, used in the majority of previous constructions, with an external product between TLWE and TGSW.Two kinds of bootstrapping are presented. The first one, called gate bootstrapping, is performed after the evaluation of a homomorphic gate (binary or Mux); the second one, called circuit bootstrapping, can be executed after the evaluation of a larger number of homomorphic operations, in order to refresh the result or to make it compatible with the following computations.In this thesis, we also propose new techniques to improve homomorphic computations without bootstrapping and new packing techniques. In particular, we present a vertical packing, that can be used to efficiently evaluate look-up tables, we propose an evaluation via weighted deterministic automata, and we present a homomorphic counter, called TBSR, that can be used to evaluate arithmetic functions.During the thesis, the TFHE scheme has been implemented and it is available in open source.The thesis contains also ancillary works. The first one concerns the study of the first model of post-quantum electronic voting based on fully homomorphic encryption, the second one analyzes the security of homomorphic encryption in a practical cloud implementation scenario, and the third one opens up about a different solution for secure computing, multi-party computation.

Nous présentons une nouvelle approche de préservation de la vie privée pour améliorer l’équité des éléments dans les systèmes de classement. Nous utilisons des techniques de post-traitement dans un environnement de recommandation multipartite afin d’équilibrer l’équité et la protection de la vie privée pour les producteurs et les consommateurs. Notre méthode utilise des serveurs de calcul multipartite sécurisés (MPC) et une confidentialité différentielle (DP) pour maintenir la confidentialité des utilisateurs tout en atténuant l’injustice des éléments sans compromettre l’utilité. Les utilisateurs soumettent leurs données sous forme de partages secrets aux serveurs MPC, et tous les calculs sur ces données restent cryptés. Nous évaluons notre approche à l’aide d’ensembles de données du monde réel, tels qu’Amazon Digital Music, Book Crossing et MovieLens-1M, et analysons les compromis entre confidentialité, équité et utilité. Notre travail encourage une exploration plus approfondie de l’intersection de la confidentialité et de l’équité dans les systèmes de recommandation, jetant les bases de l’intégration d’autres techniques d’amélioration de la confidentialité afin d’optimiser l’exécution et l’évolutivité pour les applications du monde réel. Nous envisageons notre approche comme un tremplin vers des solutions de bout en bout préservant la confidentialité et promouvant l’équité dans des environnements de recommandation multipartites. / We present a novel privacy-preserving approach to enhance item fairness in ranking systems. We employ post-processing techniques in a multi-stakeholder recommendation environment in order to balance fairness and privacy protection for both producers and consumers. Our method utilizes secure multi-party computation (MPC) servers and differential privacy (DP) to maintain user privacy while mitigating item unfairness without compromising utility. Users submit their data as secret shares to MPC servers, and all calculations on this data remain encrypted. We evaluate our approach using real-world datasets, such as Amazon Digital Music, Book Crossing, and MovieLens-1M, and analyze the trade-offs between privacy, fairness, and utility. Our work encourages further exploration of the intersection of privacy and fairness in recommender systems, laying the groundwork for integrating other privacy-enhancing techniques to optimize runtime and scalability for real-world applications. We envision our approach as a stepping stone towards end-to-end privacy-preserving and fairness-promoting solutions in multi-stakeholder recommendation environments.

安全多方計算的研究主要是針對在分散環境下的兩造(或多方)之間，如何在不透露彼此私有的資料的情況下，計算一個約定函數的問題，並要確保除了計算結果及其可能推導出的資訊，不會洩漏額外的私有資料。依此設計出來的函數算法，稱為安全的多方計算協定(protocol)。 過去兩年本實驗室根據一套基於向量內積運算(scalar product)發展出的安全多方計算方法，設計了一個雛型的分散式系統框架，開發了一套符合其安全要求的常用算數運算函數庫。 但目前個別的應用問題在此系統上發展安全協定的程式時，使用者必須相當熟悉其架構與程式庫細節，才能開發所需程式，造成推廣上的障礙。有鑑於此，本論文採用領域專屬語言(domain-specific language)的方法與技術，針對一般安全多方協定程式的特徵來進行歸納與分析，找出協助其表達計算步驟的適當抽象機制，並在設計上訂定了以下目標： 1. 設計一高階語言用以描述多方安全計算，以提供使用者撰寫安全多方計算程式。 2. 檢查並確保使用者撰寫的程式不會有資訊洩漏。 3. 多方安全運算執行上能保持一定的效率。 4. 建立多方安全計算的運算流程，讓PDL與現有的運作環境配合，達到各伺服器合作運行多方安全計算的目的。 朝向這四個目標發展出一套協定描述語言與其編譯器。以便與SMC-Protocol以及其環境合作，協助領域專家以更簡便的方式來設計與實驗更多的安全多方協定。我們稱此語言為多方安全計算協定描述語言(Protocol Description Language, PDL)。 / Protocols for secure multi-party computation (SMC) allow participants to share a computation while each party learns only what can be inferred from their own inputs and the output of the computation. In the past two years, we developed an SMC implementation framework for both integers and floating numbers which comprises a set of arithmetic operations that manipulate secret values among involved parties using the scalar product protocol as the basis. Such a library of arithmetic operations is call building blocks. But using this library is not easy. To solve individual SMC problem, programmer should knowing the given framework and protocol detail very well. This difficulty makes them won't consider this framework while facing the need of SMC. To ease the writing of more complex user-defined protocols, using the technique of domain-specific language, this thesis analysis the general needs of SMC, develop a domain-specific language of SMC, and implement a compiler that coverts this language to SMC code, which is executable code composed of the protocols of given framework. We called this language Protocol Description Language, PDL.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal