Theory and Practice of Multiparty Computation

Ivan Damgård, Martin Geisler, Mikkel Krøigaard +1 more

Bernardo David, Ryo Nishimaki, Samuel Ranellucci +1 more

Tord Ingolf Reistad

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.

Chen SUN Xuhong LIU, Chen SUN

As a fundamental part of cryptography, secure multiparty computation (SMC) is a building block of various cryptographic protocols, and it is also a hot topic in the international cryptographic community.In recent years, many SMC problems, such as secret information comparison, secret set problems and secure multiparty computational geometry, have been widely studied.As many practical problems need to be described by rational numbers, it is both theoretically and practically important to study the SMC problems in the rational number field.However, most of the existing researches focus on integers and the studied data are mainly one-dimensional data.There are few researches on secure multiparty computation of multi-dimensional data in the rational number field, but they can’t be generalized.Based on the fractional representation of rational numbers, the new encoding schemes about rational numbers and rational number vectors were proposed, which could encode multi-dimensional data in the rational number field and provided new solutions for other SMC problems in the rational number field.Based on the encoding scheme and one-way hash function, some protocols were designed for equality problems and set problems in the rational number field.These protocols used basic arithmetic operation and hash operation to guarantee efficiency than existing related protocols.And these protocols didn’t limit the range of research data and they were more widely applicable.It proves that these protocols are secure in the semi-honest model using simulation paradigm, and demonstrates the efficiency and the applicability of these protocols by theoretical analysis and experiment.A practical example was also given to illustrate that approaches are more versatile, and they could also be directly used to solve some secure multiparty computational geometry problems in the rational number field.

Yevgeniy Dodis, Rafael Pass, Shabsi Walfish

Peeter Laud

In this note we describe efficient protocols to perform in parallel many reads and writes in private arrays according to private indices. The protocol is implemented on top of the Arithmetic Black Box (ABB) and can be freely composed to build larger privacy-preserving applications. For a large class of secure multiparty computation (SMC) protocols, we believe our technique to have better practical performance than any previous ORAM technique that has been adapted for use in SMC. We also argue that for a significant class of SMC protocols, our technique has better asymptotic performance than previous approaches.