Multiparty computation is a computation between multiple players which want to compute a common function based on private input. It was first proposed over 20 years ago and has since matured into a well established science. The goal of this thesis has been to develop efficient protocols for different operations used in multiparty computation and to propose uses for multiparty computation in real world systems. This thesis therefore gives the reader an overview of multiparty computation from the simplest primitives to the current state of software frameworks for multiparty computation, and provides ideas for future applications. Included in this thesis is a proposed model of multiparty computation based on a model of communication complexity. This model provides a good foundation for the included papers and for measuring the efficiency of multiparty computation protocols. In addition to this model, a more practical approach is also included, which examines different secret sharing schemes and how they are used as building blocks for basic multiparty computation operations. This thesis identifies five basic multiparty computation operations: sharing, recombining, addition, multiplication and negation, and shows how these five operations can be used to create more complex operations. In particular two operations “less-than” and “bitwise decomposition” are examined in detail in the included papers. “less-than” performs the “<” operator on two secret shared values with a secret shared result and “bitwise decomposition” takes a secret shared value and transforms it into a vector of secret shared bitwise values. The overall goal of this thesis has been to create efficient methods for multiparty computation so that it might be used for practical applications in the future.

Despite being a relatively young field, cryptography taught us how to perform seemingly-impossible tasks, which now became part of our everyday life. One of them is secure multiparty computation (MPC), which allows mutually distrustful parties to jointly perform a computation on their private inputs, so that each party only learns its prescribed output, but nothing else. In this work we deal with two longstanding challenges of MPC: adaptive security and deniability (or, incoercibility). A protocol is said to be adaptively secure, if it still guarantees security for the remaining honest parties, even if some parties turn dishonest during the execution of the protocol, or even after the execution. (In contrast, statically secure protocols give security guarantees only when the set of dishonest parties is fixed before the execution starts.) While adaptive security threat model is often more realistic than the static one, there is a huge gap between efficiency of statically and adaptively secure protocols: adaptively secure protocols often require more complicated constructions, stronger assumptions, and more rounds of interaction. We improve in efficiency over the state of the art in adaptive security for a number of settings, including the first adaptively secure MPC protocol in constant number of rounds, under assumptions comparable to those of static protocols (previously known protocols required as many rounds of interaction as the depth of the circuit being computed). The second challenge we deal with is providing resilience in the situation where an external coercer demands that participants disclose their private inputs and all their secret keys - e.g. via threats, bribe, or court order. Deniable (or, incoercible) protocols allow coerced participants to convincingly lie about their inputs and secret keys, thereby still maintaining their privacy. While the concept was proposed more than twenty years ago, to date secure protocols withstanding coercion of all participants were not known, even for the simple case of encryption. We present the first construction of such an encryption scheme, and then show how to combine it with adaptively secure protocols to obtain the first incoercible MPC which withstands coercion of all parties.

Smartphones are rapidly becoming a widespread computation platform, with many users relying on their mobile devices as their primary computing device. This popularity has brought about a plethora of mobile applications and services which are designed to efficiently make these limited devices a viable source of entertainment and productivity. This is commonly accomplished by moving the critical application computation to a Cloud or application server managed by the application developer. Unfortunately, the significant number of breaches experienced by mobile application infrastructure and the accompanying loss of private user data indicates the need for stronger security and privacy guarantees before this model of computation can become ubiquitous. The cryptographic community has developed the field of secure multiparty computation (SMC) to allow applications to perform computation over encrypted data. Such a protocol would allow mobile users to keep their private information encrypted while still enjoying the convenience of their Cloud based applications. However, while SMC protocols have seen significant advances in efficiency on desktop and server class machines, they currently require more computation power and memory than is available on commodity smartphones. Furthermore, even as smartphone computational power increases, the mobile-specific limitations of network bandwidth and power usage will always stand as barriers to efficiently executing SMC protocols. This dissertation develops techniques for outsourcing the costly operations in garbled circuit SMC protocols to an untrusted Cloud to allow resource-constrained devices to use this cryptographic primitive. By providing the mobile device with a third party Cloud provider, we show that it is possible for a mobile device to execute a garbled circuit with an application server at approximately the same efficiency as the same computation run between two server class machines. We first show two protocols for outsourcing the garbled circuit evaluation and generation. We develop a novel outsourced oblivious transfer (OOT) protocol to make this type of outsourcing possible. Second, we develop a black box technique for outsourcing any two-party SMC protocol, and show that the overhead incurred by outsourcing is minimal. Finally, we develop a protocol for outsourcing SMC that pro- vides both input privacy and circuit privacy, preventing the assisting Cloud from learning anything about the computation besides the fact that it took place. Through the protocols and the empirical evaluations in this dissertation, we show that executing SMC protocols on mobile devices can be done with comparable efficiency to the desktop platform, and provide techniques to allow for such computation using the latest developments in secure computation.

<div> <div> <div> <p>Organizations today collect and aggregate huge amounts of data from individuals under various scenarios and for different purposes. Such aggregation of individuals’ data when combined with techniques of data analytics allows organizations to make informed decisions and predictions. But in many situations, different portions of the data associated with individuals are collected and curated by different organizations. To derive more accurate conclusions and predictions, those organization may want to conduct the analysis based on their joint data, which cannot be simply accomplished by each organization exchanging its own data with other organizations due to the sensitive nature of data. Developing approaches for collaborative privacy-preserving data analytics, however, is a nontrivial task. At least two major challenges have to be addressed. The first challenge is that the security of the data possessed by each organization should always be properly protected during and after the collaborative analysis process, whereas the second challenge is the high computational complexity usually accompanied by cryptographic primitives used to build such privacy-preserving protocols. </p><p><br></p><p> </p><div> <div> <div> <p>In this dissertation, based on widely adopted primitives in cryptography, we address the aforementioned challenges by developing techniques for data analytics that not only allow multiple mutually distrustful parties to perform data analysis on their joint data in a privacy-preserving manner, but also reduce the time required to complete the analysis. More specifically, using three common data analytics tasks as concrete examples, we show how to construct the respective privacy-preserving protocols under two different scenarios: (1) the protocols are executed by a collaborative process only involving the participating parties; (2) the protocols are outsourced to some service providers in the cloud. Two types of optimization for improving the efficiency of those protocols are also investigated. The first type allows each participating party access to a statistically controlled leakage so as to reduce the amount of required computation, while the second type utilizes the parallelism that could be incorporated into the task and pushes some computation to the offline phase to reduce the time needed for each participating party without any additional leakage. Extensive experiments are also conducted on real-world datasets to demonstrate the effectiveness of our proposed techniques.<br></p> <p> </p> </div> </div> </div> </div> </div> </div>

The number of opportunities for cooperative computation has exponentially been increasing with growing interaction via Internet technologies. These computations could occur between trusted partners, between partially trusted partners, or even between competitors. Most of the time, the communicating parties may not want to disclose their private data to the other principal while taking the advantage of collaboration, hence concentrating on the results rather than private and perhaps useless data values. For performing such computations, one party must know inputs from all the participants / however if none of the parties can be trusted enough to know all the inputs, privacy will become a primary concern. Hence the techniques for Secure Multiparty Computation (SMC) are quite relevant and practical to overcome such kind of privacy gaps. The subject of SMC has evolved from earlier solutions of combinational logic circuits to the recent proposals of anonymity-enabled computation. In this thesis, we put together the significant research that has been carried out on SMC. We demonstrate the concept by concentrating on a specific technique called Oblivious Polynomial Evaluation (OPE) together with concrete examples. We put critical issues, challenges and the level of adaptation achieved before the researchers. We also provide some future research opportunities based on the literature survey.

In todays heterogeneous network environment, there is a growing demand for distrusted parties to jointly execute distributed algorithms on private data whose secrecy needed to be safeguarded. Platforms that support such computation on image processing purposes are called secure image processing protocols. In this thesis, we propose a new security model, called quasi information theoretic (QIT) security. Under the proposed model efficient protocols on two basic image processing algorithms linear filtering and thresholding are developed. For both problems we consider two situations: 1) only two parties are involved where one holds the data and the other possesses the processing algorithm; 2) an additional non-colluding third party exists. Experiments show that our proposed protocols improved the computational time significantly compared with the classical cryptographical couterparts as well as providing reasonable amount of security as proved in the thesis

<p>Research in engineering design assumes that data flows smoothly among different designers within a product realization process. This assumption is not valid in many scenarios, including when designers partner with a future competitor or when designers search for potential collaborators is hampered by an inability to share sensitive data. This information asymmetry among designers has an adverse effect on the outcomes of the product realization process. Designers need a secure yet collaborative design process that enables them to overcome these information-related risks borne from collaborators participating in their product realization process. Existing cryptographic techniques aimed at overcoming these risks are computationally intensive, making them unsuitable for heavy engineering computations such as finite element analysis (FEA). FEA is a widely used computation technique in several engineering applications, including structural analysis, heat transfer, and fluid flow. In this work, we developed a new approach, secure finite element analysis (sFEA), using which designers can perform their analysis without revealing their confidential design data to anyone, including their design collaborators even though the computed answer depends on confidential inputs from all the collaborators. sFEA is a secure, scalable, computationally lightweight, and cloud-compatible. In addition to sFEA, we developed prototypes and demonstrated that the computational framework within sFEA is general enough to be applied to different stages of the product realization process.</p>

<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>

Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-06-22T17:04:20Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Utilizando o Protocolo Bitcoin para Condução de Computações Multilaterais Seguras e Justas.pdf: 1665447 bytes, checksum: 2ff437be55e080c80d97e0d6582cb360 (MD5) / Made available in DSpace on 2016-06-22T17:04:20Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Utilizando o Protocolo Bitcoin para Condução de Computações Multilaterais Seguras e Justas.pdf: 1665447 bytes, checksum: 2ff437be55e080c80d97e0d6582cb360 (MD5) Previous issue date: 2016-02-02 / Suponha que dois milionários desejam descobrir quem é o mais rico sem que, para isso, um descubra o valor da fortuna do outro. Esse problema pode ser facilmente resolvido se ambos concordarem sobre um juiz a quem eles possam confiar a tarefa de calcular a resposta sem quebrar a privacidade de nenhum dos dois. O desafio, no entanto, é substituir esse juiz por uma interação multilateral, ou protocolo, que alcance o mesmo grau de segurança. Isso significa conduzir uma computação multilateral segura. Esse exemplo é conhecido como o problema dos milionários de Yao e foi proposto por Andrew Yao em um dos primeiros esforços para desenvolver uma forma geral de se conduzir computações multilaterais seguras. Desde lá, na década de 1980, vários avanços foram feitos nesse sentido e, hoje, já é um resultado bem estabelecido que qualquer função multilateral pode ser computada de maneira segura. Esse importante resultado, no entanto, vem com uma importante ressalva: a justiça não pode ser alcançada de maneira geral. Entende-se por justiça a garantia de que, no final de uma computação, ou todos os participantes recebem suas respostas ou nenhum deles recebe. Motivadas por esse resultado de impossibilidade, várias definições alternativas de justiça foram concebidas. Uma delas considera uma computação como sendo justa se os participantes que agirem desonestamente forem monetariamente penalizados. Ou seja, se alguns participantes receberem o resultado da computação e privarem os demais de receberem, então esse conluio é penalizado e os demais participantes, compensados. Com essa definição, uma computação justa pode ser vista como o cumprimento de um contrato, no qual cada participante se compromete a agir honestamente ou a pagar uma multa. Sob essa perspectiva, trabalhos recentes mostram como criptomoedas podem ser utilizadas para escrever esses contratos e, portanto, servir para condução de computações multilaterais seguras e monetariamente justas. Uma criptomoeda é um sistema monetário que se baseia em princípios criptográficos para alcançar segurança e controlar a taxa de emissão de novas moedas. O Bitcoin, criado em 2008 por Satoshi Nakamoto, foi a primeira realização dessa ideia. Ele se baseia em uma estrutura de dados pública chamada blockchain, que armazena o histórico de todas as transações já realizadas. A segurança da blockchain, incluindo sua não-maleabilidade, é garantida pela dificuldade da prova de trabalho exigida para que novas informações sejam adicionadas nessa estrutura. Cada transferência de moedas no Bitcoin é feita de maneira que um usuário só pode recebê-las mediante a apresentação de uma entrada que satisfaça um script especificado pelo remetente. Contratos escritos através desses scripts se fazem cumprir sem a necessidade de intervenção de uma parte confiável externa. Essa característica é o que faz o Bitcoin ser adequado e atrativo para se conferir justiça para computações multilaterais seguras. Um dos nossos objetivos neste trabalho é a realização de um estudo sobre os resultados que permitem a computação segura de uma função qualquer e dos que estabelecem a impossibilidade de se alcançar justiça de maneira geral. Tentaremos manter o rigor matemático para evitar uma apresentação estritamente panorâmica. Além disso, analisaremos criticamente uma construção proposta para utilizar o Bitcoin como plataforma para condução de computações multilaterais seguras e justas. Por fim, a partir dos pontos positivos e negativos levantados, apresentaremos uma proposta nossa com a mesma finalidade. / Suppose that two millionaires want to find out which one is the richest, but without revealing how much their fortunes are worth in the process. This problem can be easily solved if they trust a judge to compute the desired answer without compromising their privacy. The challenge, however, is to replace such a judge by a multiparty interaction, or protocol, that achieves the same level of security. That is, the challenge is to carry out a secure multiparty computation. The previous example is known as Yao’s millionaires’ problem and was stated by Andrew Yao in one of the first efforts to develop a general algorithm to carry out secure multiparty computations. Since then, in the 1980s, several advances were made to achieve this goal and, nowadays, it is a well-established result that any multiparty function can be securely computed. This important result, however, comes with an important restriction: fairness cannot be achieved in general. Fairness is the guarantee that, at the end of a computation, either all parties receive their outputs or none of them does. Motivated by this impossibility, several alternative definitions of fairness have been proposed. One of them considers a computation to be fair if the dishonest parties are monetarily penalized and the honest ones are monetarily compensated. According to this definition, a fair computation can be viewed as the enforcement of a contract, in which the parties agree on paying a penalty if they misbehave. Recent works have shown how cryptocoins can be used to write those contracts and, therefore, to be used for carrying out secure and monetarily fair multiparty computations. A cryptocoin is a monetary system that relies on cryptographic principles for achieving security and controlling the coin issuing rate. Bitcoin, created in 2008 by Satoshi Nakamoto, was the first practical realization of this idea. In its core, there is a publicly maintained data structure called blockchain, which works as a ledger and stores every transaction ever made. The security of the blockchain, including its non-malleability, is guaranteed by the difficulty of the proof of work required to add new data to it. A Bitcoin transaction can only be redeemed by a user that presents an input satisfying a script specified by the issuer of the transaction. Contracts written on these scripts are enforced without an external trusted third-party to intervene. This makes Bitcoin suitable and interesting to confer monetary fairness to multiparty computations. One of the goals of this work is to present the results that allow any function to be securely computed and the ones that show the impossibility of achieving fairness in general. We will try to present these results with the appropriate mathematical rigor to avoid giving just an overview of them. We will also analyze a recently proposed construction that uses Bitcoin as a platform to carry out fair multiparty computations. Finally, based on its positive and negative points, we will propose a construction with the same goal.

<div>Multiparty computation refers to a scenario in which multiple distinct yet connected parties aim to jointly compute a functionality. Over recent decades, with the rapid spread of the internet and digital technologies, multiparty computation has become an increasingly important topic. In addition to the integrity of computation in such scenarios, it is essential to ensure that the privacy of sensitive information is not violated. Thus, secure multiparty computation aims to provide sound approaches for the joint computation of desired functionalities in a secure manner: Not only must the integrity of computation be guaranteed, but also each party must not learn anything about the other parties' private data. In other words, each party learns no more than what can be inferred from its own input and its prescribed output.</div><div><br></div><div> This thesis considers secure two-party computation over arithmetic circuits based on additive secret sharing. In particular, we focus on efficient and secure solutions for fundamental functionalities that depend on the equality of private comparands. The first direction we take is providing efficient protocols for two major problems of interest. Specifically, we give novel and efficient solutions for <i>private equality testing</i> and multiple variants of <i>secure wildcard pattern matching</i> over any arbitrary finite alphabet. These problems are of vital importance: Private equality testing is a basic building block in many secure multiparty protocols; and, secure pattern matching is frequently used in various data-sensitive domains, including (but not limited to) private information retrieval and healthcare-related data analysis. The second direction we take towards a performance improvement in equality-based secure two-party computation is via introducing a generic functionality-independent secure preprocessing that results in an overall computation and communication cost reduction for any subsequent protocol. We achieve this by providing the first precise functionality formulation and secure protocols for replacing original inputs with much smaller inputs such that this replacement neither changes the outcome of subsequent computations nor violates the privacy of sensitive inputs. Moreover, our input-size reduction opens the door to a new approach for efficiently solving Private Set Intersection. The protocols we give in this thesis are typically secure in the semi-honest adversarial threat model.</div>