Unconditionally Secure MPC for Boolean Circuits with Constant Communication (Crypto 2026)

Hello everyone, this is Bang. It is a great pleasure to present this joint work with Kanyang and Mang. This work is entitled unconditionally secure MPC for boring circus with constant communication. First let me briefly introduce secure multi-party communication or MPC. NPC is an interactive protocol that allows several mutually distrusting parties, say Alice, Bob, Carol, and Dave to jointly compute a function on their private inputs. Each party provides its own input and should learn only prescribe output yi and nothing else about the other parties inputs. To formalize security, we consider an adversary that may corrupt some of the parties. The protocol should guarantee privacy and correctness even against such an adversary. In this work, we focus on unconditionally secure MPC. Unlike computationally secure m secure protocols, unconditional security does not rely on computational hardly assumptions and provide security even against computationally unbounded adversaries. Such protocols typically involve lightweight local computation and can be obtained naturally from secret sharing techniques in the honest majority setting. Therefore, communication complexity is a central efficiency measure and reducing communication is a major focus of this line of the work. Most secret sharing based MPC protocols are naturally designed for arithmetic circuits over large fields. In this setting, driver works have reduced the communication complexity to linear communication per gates in the standard honest majority setting and even to constant communication per gates under stronger honest majority assumption. Now we turn to the boolean circuits which are another fundamental computation model in MPC especially for applications such as database queries, comparisons, sorting and secure inference. In this application, many common operations are inherently beat oriented. For instance, comparisons in database queries and sorting as well as value operations in secure inference can often be handled more efficiently over bulling circuits than over the large field arithmetic circuits. However, the best known booing circuit protocols still require all loan BS of communication per gate in sharp contrast to the constant communication results over the large fields. Putting these results together, we see a clear efficious gap between large field arithmetic circuits and the boolean circuits. This gap naturally leads to the following questions. Can we construct unconditional secure MPC protocols for evaluating a single boolean CPU with total communication complexity OCBS? We answer this question in affirmative. Informally in the strong honest majority setting our protocol securely evaluates a single bulling circuit with total communication OCBs. Equivalently this gives constant per this gives constant communication per gau for both semi-honest and malicious adversaries. To understand the main idea of our construction, it is helpful to first release the natural approaches to boolean circuit MPC. The main difficulty is that the base field is too small. So, previous techniques typically fall into two categories. Either walking directly over the small field or embedding the computation into a large field. A natural small field approach is based on algebraic geometric codes. By using algebraic curves with many rational places, these schemes obtain enough evaluation positions for secret sharing almost more fields. However, this introduce more expensive computation and the best known communication along this line remains OMB gates. Another natural direction is large field embedding. The first approach is direct embedding. We simply feel each bit as an elements of an extension field f_sub_2 to a lambda. However, to have enough points for interpolation, the extension degree must be at least log M. Therefore, even if we combine these with constant communication large field protocols, we still get all log MBs per pooling gau. A more efficient approach is reverse multiplication friendly embedding or RMFE. Instead of embedding a single bits, RMFE maps a vector of LBS into one extension feed elements while preserving component wise multiplication through the maps F and PI. Since the expansion factor M / L is bounded by a constant, this gives a much better baiting rates. The key limitation is that these maps are only F2 limit. This will become an issue when we try to construct protocols. Although RMFE provides a powerful way to embed a boolean computation into a large field, it also imposes structural constraints on the computation. The original RMFE based approach requires evaluating many identical circuits in parallely. Later work removes this par evaluation restriction but is is gate by gate paren still incurs a linear communication lower bound. This suggests that RMFE alone is not enough. We need additional techniques to exploit RMFE more effectively. Starting from the limitation of RMFE alone and inspired by HY24, we can pack RMFE encoded secrets to obtain further amotization. Before presenting the construction, let us briefly let us briefly recall package secret shing or PSS for shortly. PSS generalize shamir shing by encoding multiple secrets in a single polomial. It preserves the algebraic structure of shamir shing enabling packet additions and multiplications. When RMFE is combined with PSS, we can pack K* L boolean secrets into one sharing and evaluated them in parallel in the strong honest majority setting. Since the main computation is now moved to the extension field, we can largely follow the standard PSS computation pattern over the large fields such as DN style operations. The red part here indicates the actual multiplication step in our construction. What we want to emphasize is that once this DS style operations can be carried out correctly, the multise communication naturally becomes OEB spates. However, as shown in these slides, the structure of a general circuit is not automatically compatible with parally packaged evaluation. The inputs required by the next layer may be distributed across different output sharings and even after they are collected their order may be misaligned together. These issues constitute the so-called network routting problem. Packet w values must be realigned so that the next layer receives the correct inputs in the correct positions. Although GPS21 and GPS22 provide a complete routing framework over large views, our sharing has an additional nested structure. The outer layer consists of RMFE encoded field elements 5xi while the inner layer contains the booing secret hidden inside them. Standard routing only works on the outer PSS layer but cannot directly rearrange the inner bits positions. This makes rooting more challenging in our setting. More seriously, efficient routting requires correlated randomly and generating such random lakes involves substantial operations over the extension field. However, RMFE only supports F2 linearity which makes the computation in incompatible. To overcome these challenges, we first release the routine framework from private works and examine which ideas can be adapted to our necessary. Private works address the two routine issues using two basic operations efficient permutation and efficient selection. Permutation is relatively straightforward. It can be viewed as a linear transformation on the secret vector and implemented using DN style operations. Selection is more subtle. We first consider an idea case where the selected secrets lie in different positions. In this case, the target vector can be written as a linear combination between public vectors and selected secret vectors and can therefore be computed efficiently. The key questions is how to make each selection idea. To make each selection idea, GPS21 introduces another linear operation called fast gates. The idea is to copy each secret the number of times it will be used in later layers and pack this copied into expanded PSS. After applying proper permutations to each expanded sharing, each selection becomes ideal as guaranteed by horse marriage theorem. We recommend reading GPS 21 to fully appreciate this routine framework. These slides summarize the routting framework. Permutation and fan out can be filled as a linear transformation on the secret vectors and implemented using correlated randomly and DN style operations combined with a suitable circuit transformation. They can make each selection idea yielding efficient routine over large fields. Back to our work, our key observation is that if we separate the rooting operations from their concrete computation and focus only on their action on secret vectors, then our setting only increase the vector dimension from K to KL. The underlying combinatorial arguments and the linear transformations are essentially field independent. Rooting extension field secrets and rooting boolean secrets have the same abstract structure only the dimension changes. We refer to these as the third independent part of the routting framework. Following this observation, the boolean routting problem can be separated into two parts. The field independent part naturally extends from the large field setting. The only remaining field dependent part is how to realize the three grouping operations efficiently at the bit level. We first realize bit level selection. Now assume bit level permutation and fan out are available. The previous rooting argument naturally extends to the k dimensional case making each bit level selection idea. Next we check the idea bit level selection can be implemented efficiently. In the idea case the target vector can again be written as a sum of component wise products between public unit vectors and selected secret vectors. Here we cannot encode a k dimensional unit vector directly as one PSS sharing. Instead we decompose it into K blocks of lens air and encoded them these blocks as constant PS sharings using the multiplicative property of RMFE together with correlated randomness. We can realize idea selection at the beta level. The communication is n * m bits excluding the cost of randomly generation. Now we return to bit level permutation and fan out. These op operations are easier to handle since they can also be expressed as linear transformationations on the underlying bit vector except the linearity is over f_sub_2. Therefore they can again be implemented using correlated randomly and dn style operations. Similar to selection the communication is bounded by all n * n bits excluding randomly generations. So putting the three operations together, efficient boolean routing is now reduced to the problem of efficiently generating required random required correlated randomly. As mentioned earlier, the main difficulty in random list generation comes from the fact that RMFE maps F and PI are only F2 linear. We overcome this limitation through two main techniques. The first one is the tensoring up lema from CCXY18. By taking an M4 interlift sharing, we can support F2 to the M linear operations. This allows us to use hyper invertible mergers to generate the correlated randomly needed for multiplication and selection. For permutation and fan out, the required random list is smaller in size but comes in many different types. For this part, we use the sharing transformation technique from GPS22. Informally, it converts easy to generate base sharings into structured random lists required by different routing operations. In our construction, the degree ti vector r serves as the base sharing which can be generated in large batches using the first technique. The random list required by different routting operations is treated as specific sharings where each linear map f corresponds to a different sharing scheme. We now show how to consume n * n base sharings to generate k* a specific sharings. First, we prepare n * n base sharings and arrange their underlying secret vectors row by row to form an n m * k bit matrix. Since the sharing algorithm of each scheme is linear, if both the input tab and the random tab are random, the output is definitely a random sharing. In our matrix, each column provides randomness needed for one specific sharing scheme. However, these algorithms are only F2 linear. So they cannot generate extension fees. To handle this, we will use the bit decomposition technique. From the from each main sharing algorithms, we derive sub algorithms that generates the same position bits of all schemes. Repeating this procedure m times and recombining the beads years secrets over f2 to m. Putting these pieces together, we obtain an efficient random lace protocol. Each required random list cost N* M bits to generate. With these random lists, we can implement efficient bit level permutation and fan out gates and then use the natural dimension extension to realize efficient bit level section. Combining these routing operations will present a full boole network routting procedure together with normal calculations. Any single sharing in this work requires total O time NBS in communication. Since each sharing takes K * L bulling secrets, the cause is a multi to constant communication package yielding an overall OCB protocol. So this is our work. Thanks for your attention. If you have any questions, please contact me via this email.