In this chapter we will look at two different applications of information-theoretic multiparty computation (MPC), a practical application and a theoretical application. The example of a practical application is the use of MPC to clear a commodity derivative market. The focus will be on the algorithmic tricks used to implement the auction efficiently. The theoretical application is the use of MPC to realize so-called zero-knowledge proofs. A zero-knowledge proof is a way for a prover to convince a verifier about the validity of a statement without leaking any information on why the statement is true. This can be seen as an MPC problem with n = 2 parties. However, since the minimal requirement for information-theoretic MPC is that fewer than n /2 parties are corrupted, information-theoretic MPC does not seem to help in constructing zero-knowledge proofs. However, as we shall see, a technique sometimes called MPC in the head can be used to turn an efficient, secure MPC for a given relation into an efficient zero-knowledge proof for the same relation. A Double Auction In this section we look at a concrete application of MPC, with a main focus on the algorithmic tricks needed to efficiently do a secure auction. Along the way, we will look at how to efficiently and securely compare two integers secret shared among the parties. 9.1.1 Introduction The algorithmic techniques we will look at are fairly general, but it is instructive to view them in a practical context. We will look at how they have been used to clear the Danish market for contracts on sugar beets from 2008 and until the time of this writing. This was the first industrial application of MPC. More historical details on this can be found later and in the Notes section at the end of this chapter. In the economic field of mechanism design, the concept of a trusted third party has been a central assumption since the 1970s. The field has grown in momentum since it was initiated and has turned into a truly cross-disciplinary field. Today, many practical mechanisms require a trusted third party.
In this chapter we will look at two different applications of information-theoretic multiparty computation (MPC), a practical application and a theoretical application. The example of a practical application is the use of MPC to clear a commodity derivative market. The focus will be on the algorithmic tricks used to implement the auction efficiently. The theoretical application is the use of MPC to realize so-called zero-knowledge proofs. A zero-knowledge proof is a way for a prover to convince a verifier about the validity of a statement without leaking any information on why the statement is true. This can be seen as an MPC problem with n = 2 parties. However, since the minimal requirement for information-theoretic MPC is that fewer than n /2 parties are corrupted, information-theoretic MPC does not seem to help in constructing zero-knowledge proofs. However, as we shall see, a technique sometimes called MPC in the head can be used to turn an efficient, secure MPC for a given relation into an efficient zero-knowledge proof for the same relation. A Double Auction In this section we look at a concrete application of MPC, with a main focus on the algorithmic tricks needed to efficiently do a secure auction. Along the way, we will look at how to efficiently and securely compare two integers secret shared among the parties. 9.1.1 Introduction The algorithmic techniques we will look at are fairly general, but it is instructive to view them in a practical context. We will look at how they have been used to clear the Danish market for contracts on sugar beets from 2008 and until the time of this writing. This was the first industrial application of MPC. More historical details on this can be found later and in the Notes section at the end of this chapter. In the economic field of mechanism design, the concept of a trusted third party has been a central assumption since the 1970s. The field has grown in momentum since it was initiated and has turned into a truly cross-disciplinary field. Today, many practical mechanisms require a trusted third party.
Secure Multi-party Computation (MPC) considers the problem where a set of mutually distrusting parties want to jointly compute a function over their private inputs, without revealing any extra information about these inputs other than what it can be inferred from the output of the function. This setting is well-motivated, and it has many real-world applications such as auction, voting, etc. MPC can be also seen as a generalization of many natural cryptographic primitives. For example, zero-knowledge (ZK) can be viewed as a special case of two-party secure computation. In ZK, a party, called prover aims to convince a second party, called verifier, that the prover’s private input witness w and a public input statement x belong to a relation R. An important research direction in secure computation is to find the trade-off between the required setup (e.g., the use of the broadcast channel, the use of common reference string (CRS) / public key infrastructure (PKI), the upper bound of the parties that can be corrupted, etc.), and the security guarantees that can be achieved. The setups can be viewed as some general assumptions that the protocol needs to satisfy, and they influence the usability of the protocol in real-world scenarios. In principle, having simpler (or no) setups mean that the protocol is more general and can be more useful in real-world scenarios. At the same time, having simpler setups may lead to weaker security guarantees. Therefore, finding the trade-off between setup and security guarantees is important and meaningful. In this thesis, we target MPC and ZK, and we focus on how to minimize the setup for MPC and ZK while still providing meaningful levels of security. More specifically: Regarding MPC, we focus on the dishonest majority (i.e., the adversary can corrupt all but one party), and we aim at 1) minimizing the use of broadcast channels. 2) studying the MPC with pre-processing when no setup is available. • Informally, a broadcast channel guarantees that when a message is sent, this reaches all the parties, without ambiguity. It also guarantees that if an honest party receives a message from a corrupted party, then it is guaranteed that all the honest parties have received the message. To realize broadcast, parties in the protocol could run the broadcast protocol, which may require many rounds of peer-to-peer communications. An alternative way is to rely on physical or external infrastructure such as blockchain. In both cases, broadcast is expensive, as such, we want to minimize its use. In particular, this thesis presents the following results: – When assuming no setup, we give a complete characterization with respect to the use of broadcast channels, and we obtain the optimal results. – We consider the same problem for the case that we only want to allow the black-box use (i.e., do not have access to the code of the algorithm) of the oblivious transfer protocol. We also give a characterization. • In the standard definition of MPC, the parties’ private inputs are fixed before the start of the protocol. However, there is another type of MPC named MPC with pre-processing, where the protocol can pre-compute some messages without using parties’ inputs, and these messages can accelerate computations in the online phase (i.e., other computations that require parties’ inputs). Since some expensive computations can be pre-computed, the online phase could be more lightweight. Therefore, we want to remove the dependency of the input from as many rounds as possible, so that we can do some pre-processing. In this direction, we explore the protocol with no setup. We provide a compiler that can turn a big class of MPC protocol that may require the inputs already to compute the first round, into a new protocol that needs the inputs only in the last two rounds. We also propose new MPC definitions that capture this delayed-input features. Regarding ZK, we do the following: • In standard single-theorem ZK definition, the security of the ZK protocol is guaranteed to hold only when one proof is issued. In the case where multiple zero-knowledge proofs need to be issued (i.e., to prove multiple NP statements), each new zero-knowledge proof requires a freshly generated setup. In the multi-theorem ZK definition, instead, one setup is sufficient for generating multiple zero-knowledge proofs for multiple instances. We propose a multi-theorem protocol (in the format of a compiler) that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Prior works could achieve this adaptive security only inefficiently via NP reductions. • ZK protocols are secure only when all setups are correctly generated, but in real-world scenarios, some of the setups may not be correctly generated. For instance, to run a non-interactive zero-knowledge (NIZK) protocol, the setup CRS could be chosen with bias. In this case, the security of the NIZK protocol does not hold anymore. Instead of finding a secure ZK candidate, one alternative solution is to have multiple instantiations of ZK candidates and assume that only for a subset of them the setup is generated correctly. More formally, we consider the case where only a subset of the instances are secure. In more detail, given access to n candidate instantiations of a NIZK for some language, we want to have a construction that itself implements a NIZK for the same language without relying on any additional computational assumptions. We refer to this type of construction as combiner, and the combiner is secure assuming at least t of the given candidates are secure. In this work, we provide three different constructions of robust NIZK combiners and show that combiners are impossible to realize unless the majority of the input candidates are secure.
In the last few years the efficiency of secure multi-party computation (MPC) increased in several orders of magnitudes. However, this alone might not be enough if we want MPC protocols to be used in practice. A crucial property that is needed in many applications is that everyone can check that a given (secure) computation was performed correctly – even in the extreme case where all the parties involved in the computation are corrupted, and even if the party who wants to verify the result was not participating. This is especially relevant in the clients-servers setting, where many clients provide input to a secure computation performed by a few servers. An obvious example of this is electronic voting, but also in many types of auctions one may want independent verification of the result. Traditionally, this is achieved by using non-interactive zero-knowledge proofs during the computation.A recent trend in MPC protocols is to have a more expensive preprocessing phase followed by a very efficient online phase, e.g., the recent so-called SPDZ protocol by Damgård et al. Applications such as voting and some auctions are perfect use-case for these protocols, as the parties usually know well in advance when the computation will take place, and using those protocols allows us to use only cheap information-theoretic primitives in the actual computation. Unfortunately no protocol of the SPDZ type supports an audit phase.In this paper, we show how to achieve efficient MPC with a public audit. We formalize the concept of publicly auditable secure computation and provide an enhanced version of the SPDZ protocol where, even if all the servers are corrupted, anyone with access to the transcript of the protocol can check that the output is indeed correct. Most importantly, we do so without significantly compromising the performance of SPDZ i.e. our online phase has complexity approximately twice that of SPDZ.
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.
Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai et al., STOC '07) which use secure multiparty computation (MPC) protocols as the basis. Efficient instances of this paradigm have emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al., USENIX '16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.
In a data-driven society, individuals and companies encounter numerous situations where private information is an important resource. How can parties handle confidential data if they do not trust everyone involved? This text is the first to present a comprehensive treatment of unconditionally secure techniques for multiparty computation (MPC) and secret sharing. In a secure MPC, each party possesses some private data, while secret sharing provides a way for one party to spread information on a secret such that all parties together hold full information, yet no single party has all the information. The authors present basic feasibility results from the last 30 years, generalizations to arbitrary access structures using linear secret sharing, some recent techniques for efficiency improvements, and a general treatment of the theory of secret sharing, focusing on asymptotic results with interesting applications related to MPC.
Introduction In Chapter 1 we gave an introduction to the multiparty computation problem and explained what it intuitively means for a protocol to compute a given function securely, namely, we want a protocol that is correct and private. However, we only considered three players, we only argued that a single player does not learn more than he or she is supposed to, and finally, we assumed that all players would follow the protocol. In this chapter we will consider a more general solution to multiparty computation, where we remove the first two restrictions: we will consider any number n ≥ 3 of players, and we will be able to show that as long as at most t < n /2 of the players go together after the protocol is executed and pool all their information, they will learn nothing more than their own inputs and the outputs they were supposed to receive, even if their computing power is unbounded. We will still assume, however, that all players follow the protocol. This is known as semihonest or passive security . To argue security in this chapter, we will use a somewhat weak but very simple definition that only makes sense for semihonest security. We then extend this in Chapter 4 to a fully general model of what protocols are and what security means. Throughout this chapter we will assume that each pair of players can communicate using a perfectly secure channel, so if two players exchange data, a third player has no information at all about what is sent. Such channels might be available because of physical circumstances, or we can implement them relative to a computational assumption using cryptography. For more details on this, see Chapter 7. We end the chapter by showing that the bound t < n /2 is optimal: if t ≥ n /2, then some functions cannot be computed securely in the model mentioned, that is, obtaining perfect security by using only secure point-to-point communication as the communication resource. Secret Sharing Our main tool to build the protocol will be secret-sharing schemes. The theory of secret-sharing schemes is a large and interesting field in its own right with many applications to multiparty computation (MPC), and we look at this in more detail in Chapter 11, where a formal definition of the notion as well as a general treatment of the theory of secret sharing can be found.