In this post, we’ll discuss how Galois rings (a recent algebraic structure) improve the communication complexity of dishonest multiparty computation (MPC) protocols.

Before we dive into MPC, I’ll take a brief detour to discuss how computation is usually modeled in cryptography. When cryptographers think about computation, they often think about circuits comprised of addition and multiplication gates. You may think ah so like boolean circuits? Nope, cryptographers love circuits over HUGE fields; in fact, the bigger the better! Fields are convenient to work with as 1) every element except for zero is invertible and 2) low-degree, non-zero polynomials have few roots. As such, we can often tie the security of cryptographic protocols directly to the size of the field (as we’ll see shortly). However, deep down, cryptographers really just want to work with circuits over the integers mod (), think /-bit unsigned integers. For ease of notation, we will use . Integer arithmetic (i.e. ) is exactly the arithmetic we already have on our cpus. Just think about how much modern software we could directly capture… but, OOF, is a pain to work with! Half of the elements are not invertible, and low-degree, non-zero polynomials can have TONs of roots (like ). If only we had a ring with similar properties to fields that could also capture arithmetic. In fact, we do. GALOIS RINGS!

A Galois ring is a quotient ring for which is a monic polynomial of degree such that is an irreducible polynomial in . Here, we use , but Galois rings are described generally for for any prime . Informally, you can view the elements of as degree polynomials whose coefficients belong to and operations are performed . Galois rings have several nice properties:

1) fraction of elements are invertible [Wan03].
2) is isomorphic to [Wan03].
3) A non-zero polynomial with has at most roots [ACDEY19].
4) There exists -linear maps called reverse multiplication friendly embeddings or RMFEs [EHLXY23].

Property 3) gives us a nice analog of the Schwartz-Zippel lemma, but over Galois rings instead (which are not integral domains)! Namely, . As we will see later, property 3) can help us catch cheaters and 4) will naturally embed arithmetic into arithmetic.

With that aside over, we now have enough to discuss MPC. Let be some ring (like , , ). Multiparty computation [BGW88, CCD88, GMW87, Yao86] is an interactive protocol between multiple parties, , who each have their own private inputs , respectively. They want to compute the output of some public circuit on their inputs. The catch is that no party should learn anything about the other parties private inputs, besides what is revealed by . Ideally, the amount of information the parties can learn is identical to as if they had just asked a trusted third party to do the computation. When all parties follow the protocol honestly, we know of simple MPC protocols (semi-honest MPC) where this trusted third party can be replaced purely with interaction between parties.

Unfortunately, it’s unrealistic to expect that all parties behave honestly. Some malicious parties could arbitrarily deviate from the protocol in an attempt to learn more information about the other parties’ private inputs. So, we need a way to catch when malicious parties misbehave and abort the whole protocol before information is leaked! There are two prevailing paradigms for constructing dishonest MPC:

1) Authenticated secret sharing [DPSZ12, DKLPSS13, KOS16, KPR18]
2) Fully Linear Interactive Oracle Proofs (zk-FLIOPs) [BBCGI19, BGIN19,BGIN20, BGIN21]

We will focus on authenticated secret sharing in this post, and what goes wrong when working over . Consider an arbitrary element . An additive secret sharing of is a collection of uniformly sampled elements



For example, I can share my password (private input) with friends (parties possessing , respectively) in such a way that they can recover my password if all of them work together, but without this quorum, they locally can only see uniformly random nonsense. Additive secret shares are also linearly homomorphic; given shares and , parties can derive a share to by locally computing for any constant . This property is essential for constructing semi-honest MPC.

However, if a friend, , is malicious, they may try to mess up recovery by introducing some additive error to their share such that together the parties recover , which is not the correct value. The security of dishonest MPC protocols essentially boils down to catching when malicious parties introduce these additive errors to secret shares. But, how do we actually catch cheaters? During a setup phase, Parties will receive an additive secret sharing of an element , sampled uniformly from the ring, which is unknown to all parties. An authenticated secret share of is a pair of additive secret shares of both and . Intuitively, we can think of this additional share as an MAC (message authenticated code) and as a MAC key. To see why, let’s go over the recovery (opening) procedure. As before, let be a malicious party who wants to shift the opening by an additive error .

1) Parties broadcast their shares .
2) Parties locally compute claimed opening .
3) Honest parties locally compute . Dishonest party locally computes for some of their choice.
4) Parties broadcast their shares and locally check . If not, abort!

For a malicious party to succeed, they must guess such that . If is a field, we can trivially solve for . Thus, the malicious party must be able to guess ! Since is uniformly random and unknown to any party, we can bound the probability the malicious party succeeds with . With a large field (say ), this chance is vanishingly small. However, things go terribly wrong when we choose . Notably, there’s an explicit attack that has a chance of succeeding! The malicious party samples a random bit and choose . Observe where is the -th bit of . This is zero with probability !

Prior works [CDE+18, BBH+22] avoid this issue with by working over a larger ring where . In this setting, and authenticated share for (over the smaller ring) consists of additive shares where belongs to the larger ring. Now, the malicious party must guess such that . Let be the largest power of two that divides . We have that , which means the malicious party must guess at least -bits of the secret . Therefore, we can bound the probability of success by . Unfortunately, this technique sacrifices share size for better security! In particular, higher security requires higher communication overhead (only out of -bits are used meaningfully). Shoot…if only there was a better ring… [Insert heroic entrance!]

[EXY22, LXY24] avoid this tradeoff by setting the underlying ring to be a Galois ring . Leading to a protocol where communication does not scale with the level of security! Let’s perform similar analysis, but now over . Since , we have is a non-zero, degree- polynomial. Thus, by property 3), we have . Yay! We have a security when is large enough. An astute reader might ask: didn’t we want to capture computation over and not this weird ring ? And, they would be right!

Recall, informally, that we can think of as a set of degree polynomials with coefficients in . Maybe we can embed an into by treating it as a constant polynomial? Now, when we compute a circuit over , the constant terms in get added and multiplied together as needed. In fact, this strategy will work and is secure, but we just dug ourselves into a deeper hole! Since (a random degree polynomial), we have that the authenticated secret share size scales with , which itself scales with our security! SHOOT, the rate is terrible. Instead of more bits per share (as in the prior strategy over ), we have a multiplicative factor in communication! But all hope is not lost. [Insert second heroic entrance!]

Reverse multiplication friendly embeddings (RMFEs) (their theory was unified in EHLXY23) are maps with several amazing properties (among many others):

1) (Good rate) Let . There exists families of RMFEs such that is a constant ().
2) (Linearity) Both maps are -linear. In other words, for all , we have and .
3) (Multiplication Friendliness) For all , we have (where is multiplication and is element-wise product).
4) is injective, is surjective, , for all , and (internal direct sum).

Let’s break down why these properties enable communication to be independent of security. First off, the good rate of RMFEs helps us pack integers from into a single ring element in . Thus, now each ring element in can be thought of as integers (avoiding that blowup from the constant embedding). With linearity, additions over the ring naturally simulate additions over the vector space . In particular, if we embed two vectors into the ring, then the ring addition simulates the vector addition. Finally, multiplication friendliness similarly allows us to naturally simulate element-wise multiplication with multiplication over the Galois ring. Therefore, despite each ring element being the size, we do the work per element! Beyond the theoretical independence, [EXY22, LXY24] concretely show roughly less communication over prior work for high security applications (think -bits of statistical security).

In conclusion, we discussed what cryptographers like about different rings (fields, integers mod , and Galois rings), the relationship between MPC and authenticated secret sharing, how different rings affect the security and communication of MPC protocols, and how choosing Galois rings can avoid communication blowups by packing more work into each element. Of course, I skipped over many details including, but not limited to, how to construct MPC from authenticated secret sharing, why security reduces to catching bad openings, why Galois rings have such few roots, and how RMFEs are constructed. I suggest readers who are interested to refer to the works referenced!

Acknowledgements: I wrote this blog post as a part of my qualifying exam. Thank you to Mary Wootters, Dan Boneh, and Clark Barrett for being on my quals committee and occasional chats about algebraic geometry. Special thanks to the Applied Crypto group for their continual support during my quals prep.

zk-FLIOP references: [BBCGI19, BGIN19,BGIN20, BGIN21]