Private Information, Uses and Misuses

In a modern information-driven society, the everyday life of individuals and companies is full of cases where various kinds of private information are important resources. While a cryptographer might think of PIN codes and keys in this context, these types of secrets are not our main concern here. Rather, we will talk about information that is closer to the primary business of an individual or a company. For a private person, this may be data concerning his or her economic situation, such as income, loans, and tax data, or information about his or her health, such as diseases and medicine usage. For a company, it might be the customer database or information on how the business is running, such as turnover, profits, and salaries.

What is a viable strategy for handling private information? Finding a good answer to this question has become more complicated in recent years. When computers were in their infancy, in the 1950s and 1960s, electronic information security was to a large extent a military business. A military organization is quite special in that confidential information needs to be communicated almost exclusively between its own members, and the primary security goal is to protect this communication from being leaked to external enemies. While it may not be trivial to reach this goal, at least the overall purpose is simple to state and understand.

In modern society, things get much more complicated: using electronic media, we need to interact and do business with a large number of parties, some of whom we have never met and many of whom may have interests that conflict with ours. So how do you handle your confidential data if you cannot be sure that the parties you interact with are trustworthy?

One could save the sensitive data in a very secure location and never access it, but this is, of course, unreasonable. Our private data usually have value only because we want to use them for something. In other words, we have to have ways of controlling leakage of confidential data while these data are being stored, communicated, or computed on, even in cases where the owner of the data does not trust the parties he or she communicates with.

Introduction

In this chapter we will show how the protocols we have seen so far can be generalized to be based on general linear secret-sharing schemes. Doing this generalization has several advantages: first, it allows us to design protocols that protect against general adversary structures, a concept we explain later, and second, it allows us to consider protocols in which the field that is used in defining the secret-sharing scheme can be of size independent of the number of players. This turns out to be an advantage for the applications of multiparty computation (MPC) that we consider later but cannot be done for the protocols that we have seen so far: to use Shamir's scheme for n players based on polynomials as we have seen, the field must be of size at least n+1.

For now, we will only consider the theory for linear secret sharing that we need to construct the protocols in this chapter. However, we note already that to get full mileage from the more general applications of secret sharing and MPC, we need additional theory, in particular, about the asymptotic behavior of secret-sharing schemes. This material can be found in Chapter 11.

General Adversary Structures

The corruption tolerance of the protocols that we have seen so far has been characterized by only a single number t, the maximal number of corruptions that can be tolerated. This is also known as the threshold-t model. One way to motivate this might be to think of corruption of a player as something that requires the adversary to invest some amount of resource, such as time or money. If the adversary has only bounded resources, there should be a limit on the corruptions he or she can do. However, characterizing this limit by only an upper bound implicitly assumes that all players are equally hard to corrupt. In reality, this may be completely false: some players may have much better security than others, so a more realistic model might be that the adversary can corrupt a small number of well-protected players or a large number of poorly protected players. However, the threshold model does not allow us to express this.

Introduction

Throughout, the reader is assumed to already have a good (working) knowledge of basic undergraduate algebra. For ease of reference, we shall first recall some central definitions and useful elementary results concerning groups, rings, fields, modules, vector spaces, and algebras. For additional basic theory, full details and more, please refer, for example, to Serge Lang's Algebra [126].

Furthermore, at some points we shall need some results from field theory and algebraic number theory, as well as from multilinear algebra, specifically concerning cyclotomic number fields and tensor products. In each of these cases we shall give a brief introduction and state the required results. For full details and more, please refer to references 125, 126, 127. Our exposition of these topics (loosely) follows Lang [126], except where stated otherwise.

Finally, we shall need results from the theory of algebraic function fields (in one variable) over finite fields, that is, algebraic curves over finite fields. This is deferred to Section 12.7. Specifically, the focus there will be on families of curves with asymptotically many rational points. We will give a bird's-eye introduction to this topic that is self-contained in that it assumes as background only the material on basic algebra covered earlier on. For a full treatment of the basic theory of algebraic function fields, as well as such results as the ones referred to earlier, we refer to Henning Stichtenoth's Algebraic Function Fields and Codes [172]. Except when stated differently, our exposition follows Stichtenoth [172], specifically parts of Chapters 1, 3, 5, and 7. Full proofs are mostly beyond the scope of this introduction. Sometimes a sketch is given. Yet we shall state all results needed for our purposes.

Basic definitions and results that are covered in full detail by most standard introductory textbooks are mentioned without reference (but sometimes a proof is given). In case we suspect that a result we quote is not so easy to look up elsewhere in full detail (say, if it is disguised as a special case of more advanced theory or hidden in exercises), we give an explicit reference to a suitable text.

In a few places in the text we will give appropriate references when discussing certain specific (advanced) algorithmic aspects.

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.

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.

Introduction

We introduce the notion of an arithmetic codex [43, 57], or codex for short, and develop its basic theory. Codices encompass several well-established notions from cryptography (various types of arithmetic secret-sharing schemes, which all enjoy additive as well as multiplicative properties) and from algebraic complexity (bilinear complexity of multiplication in algebras) in a single mathematical framework. Arithmetic secret-sharing schemes have important applications to secure multiparty computation (MPC) and even to two-party cryptography. One such application, known as “MPC-in-the-head,” can be found in Chapter 8.

Interestingly, several recent applications to two-party cryptography (including the one we present in this book) rely crucially on the existence of certain asymptotically good schemes. It is intriguing that their construction requires asymptotically good towers of algebraic function fields over a finite field: no elementary (probabilistic) constructions are known in these cases. Besides introducing the notion, we discuss some of the constructions, as well as some limitations.

Throughout this chapter, let K be a field, let p > 0 be a prime number, let v be a positive integer, and define q=pv. Let Fq be a finite field with q elements.

The Codex Definition

For our purposes, a K-algebra is a commutative ring such that K is a subring (see Section 10.8). By definition of a subring, the multiplicative unity of a K-algebra is precisely the multiplicative unity of K. It is henceforth denoted by 1. Recall that a K-algebra is in particular a K-vector space.

Powers of a Space

Taking powers of a subspace of a K-algebra R plays a fundamental role in the definition and study of codices. Suppose that C ⊂ R is a K-vector subspace of R, with R viewed as a K-vector space. In general, of course, the space C is not closed under multiplication. For example, take R = K[X], the polynomial ring over K, and let C be the subspace of polynomials of degree ≤ t for some positive integer t.

We define, for each positive integer d, the “closure” of C under “d-multiplication” as the subspace C∗d ⊂ R generated by the elements of R that can be written as a product of d elements selected from C. Formally, we have the following:

DEFINITION 12.1 (SET OF d-PRODUCTS) Let R be a K-algebra. Let C ⊂ R be a K-vector subspace. Let d≥ 0 be an integer.

This is a book on information theoretically secure multiparty computation (MPC) and secret sharing and about the intimate and fascinating relationship between the two notions. We decided to write this book because we felt that a comprehensive treatment of unconditionally secure techniques for MPC was missing in the literature. In particular, because some of the first general protocols were found before appropriate definitions of security had crystallized, proofs of those basic solutions have been missing so far.

We present the basic feasibility results for unconditionally secure MPC from the late 1980s, generalizations to arbitrary access structures using linear secret sharing, and a selection of more recent techniques for efficiency improvements. We also present our own simplified variant of the Universally Composable (UC) framework in order to be able to give complete and modular proofs for the protocols we present.

We also present a general treatment of the theory of secret sharing, in particular, secret-sharing schemes with additional algebraic properties, which is also a subject missing in textbooks. One of the things we focus on is asymptotic results for multiplicative secret sharing, which has various interesting applications that we present in the MPC part.

Our ambition has been to create a book that will be of interest to both computer scientists and mathematicians and can be used for teaching at several different levels. We have therefore tried to make Parts I and II self-contained units, even if this implies some overlap between the parts. This means that there are several different ways to read this book; we give a few suggestions in the following paragraphs. In particular, the concept of secret sharing, of course, appears prominently in both parts. In Part I, on MPC, however, it is introduced only as a tool on a “need-to-know” basis. In Part II, we reintroduce the notion, but as a general concept that is interesting in its own right and with a comprehensive treatment of the mathematical background.

This book is intended to be self-contained enough to be read by advanced undergraduate students, and the authors have used large parts of the material in the book for teaching courses at this level. By covering a selection of more advanced material, the book can also be used for a graduate course.

How to Use This Book

For a course on the advanced undergrad level for computer science students, we recommend covering Chapters 1 through 5.