Efficient protocols for joint random number generation using multi-party computation techniques: Efficiente protocollen voor het genereren van samenhangende random getallen voor groepsberekeningen
There exists several applications where it is desirable to produce random numbers such that adding these random numbers yields a publicly known sum. Efficient algorithms are necessary for generating such joint random numbers in an untrusted environment in settings such as, but not restricted to, multi-party computation (MPC). Applications range all the way to secure license plate identification or facial recognition. In this thesis, we give a brief introduction into the field of cryptography. Then, we focus on a core component in MPC protocols, namely on how to generate these joint random numbers. We first analyze the existing work. Then, we propose two new protocols to efficiently achieve joint random number generation, both in terms of computational demand and communication. We show that our second protocol can also omit the need for secure networks, meaning all the messages can be public. In addition to these protocols we also introduce an extension for general joint random number generation protocols in large networks based on a star topology, with explicit protocols for parties that are joining or leaving. We analyze all our proposals in terms of security, complexity and performance. Finally, we discuss questions that remain open after this thesis.
There exists several applications where it is desirable to produce random numbers such that adding these random numbers yields a publicly known sum. Efficient algorithms are necessary for generating such joint random numbers in an untrusted environment in settings such as, but not restricted to, multi-party computation (MPC). Applications range all the way to secure license plate identification or facial recognition. In this thesis, we give a brief introduction into the field of cryptography. Then, we focus on a core component in MPC protocols, namely on how to generate these joint random numbers. We first analyze the existing work. Then, we propose two new protocols to efficiently achieve joint random number generation, both in terms of computational demand and communication. We show that our second protocol can also omit the need for secure networks, meaning all the messages can be public. In addition to these protocols we also introduce an extension for general joint random number generation protocols in large networks based on a star topology, with explicit protocols for parties that are joining or leaving. We analyze all our proposals in terms of security, complexity and performance. Finally, we discuss questions that remain open after this thesis.
In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.
Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite fields. We are motivated by two limitations of these techniques: – Generality. Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). – Efficiency. The best known constant-round protocols do not efficiently scale even to the case of large finite fields. Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite ring, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a black-box access to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function. 1
MPC is a primitive which allows for mutually distrusting parties to jointly compute the output of a function over their private inputs. This technology has many practical applications and, as such, has seen extensive research, which has generated several different methods for achieving MPC. In this thesis, we discuss and expand on three of the best known methods for achieving MPC. The first is based on Shamir's secret sharing scheme. We present a novel secret sharing based scheme which achieves MPC under the following constraints. We allow for a malicious adversary that can arbitrarily delay any parties for a number of rounds. While these parties are delayed they can neither send nor receive messages. Furthermore, we assume that all messages between the parties are sent via a set of central parties called Relays. We provide a UC functionality and protocol for the relays, and for the MPC protocol. The second is based on Yao's garbled circuits protocol. Here we expand on the row reduction technology already present in maliciously secure two party garbled circuits and show how to achieve similar results in the multiparty setting. This reduces the number of ciphertexts that must be sent per AND gate in the multiparty Garbled Circuits setting from four to three. The third is based on Fully Homomorphic Encryption. The particular protocol we introduce expands the FINAL FHE scheme and expands it to accept multiple keys, which can then be used by different parties to collectively outsource a computation to an untrusted server. We cover the various different obstacles that needed to be overcome in this expansion, and we show that our protocol has an asymptotic improvement in the efficiency of the bootstrapping over other multi-key FHE schemes. This now requires a number of polynomial multiplications which is linear in the number parties, rather than quadratic.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t l n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t l n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t < n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t < n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
In this work we formalize the notion of a two-party permutation correlation (A,B),(C,π) s.t. π(A)=B+C for a random permutation π of n elements and vectors A,B,C∈Fn . This correlation can be viewed as an abstraction and generalization of the Chase et al. (Asiacrypt 2020) share translation protocol. We give a systematization of knowledge for how such a permutation correlation can be derandomized to allow the parties to perform a wide range of oblivious permutations of secret-shared data. This systematization immediately enables the translation of various popular honest-majority protocols to be efficiently instantiated in the two-party setting, e.g. collaborative filtering, sorting, database joins, graph algorithms, and many more. We give two novel protocols for efficiently generating a random permutation correlation. The first uses MPC-friendly PRFs to generate a correlation of n elements, each of size ℓ=log∣F∣ bits, with O(nℓ) bit-OTs, time, communication, and only 3 rounds including setup. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for n=220,ℓ=128 requires just 7 s & ∼2ℓn bits of communication, a respective 40 & 1.1× improvement on the LWE solution of Juvekar at al. (CCS 2018). The second protocol is based on pseudo-random correlation generators and achieves an overhead that is sublinear in the string length ℓ , i.e. the communication and number of OTs is O(nlogℓ) . The overhead of the latter protocol has larger hidden constants, and therefore is more efficient only when long strings are permuted, e.g. in graph algorithms. Finally, we present a suite of highly efficient protocols based on permutations for performing various batched random access operations. These include the ability to extract a hidden subset of a secret-shared list. More generally, we give ORAM-like protocols for obliviously reading and writing from a list in a batched manner. We argue that this suite of batched random access protocols should be a first class primitive in the MPC practitioner’s toolbox.(The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ .)