Multiparty Computation over Z/2^kZ

A digest of my PhD Thesis

My cat Nemo, again

A few days ago, on the 2nd of November of 2021, I defended my PhD Thesis at Aarhus University. Its topic is secure multiparty computation (MPC) over the ring of integers modulo a power of two (Z/2^kZ), that is, MPC protocols that natively support additions and multiplications modulo powers of two.¹ This is in contrast to most existing MPC protocols that only support arithmetic over fields, which include, for example, integers modulo a prime.

There are several reasons why this makes up for an interesting project:

• Existing computer architectures already implement (in hardware) arithmetic modulo some powers of 2 — this is what the types int32 and int64, for example, correspond to. This has at least two potential benefits: (1) if you have a program that uses basic operations over these types, an MPC protocol supporting this arithmetic could natively implement you program securely, and (2) if an MPC protocol only makes use of these basic data types then its implementation can potentially become simpler and more efficient (compared to, for instance, arithmetic modulo a prime, which requires software implementation).
• MPC is not only about additions and multiplications: we typically care about more complex operations such as comparisons, truncation, mathematical functions, bit slicing, etc. To this end, it is customary to rely on “bit-wise” techniques that, in a way, allow us to access the individual bits of some given shared values so that we can operate on these directly. Intuitively, arithmetic modulo a power of 2 is more “compatible” with arithmetic modulo 2, which is what bit operations correspond to, and this is indeed reflected both in the design of these higher-level primitives and in their performance.
• Finally, there is always a theoretical drive. Most existing MPC protocols make use of fields, and it is not obvious how to extend them to operate over Z/2^kZ. It is natural to wonder then if this is an inherent limitation, or if it can be overcome without any complications that may hurt efficiency considerably. Furthermore, MPC over Z/p^kZ for arbitrary primes p leads to MPC modulo N for any natural number N via the CRT, which is an interesting result on its own.

The goal of this post is to summarize the key ideas and techniques needed to achieve secure computation over the ring Z/2^kZ. This is an algebraic structure that contains zero divisors and other subtleties that make it hard, or at least, not trivial, to design MPC protocols that natively support these operations. In this post I describe some of the core ideas that enable secure multiparty computation over Z/2^kZ, in spite of these issues.

I would like to remark that this post assumes certain background on MPC. This can be complemented with some of my previous posts, but there are probably some assumed facts not discussed in these.

What Goes Wrong with Existing Techniques?

Most existing MPC protocols will require the underlying algebraic structure to be a field, and they will break if this structure is replaced with a more general ring such as Z/2^kZ. For reference, in a field such as the set Z/pZ of integers modulo a prime p (also denoted by F_p), every non-zero element x admits a multiplicative inverse x^-1, which satisfies x*x^-1 = 1. This is not the case over Z/2^kZ, since non-zero elements like 2 do not allow for such inverse — every number multiplied by 2 over Z/2^kZ results in an even number, so it cannot equal 1. In fact, only odd numbers are invertible modulo 2^k. In particular, Z/2^kZ is not a field.

Rings like Z/2^kZ behave more “wildly” than fields. For example, they have zero divisors, which are non-zero elements whose product is zero. Polynomials over Z/2^kZ may have many more roots than their degree, and the product of two non-zero uniformly random values does not look uniformly random. This leads to several existing techniques to break once the field has been replaced with Z/2^kZ. There are many little things that simply do not work in this new setting, but the ones I’d like to focus on are the following two:

• Active security in the dishonest majority setting via MACs does not work. In that setting, an additive sharing of a value [x] is accompanied by a MAC [α*x], where the parties have shares of the uniformly-random value [α]. An adversary can only cheat successfully and reconstruct an incorrect result if she manages to find δ and γ such that (1) δ is not zero and (2) α is a root of the polynomial δ*X + γ. If the given algebraic structure is a field, any such polynomial would have at most one root and the chances that α is such root are slim. However, over Z/2^kZ, polynomials like 2^k-1 * X can have many roots!
• Shamir secret-sharing does not work over Z/2^kZ. This construction requires some properties about polynomial interpolation, which ultimately rely on being able to invert elements to define Lagrange polynomials to prove existence, and bounding the number of roots of a polynomial to be able to prove uniqueness. None of these are generally possible over Z/2^kZ. Notice that, even if we are able to obtain Shamir secret-sharing over Z/2^kZ (hint: we will be able to achieve this but over a so-called Galois ring extension), we still need to take care of other properties such as error correction, which are mostly studied over fields.

If I have to summarize the core idea of a big portion² of my thesis (which I have to for the purpose of this post), I would do it in the following observation:

Main Observation: You don’t need all non-zero elements to be invertible, like in a field. Instead, you just need the ring to have a large enough exceptional set, which is a set whose non-zero pairwise differences are invertible.

In what follows we explore how is that the core property above is useful for MPC, and how is that we can achieve this property over rings like Z/2^kZ.

Exceptional Sets and Why They Are Useful

Let R be any finite ring, and let’s assume it is commutative.³ This ring may not be a field, so in particular, it may not be the case that every non-zero element is invertible. However, suppose that there exists a subset {β1, β2, …, βm} of R such that βi-βj is invertible for every i different to j. Such set is called an exceptional set, and even though, unlike fields, R itself may not be an exceptional set, as we will see there exist non-field rings with relatively large exceptional sets.

Lagrange Interpolation

The main interesting fact about exceptional sets is that Lagrange interpolation works as long as the evaluation points are taken over an exceptional set. More precisely, given any set of pairs {(β1,y1), (β2,y2), …, (βm,ym)}, there exists a polynomial f(X) over R such that f(βi) = yi for i=1,…,m. This polynomial is obtained as usual by taking a linear combination of Lagrange polynomials, which are well defined since the only multiplicative inverses these make use of are of elements of the form βi-βj.

Bounding the Number of Roots

Lagrange polynomials show that interpolation is possible, but they do not show that such interpolation is unique. To this end, over fields, the fact that every non-zero polynomial of degree d has at most d roots. As we have mentioned, this may not hold over more general rings such as our R under consideration. However, the following holds:

Let S be the set of roots of a polynomial f(X) of degree d. Even though |S| might be larger than d, any exceptional subset of S must have size at most d.

In other words, f(X) can have many roots, but the amount of roots that constitute exceptional set is bounded by the degree of the polynomial. This leads to the uniqueness of Lagrange interpolation: the difference of any two polynomials f(X) and g(X) of degree ≤m-1 such that f(βi)=g(βi)=yi for every i=1,…,m is a polynomial of degree ≤m-1 with β1,…,βm as roots, which has to be zero due to the property above.

We see then that exceptional sets are useful, for instance, since they allow us to reason about polynomials in a similar way as done over fields. This is of course particularly convenient when working with Shamir secret-sharing, but in fact it also has several applications beyond that. For example, in the dishonest majority setting this allows us to check the correctness of multiple openings in one go by taking a random linear combination using coefficients of the form ξ⁰,ξ¹, …, where ξ is uniformly random in an exceptional set. I am aware this says little about how this is actually done (or what this even means), but the point is that this seemingly small property is actually at the core of several techniques used for secure computation over more general rings.

Galois Rings

Now we know that, if the ring under consideration has a large enough exceptional set, as long as we “work over this subset” then several properties and results over fields actually carry over to this new setting. For example, if there is an exceptional set {β1, β2, …, βm}, then we can instantiate Shamir secret-sharing with m-1 parties (m-1 evaluation points for the shares, and 1 evaluation point for the secret). However, let’s recall that the ring of interest to us is Z/2^kZ, so, how large are exceptional sets in this ring?

Truth is, not too large. Any set of three elements cannot be exceptional, with the reason being simply that any set of at least three elements contains at least two elements with the same parity, whose difference will be even, hence non-invertible. This is useless — unless you want to use Shamir secret-sharing with two parties, which is simply additive secret-sharing.

To address the issue above, we rely on Galois rings. These are quotient rings of the form Z/2^kZ[X] / <h(X)>, where <h(X)> is the ideal generated by a polynomial h(X) of degree d, which is irreducible over F2 after taking modulo 2 to all of its coefficients. This ring is denoted by GR(2^k, d), and its main properties are the following:

• Elements in GR(2^k,d) can be seen either as polynomials over Z/2^kZ of degree at most d. In particular, Z/2^kZ is a subring of GR(2^k,d)
• Reducing modulo 2 leads us to GF(2^d) (the Galois field of 2^d elements), and an element in GR(2^k, d) is invertible if and only if its reduction modulo 2 is non-zero in GF(2^d).

The first property above is useful since it implies that any techniques we develop for secure computation over GR(2^k,d) leads to secure computation over Z/2^kZ, simply because the latter is a subring of the former.⁴ Now, from the second property above, we see that we can find an exceptional sequence in GR(2^k,d) of size 2^d: simply take the 2^d elements of GF(2^d), which can be seen as elements of GR(2^k,d), and observe that any non-zero difference is invertible since these are non-zero in GF(2^d).

To conclude, by taking d to be large enough, we can obtain a Galois ring GR(2^k, d) with a large enough exceptional set as to enable secure computation, by making use of the properties of these exceptional sets highlighted earlier. This is far from being the end of the story, but at least,

Bonus: A Basic Tutorial on (Secret-Sharing-Based) MPC

Finally, I would like to advertise what I believe are some hidden contributions of the thesis. In Aarhus University (as in many places), we can approach the thesis-writing process in two different ways: either we write an introduction that motivates our contribution and positions it within the area, followed by verbatim concatenation of published works, or we write the whole thing from scratch. I decided to go the second way. It ended up being an extremely time and energy-consuming task, and I regretted it for some time, but now that it’s over I’m quite happy with the result.

One of the motivations behind approaching the thesis in this way is that, by writing from scratch, I could approach the main topic of study in one single coherent and cohesive piece, having unified notation, relations among ideas that were only discovered later, etc. This way I could also focus on writing the small pieces I felt I contributed to the most, instead of copy-pasting a large paper that is the result of a lot of different contributors.

However, the main reason why I wanted to write a thesis in this way is that I saw this as an opportunity to contribute to the field in terms of “teaching”. To this end, the first part of the thesis is a ~80 pages introduction to (secret-sharing-based) MPC, which is intended to be self-contained, accessible, relatively comprehensive and hopefully clear. I missed a resource of this kind when I started the PhD, so when I saw the opportunity to write one, such as my thesis, I became super excited and committed. My plan is to turn this into a stand-alone document in a few months, but for now, a first draft of this tutorial is already out there as part of my thesis, which some people might find useful (please let me know if it does! It’d make my day). I welcome any feedback and comments for the upcoming versions of the text.

Footnotes

1. The challenge here is not designing an MPC protocol that allows us to securely compute a program defined over Z/2^kZ: at the end of the day we know that there exist several MPC protocols to securely compute any function, regardless of how this function is represented. The challenge, however, lies in supporting these operations natively, that is, designing secret-sharing-based MPC protocols where the core operations are addition and multiplications modulo 2^k.
2. Many problems are solved by the “main observation” regarding exceptional sets, but (1) in several constructions this is not enough and (2) some other constructions — like the case of a small number of parties using replicated secret-sharing — do not even require this. However, this property is general and useful enough to be able to capture a big portion of the thesis.
3. Many of these properties even hold if the ring is non-commutative, but to simplify matters let’s just assume this is not the case.
4. This is of course potentially very wasteful: we’re developing techniques to securely compute circuits over a Galois ring, which contains several “copies” of Z/2^kZ, but we’re only using it to compute over one such copy. This is likely to lead to some overhead that depends on the degree of the polynomial used for the Galois ring. There are several ways to avoid this. One is for example to use the so-called Reverse Multiplication-Friendly Embeddings over Rings, which enables parallel computation, together with some network routing to convert this into single-circuit computation.