We generate and gather a lot of data about ourselves and others, both willingly and unwillingly. Much of that data is considered confidential by someone, and its collection, storage and use are regulated by laws, contracts, societal norms or personal care. The restrictions on the use of data can limit the benefits we can obtain from its analysis, even if all the parties involved agree that it would be beneficial to learn the result of a certain computation applied to confidential data. Examples include the statistical analysis of personally identifiable information (PII) of a large number of people, where the results of a well-designed analysis can no longer be linked to a single person, or a small group of persons, but can be used as a basis for sound policy decisions. Examples also include the monitoring of critical infrastructure and reacting to changes in its status, where different parts of the infrastructure are owned by different entities afraid that their trade secrets might leak. Another example considers negotiations among several parties planning a cooperative activity, where the parties are reluctant to bring all the relevant facts to the negotiation table in fear of leaking their trade secrets and harming their position, but the lack of these facts may lead to a sub-optimal contract.

In all these examples, the parties would like to execute a specific program on their confidential data, and learn the outcome of the result, while making sure that nothing else about the data is leaked. There is cryptographic technology that is capable of providing the parties with exactly this functionality and guarantees. In secure multiparty computation (SMC), parties provide their inputs to a cryptographic protocol that is used to compute a pre-agreed function in such a manner that anything that a party or a sufficiently small coalition of parties sees during the protocol could be deduced from the party's or the coalition's inputs and outputs. SMC has been a subject of academic studies since the 1980s, when the first constructions were proposed and it was shown that any Boolean circuit could be securely evaluated with only a polynomial overhead. As it is possible to express any computation as a Boolean circuit (again, with only a polynomial overhead), it can also be performed securely. Since then, several different SMC techniques have appeared with different communication patterns, different numbers of parties they are able to support, different coalitions of adversarial parties they are able to tolerate, and different adversarial actions they can handle.

While SMC has been the subject of academic studies for more than 30 years, the first attempts to use it for actual computations only took place in the early 2000s. Indeed, though the first constructions of SMC were theoretically efficient, the constants hidden in their complexity measures were too large to render them practicable. The situation has steadily improved since then and by now, even relatively large computational tasks can be solved securely.

Academic research has concentrated on improving the times of securely executing Boolean circuits, or arithmetic circuits consisting of addition and multiplication gates. This makes a lot of sense from the theoretical point of view, as these operations are sufficient to express any computation with polynomial overhead. It is also advisable to use these operations when expressing certain combinatorial or numerical computation tasks as circuits. For many other kinds of computations, though, the cost of converting them into a circuit that only consists of additions and multiplications, together with the overheads of SMC, may be too much for practical applications. There have been relatively few research efforts to

• devise efficient SMC protocols for other operations, e.g. comparisons;

• efficiently combine the existing SMC protocols into secure protocols for other primitive operations used in algorithms, e.g. array access.

In our opinion, these are the advances that will encourage the take-up of SMC techniques in many different areas for many different tasks.

This book describes research, mostly performed over the last few years, that has brought forth these kind of advances. The results described show how certain algorithmic steps can be performed in a privacy-preserving manner, and how to combine these steps into larger privacy-preserving applications. We start this book with two chapters about fundamental SMC techniques. In Chapter 1, we describe the different kinds of protocols for SMC, and the ways they represent private data in a manner that prevents a small coalition from learning anything about the individual values. In Chapter 2 we discuss the composability of SMC protocols. For building large privacy-preserving applications, it is very important to ensure that the protocols can be composed freely or almost freely. Underlying the composability results is a very convenient abstraction of SMC — the ideal functionality called the arithmetic black box (ABB) that allows computing parties to perform operations with the data it stores without revealing it to those parties.

In Chapter 3 we study the society's preparedness to use SMC and adapt its processes around it. We discuss where and how SMC techniques could make the fastest inroads. Following the recommendations given in this chapter can decrease the time it takes to achieve tangible outcomes from SMC research.

We continue with an application area determined in Chapter 3 as one of the most likely to rapidly benefit from SMC techniques. In Chapter 4 we demonstrate methods for privacy-preserving statistical analysis. We explain how the functions and distributions often used in these analyses can be computed by SMC protocols. In Chapter 5 we show how we can avoid not only leaks during the computation, but also leaks through the results of statistical analyses — we show how mechanisms for differential privacy can be implemented through SMC.

Another important primitive in building privacy-preserving applications is oblivious data access — reading and writing the contents of arrays according to secret indices. In Chapter 6 we present efficient and composable methods for this building block. Some uses of these methods are presented in Chapter 7 where we show how to construct privacy-preserving protocols for language processing or business process analysis.

We continue with methods for checking the behavior of the participants of SMC protocols. In Chapter 8 we show how game-theoretic methods can encourage parties to input correct data to multiparty computation protocols. Chapters 9 and 10 describe different post-execution methods for verifying the correctness of the behavior of computing parties. The first of these is a general method where the honest majority can determine all deviating parties. The second method is applicable to tasks where, in practice, verifying the result of a computation can be much simpler than computing it. The method is demonstrated on the task of privacy-preserving linear programming.

In Chapter 11 we explore the limits of another method for privacy-preserving computation — transforming a task on the basis of its algebraic properties, publishing the transformed task and transforming the solution of the published task back into the solution of the original task. We find that, for linear programming, this method is most likely not applicable, as any transformation that preserves the confidentiality of the original task probably needs to solve the task. Still, the method can be applicable for solving systems of linear equations.

We finish the book with Chapter 12 by reviewing existing practical applications of SMC. In this chapter, we do not describe various research prototypes that have been developed by many different groups, but only the applications that have processed real data. We describe how the data was collected and processed, and how the results were made public.

Many of the results described in this book have been achieved in the project Usable and Efficient Secure Multiparty Computation (UaESMC), funded by the European Commission under the Seventh Framework Programme (grant agreement No. 284731). The project that ran from February 2012 to July 2015 under the theme ICT-2011.9.2 (HighTech Research Intensive SMEs in FET research), was a joint effort by Cybernetica AS (Estonia), the Royal Institute of Technology (Sweden), the National and Kapodistrian University of Athens (Greece), and the University of Tartu (Estonia). The goal of the project was to expand the number of areas and the kinds of algorithms that are amenable for applying SMC techniques.

In September 2014, a workshop for disseminating the results of the UaESMC project, as well as other results on applied SMC took place as a satellite event of ESORICS. In addition to talks by the project partners, there were two talks by the representatives of other research groups, for which we are very grateful. Both speakers have also generously contributed to this book as authors, and their chapters fit in well with the overall theme.

The publication of this book has also been supported by the Institutional Research Grant IUT27-1 from the Estonian Research Council, and by the Estonian Centre of Excellence in Computer Science, EXCS, funded through the European Regional Development Fund.

Peeter Laud and Liina Kamm

Tartu, April 2015