Machine Learning (ML) profitiert erheblich von der Verfügbarkeit großer Mengen an Trainingsdaten, sowohl im Bezug auf die Anzahl an Datenpunkten, als auch auf die Anzahl an Features pro Datenpunkt. Es ist allerdings oft weder möglich, noch gewollt, mehr Daten unter zentraler Kontrolle zu aggregieren. Multi-Party-Computation (MPC)-Protokolle stellen eine Lösung dieses Dilemmas in Aussicht, indem sie es mehreren Parteien erlauben, ML-Modelle auf der Gesamtheit ihrer Daten zu trainieren, ohne die Eingabedaten preiszugeben. Generische MPC-Ansätze bringen allerdings erheblichen Mehraufwand in der Kommunikations- und Laufzeitkomplexität mit sich, wodurch sie sich nur beschränkt für den Einsatz in der Praxis eignen. Das Ziel dieser Arbeit ist es, Privatsphäreerhaltendes Machine Learning mittels MPC praxistauglich zu machen. Zuerst fokussieren wir uns auf zwei Anwendungen, lineare Regression und Klassifikation von Dokumenten. Hier zeigen wir, dass sich der Kommunikations- und Rechenaufwand erheblich reduzieren lässt, indem die aufwändigsten Teile der Berechnung durch Sub-Protokolle ersetzt werden, welche auf die Zusammensetzung der Parteien, die Verteilung der Daten, und die Zahlendarstellung zugeschnitten sind. Insbesondere das Ausnutzen dünnbesetzter Datenrepräsentationen kann die Effizienz der Protokolle deutlich verbessern. Diese Beobachtung verallgemeinern wir anschließend durch die Entwicklung einer Datenstruktur für solch dünnbesetzte Daten, sowie dazugehöriger Zugriffsprotokolle. Aufbauend auf dieser Datenstruktur implementieren wir verschiedene Operationen der Linearen Algebra, welche in einer Vielzahl von Anwendungen genutzt werden. Insgesamt zeigt die vorliegende Arbeit, dass MPC ein vielversprechendes Werkzeug auf dem Weg zu Privatsphäre-erhaltendem Machine Learning ist, und die von uns entwickelten Protokolle stellen einen wesentlichen Schritt in diese Richtung dar. / Machine learning (ML) greatly benefits from the availability of large amounts of training data, both in terms of the number of samples, and the number of features per sample. However, aggregating more data under centralized control is not always possible, nor desirable, due to security and privacy concerns, regulation, or competition. Secure multi-party computation (MPC) protocols promise a solution to this dilemma, allowing multiple parties to train ML models on their joint datasets while provably preserving the confidentiality of the inputs. However, generic approaches to MPC result in large computation and communication overheads, which limits the applicability in practice. The goal of this thesis is to make privacy-preserving machine learning with secure computation practical. First, we focus on two high-level applications, linear regression and document classification. We show that communication and computation overhead can be greatly reduced by identifying the costliest parts of the computation, and replacing them with sub-protocols that are tailored to the number and arrangement of parties, the data distribution, and the number representation used. One of our main findings is that exploiting sparsity in the data representation enables considerable efficiency improvements. We go on to generalize this observation, and implement a low-level data structure for sparse data, with corresponding secure access protocols. On top of this data structure, we develop several linear algebra algorithms that can be used in a wide range of applications. Finally, we turn to improving a cryptographic primitive named vector-OLE, for which we propose a novel protocol that helps speed up a wide range of secure computation tasks, within private machine learning and beyond. Overall, our work shows that MPC indeed offers a promising avenue towards practical privacy-preserving machine learning, and the protocols we developed constitute a substantial step in that direction.

This thesis considers the problem of finitely iterated rational secret sharing. We describe how to evaluate this problem using game theory and finitely iterated prisoner’s dilemma. The players each have a private horizon that the other player does not know. The only thing that a player knows about their opponent’s private horizon is a common upper bound. The description of a synchronous and asynchronous finitely iterated secret sharing protocol with private information is followed by a game theoretic proof of the viability of such protocols. / Graduate

Electronic data has become the standard method of storing information in our modern age. Evolving from paper-based data to electronic data creates opportunities to share information between organizations in record speeds, especially when handling large data sets. However, sharing sensitive information creates requirements for electronic data exchange: privacy requires that the original data will not be revealed to unauthorized parties. In the healthcare sector in particular, there are two important use cases that require exchanging information in a privacy-preserving way. 1. Contract research organizations (CROs) need to verify the eligibility of a participant in a phase 1 clinical trial. One criterion is checking that an individual is not concurrently enrolled in a trial at another CRO. However, privacy laws and the maintenance of a private list of participants for competitive purposes prevent CROs from checking against that criterion. 2. A patient’s medical record is usually distributed amongst several healthcare organizations. To improve healthcare services, it is important to have a patient’s complete medical history: either to help diagnose an illness or to gather statistics for better disease control. However, patient medical files need to be confidential. Two healthcare organizations cannot link their large patient databases by disclosing identity revealing details (e.g., names or health card numbers). This thesis presents the development and evaluation of protocols capable of querying and linking datasets in a privacy-preserving manner: TRACK for checking concurrent enrolment in phase 1 clinical trials, and SHARE for linking two large datasets in terms of millions of (patient medical) records. These protocols are better than existing approaches in terms of the privacy protection level they offer (e.g., against dictionary and frequency attacks), of the reliance on trusted third parties, and of performance when performing blocking. These protocols were extensively validated in simulated scenarios similar to their real-world counterparts. The thesis presents novel identity representation schemes that offer strong privacy measures while being efficient for very large databases. These schemes may be used by other researchers to represent identity in different use cases. CROs may implement the protocols (and especially TRACK) in systems to check if an individual exists in another CRO’s dataset without revealing the identity of that individual. Two healthcare organizations may use a system based on this research (and especially the SHARE protocol) to discover their common patients while protecting the identities of the other patients.

Les cryptosystèmes sont présents dans de nombreux appareils utilisés dans la vie courante, tels que les cartes à puces, ordiphones, ou passeports. La sécurité de ces appareils est menacée par les attaques par canaux auxiliaires, où un attaquant observe leur comportement physique pour obtenir de l’information sur les secrets manipulés. L’évaluation de la résilience de ces produits contre de telles attaques est obligatoire afin de s’assurer la robustesse de la cryptographie embarquée. Dans cette thèse, nous exhibons une méthodologie pour évaluer efficacement le taux de succès d’attaques par canaux auxiliaires, sans avoirbesoin de les réaliser en pratique. En particulier, nous étendons les résultats obtenus par Rivain en 2009, et nous exhibons des formules permettant de calculer précisément le taux de succès d’attaques d’ordre supérieur. Cette approche permet une estimation rapide de la probabilité de succès de telles attaques. Puis, nous étudions pour la première fois depuis le papier séminal de Ishai, Sahai et Wagner en 2003 le problème de la quantité d’aléa nécessaire dans la réalisation sécurisée d’une multiplication de deux bits. Nous fournissons des constructions explicites pour des ordres pratiques de masquage, et prouvons leur sécurité et optimalité. Finalement, nous proposons un protocole permettant le calcul sécurisé d’un veto parmi un nombre de joueurs arbitrairement grand, tout en maintenant un nombre constant de bits aléatoires. Notre construction permet également la multiplication sécurisée de n’importe quel nombre d’éléments d’un corps fini. / Cryptosystems are present in a lot of everyday life devices, such as smart cards, smartphones, set-topboxes or passports. The security of these devices is threatened by side-channel attacks, where an attacker observes their physical behavior to learn information about the manipulated secrets. The evaluation of the resilience of products against such attacks is mandatory to ensure the robustness of the embedded cryptography. In this thesis, we exhibit a methodology to efficiently evaluate the success rate of side-channel attacks, without the need to actually perform them. In particular, we build upon a paper written by Rivainin 2009, and exhibit explicit formulaes allowing to accurately compute the success rate of high-order side-channel attacks. We compare this theoretical approach against practical experiments. This approach allows for a quick assessment of the probability of success of any attack based on an additive distinguisher. We then tackle the issue of countermeasures against side- channel attacks. To the best of our knowledge, we study for the first time since the seminal paper of Ishai, Sahai and Wagner in 2003 the issue of the amount of randomness in those countermeasures. We improve the state of the art constructions and show several constructions and bounds on the number of random bits needed to securely perform the multiplication of two bits. We provide specific constructions for practical orders of masking, and prove their security and optimality. Finally, we propose a protocolallowing for the private computation of a secure veto among an arbitrary large number of players, while using a constant number of random bits. Our construction also allows for the secure multiplication of any number of elements of a finite field.

Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.

Many systems contain sensitive data such as user credentials used for authentication purposes. For large systems, a common approach is to store the data in a configuration file at a trusted third party. However, that would imply a single point of failure if an adversary gains access to the trusted party. In theory this could be solved by encrypting the data but in practice this only moves the problem and does not solve it, since some type of credential data is needed to decrypt the configuration file. A more flexible solution is needed that requires less of human interaction while also providing a higher degree of security. This thesis proposes a complete cryptographical system for solving this problem in a typical enterprise setting with a set of additional implementation requirements by using multi-party computation and Shamir's secret sharing protocol. Additionally, the work combines the mentioned system with a certificateless cryptography based multi-party computation protocol, since certificates usually implies a time-consuming process. The system has been evaluated in terms of security and efficiency with the conclusion that the results look promising. In terms of performance, the bulk of the overhead comes from certificateless cryptography, a constraint for the specific scenario which might not be present in general. The work also provides incentives for developing and further evolving Java libraries for cryptography, especially for multi-party computation and certificateless cryptography. / Många system innehåller känslig data, exempelvis användaruppgifter som används för autentiseringsändamål. För stora system är en vanlig lösning att lagra data i en konfigurationsfil hos en betrodd tredje part. Det skulle emellertid innebära att den svagaste länken är om motståndare får tillgång till den betrodda parten. I teorin kan detta lösas genom att kryptera data men i praktiken flyttar det bara på problemet men löser det inte, eftersom någon typ av autentiseringsdata behövs för att dekryptera konfigurationsfilen. En mer flexibel lösning behövs som kräver mindre mänsklig interaktion samtidigt som det ger en högre grad av säkerhet. Denna avhandling föreslår ett komplett kryptografiskt system för att lösa detta problem i en typisk företagsmiljö med en ytterligare uppsättning implementationskrav genom att använda multipartsberäknande och Shamirs secret sharing protokoll. Dessutom kombinerar arbetet det nämnda systemet med ett certifikatfritt krypteringsbaserat protokoll kombinerat med multipartsberäkningar, eftersom certifikat oftast innebär en tidskrävande process. Systemet har utvärderats med avseende på säkerhet och effektivitet med slutsatsen att det ser lovande ut. När det gäller prestanda kommer huvuddelen av omkostnaden från den certifikatfria kryptografin, en begränsning för det specifika scenariot som kanske inte är närvarande i allmänhet. Arbetet ger också motiv för att vidareutveckla Java-bibliotek för kryptografi, speciellt för multipartsberäknande protokoll och certifikatlös kryptering.

Secure multi-party computation (secure MPC) has been established as the de facto paradigm for protecting privacy in distributed computation. One of the earliest secure MPC primitives is the Shamir's secret sharing (SSS) scheme. SSS has many advantages over other popular secure MPC primitives like garbled circuits (GC) -- it provides information-theoretic security guarantee, requires no complex long-integer operations, and often leads to more efficient protocols. Nonetheless, SSS receives less attention in the signal processing community because SSS requires a larger number of honest participants, making it prone to collusion attacks. In this dissertation, I propose an agent-based computing framework using SSS to protect privacy in distributed signal processing. There are three main contributions to this dissertation. First, the proposed computing framework is shown to be significantly more efficient than GC. Second, a novel game-theoretical framework is proposed to analyze different types of collusion attacks. Third, using the proposed game-theoretical framework, specific mechanism designs are developed to deter collusion attacks in a fully distributed manner. Specifically, for a collusion attack with known detectors, I analyze it as games between secret owners and show that the attack can be effectively deterred by an explicit retaliation mechanism. For a general attack without detectors, I expand the scope of the game to include the computing agents and provide deterrence through deceptive collusion requests. The correctness and privacy of the protocols are proved under a covert adversarial model. Our experimental results demonstrate the efficiency of SSS-based protocols and the validity of our mechanism design.

資訊安全的研究裡，運用安全多方計算的方法，可使得多方在不洩漏各自私有資訊的條件下完成某種函式的計算。其中一種做法是利用scalar product來當作計算的基礎演算邏輯單元，並進而建構其他更複雜的安全多方計算。 根據目前現有的安全多方運算協定，可再加以定義出一些基本的運算規則，像是一般的程式語言中常用到的變數型態，如整數、浮點數、布林值，我們可定義出安全的秘密資料形態來，並且要能達到算數計算就必須擁有數值處理的能力，如基本的四則運算等，所以提供了相關聯的安全計算協定。根據安全多方計算的運算平台，可具有處理算術計算的能力，使得可處理一般安全計算的問題。 我們並提供一個script轉譯工具，使得使用者可自行撰寫自己的安全多方計算程式，並可利用此工具來自動將使用者寫的程式碼轉成安全多方運算平台可接受的程式碼，如此一來，解決安全多方計算的問題將會變得更為容易。 / 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. This thesis concerns the implementation SMC using of a set of information theoretically secure protocols based on scalar product protocol. This main characteristic of this approach is taking the scalar product computation as the basic building, and then use it to construct more complex computation protocols. 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. Besides, to ease the writing of more complex user-defined protocols, we developed a simple scripting language and a translation tool that converts user script code to SMC code, which is code composed of the building blocks we developed.

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.