Aarhus University Seal / Aarhus Universitets segl

Daniel Esteban Escudero Ospina

Multiparty Computation over $\mathbb{Z}/2^k\mathbb{Z}$

Research output: Book/anthology/dissertation/reportPh.D. thesisResearch

The main topic of study in this thesis is \emph{Secure Multiparty Computation}, or MPC for short.
This is a set of techniques that enable a set of mutually-distrustful parties to securely compute a given function of their choice, without leaking any information about the inputs provided to the computation beyond what is leaked from the output itself.
These tools are extremely useful in many applications where privacy of data is required, but different operations on this data must still be performed.

The field of MPC has a rich and fruitful research history.
Starting with the seminal work of Yao in 1982, a large body of works has taken care of expanding the knowledge barrier in MPC in many directions, including the development of new techniques, discovering new inherent limitations, improving the efficiency of existing techniques, among others.

In spite of such a long and successful series of studies, most MPC techniques share in common a simple yet restrictive limitation.
Mathematics play a central role in the development of MPC protocols, and in particular, most MPC techniques require the desired computation to be performed over a ``nice enough'' algebraic structure.
This is typically represented by means of \emph{finite fields}, which include the natural case of arithmetic modulo $2$ over $\{0,1\}$, and more generally include integer arithmetic modulo a prime number $p$.
Unfortunately, this type of arithmetic is not very natural for many applications, and moreover, it is not ``directly compatible'' with modern computer architectures where native operations are typically arithmetic modulo $2^{32}$ or $2^{64}$.

In this thesis we explore the task of designing MPC protocols when the computation domain is a ring of the form $\mathbb{Z}/2^k\mathbb{Z}$, that is, integers modulo $2^k$.
This algebraic structure is not a field, and in fact, it has a lot of undesirable properties that complicate the task of protocol design in this setting.
On the positive side, this ring is more directly compatible with native datatypes in modern computer architectures such as \texttt{int32} or \texttt{int64}, which can naturally lead to further improvements in the efficiency of different MPC protocols.
Additionally, arithmetic modulo a power of two is more ``compatible'' with binary arithmetic, which is a central building block in many applications.

The results of this thesis include a series of MPC protocols in a wide variety of security scenarios for computation over $\mathbb{Z}/2^k\mathbb{Z}$.
These settings include passive and active corruption for $t$ corruptions where $t<n/3$, $t<n/2$ and $t<n$.
Special cases where the number of parties is small are also considered, and specialized protocols for different subcomputations that appear thoroughly in many applications are presented, taking complete advantage of the fact that the computation domain is $\mathbb{Z}/2^k\mathbb{Z}$, instead of a finite field.

As a bonus, and to compare our novel techniques with previous works over finite fields, several existing techniques over these domains that can be considered essential in the area are presented.
Original languageEnglish
Publication statusPublished - 2021

See relations at Aarhus University Citationformats

ID: 224083604