Master of Science / In a world with ever greater need for machine learning and artificial intelligence, it has be- come increasingly important to offload computation intensive tasks to companies with the compute resources to perform training on potentially sensitive data. In applications such as finance or healthcare, the data providers may have a need to train large quantities of data, but cannot reveal the data to outside parties for legal or other reasons. Originally, using a decentralized training method known as Federated Learning (FL) was proposed to ensure data did not leave the client's device. This method still was susceptible to attacks and further security was needed. Multi-Party Computation (MPC) was proposed in conjunction with FL as it provides a way to securely compute with no leakage of data values. This was utilized in a framework called SAFEFL, however, it was extremely slow. Reducing the computation overhead using programming tools at our disposal for this frame- work turns it from a unpractical to useful design. The design can now be used in industry with some overhead compared to non-MPC computing, however, it has been greatly im- proved.

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 (MPC) is a field of cryptography that aims to provide methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike of traditional cryptography where adversary is outside the system of participants, the main task (and challenge) of MPC is to protect participants from internal adversaries, who participate in protocol and can therefore send corrupted. The results presented in this thesis are three-fold. First, we study MPC from a theoretical standpoint, designing a new heuristic and a new proof system useful for proving the security of threshold signatures, a particular kind of MPC protocol. Next, we present new MPC primitives: a novel secret sharing scheme, a threshold version of Schnorr signature, a post quantum secure group action based threshold signature and finally a post quantum oblivious transfer. Lastly, we designed a coercion resistant e-voting protocol, that allows voters to freely votes without being afraid of external adversaries trying to pressure them to vote in a particular way.

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.