On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

The gist The paper studies communication complexity for symmetric Boolean functions in Multiparty Private Simultaneous Messages (PSM), which is a model for non-interactive secure computation, and establishes lower bounds and upper bounds for various symmetric functions.

Lower Bounds

The authors introduce a new combinatorial technique to obtain better lower bounds than those previously established by Ball et al. [BHI+20] who yielded only trivial linear bounds for symmetric Boolean functions In particular, their results show that the communication complexity C(OR) = ω(n) for any perfectly correct, support-private PSM protocol computing OR For MAJ or EMAJ (with even n), the communication complexity is proven to be omega(n log n) Furthermore, for MODq when q ≤ (1 − c)n for a fixed constant c > 0, the communication complexity satisfies C(MODq) = omega(n log q) These lower bounds are derived using a general combinatorial framework that reduces proving lower bounds in the PSM model to studying f-cube systems

Upper Bounds

The authors construct perfectly private PSM protocols of total communication Oe(n 3/2) for every symmetric Boolean function, improving on the known quadratic bound Specifically, Theorem 30 proves that for any symmetric Boolean function f: 0, 1 n → 0, 1 there is a perfectly correct, perfectly private PSM of total complexity Oe(n 3/2) For MAJ, a combination of known results matches the lower bound up to polylogarithmic factors, yielding a communication complexity of O(n log3 n log log n) The universal support-private construction of [BIKL25] gives Oe(n 2) communication For symmetric functions, they obtain a quasilinear bound of Oe(n) for perfectly correct, support-private PSM protocols

Key Techniques and Results

The paper introduces an f-cube system representation to isolate the correctness and privacy properties used by lower bounds This framework allows them to use agreement lemmas, such as Lemma 13 for OR, which relies on Higman’s lemma and Ramsey’s theorem They also employ Plotkin’s bound for error-correcting codes to derive alphabet lower bounds for MAJ and MODq functions The lifting lemma in Section 6 converts individual message lower bounds into a total communication lower bound

Specific Function Results

The paper provides specific results for several symmetric Boolean functions. For OR, the communication complexity is proven to be C(OR) = ω(n) For MAJ and EMAJ (when n is even), the communication complexity is omega(n log n) For MODq, the communication complexity satisfies C(MODq) = omega(n log q) when q ≤ (1 − c)n for some constant c > 0 They also show that there is a perfectly correct, perfectly private PSM protocol for MODq with cost O(n log q) when q is prime and for EMAJn of cost O(n log n)

General Lower Bound Approach

The general lower bound approach involves defining a Consistent Coloring Family and showing that the non-existence of such a family implies the non-existence of an (n, K)-protocol satisfying perfect correctness and support privacy They relate this cube argument to the Nechiporuk bound, which states that every perfectly correct, support-private protocol for f with local alphabet sizes Ki satisfies P i∈S log Ki ≥ log NS(f) − 1 This leads to Corollary 29, showing Cindiv-sum(f) ≥ Xm i=1 log NVi(f) − m

Upper Bound Construction

The upper bound construction for a general symmetric function f(x) = g(x) involves composing an outer protocol that evaluates g on the weight reconstructed from residues modulo small primes with inner protocols that privately compute the outer messages This results in a total communication complexity of O(n 3/2) For support-private protocols, they obtain a quasilinear bound of Oe(n) for any symmetric Boolean function f The upper bound for MAJ is achieved by combining a known permutation branching program with a standard PSM construction, yielding O(n log3 n log log n) The upper bound for EMAJ and MODq with prime q follows from variants of the OR protocol in Theorem 11, resulting in O(n log q) For EMAJn, a specific protocol yields a cost of O(n log n) This demonstrates the efficiency of the constructions for these symmetric functions.

Conclusion

The paper successfully establishes tight bounds for various symmetric Boolean functions in the PSM model, showing that while perfect privacy allows for quadratic communication complexity, support privacy allows for quasilinear communication complexity The study provides a general combinatorial framework and specific protocols that achieve these bounds This work contributes to understanding the cost of privacy in non-interactive secure computation.

--- Page 1 ---

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages Marshall Ball Peter Crawford-Kahrl Vladimir Podolskii and Morgan Prior New York University marshall@cs.nyu.edu pjc8515@nyu.edu Tufts University vladimir.podolskii@tufts.edu morgan.prior@tufts.edu Abstract Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness The evaluator must recover the function output without learning anything else about the inputs Perfect privacy requires identical transcript distributions on inputs with the same output We also study the weaker notion of support privacy, which requires only that these distributions have the same support We study the communication complexity of symmetric Boolean functions when each of the n parties holds one input bit Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing ORn Our technique gives omega(n log n) lower bounds for MAJn and EMAJn (with even n), and an omega(n log q) lower bound for MODq when q ≤ (1 − c)n for a fixed constant c > 0 Upper bounds. We construct perfectly private PSM protocols of total communication Oe(n 3/2) for every symmetric Boolean function, improving on the known quadratic bound For MAJn, known branching-program constructions yield an upper bound of O(n log3 n log log n) For EMAJn and MODq with prime q, the lower bounds are tight up to constant factors in the stated regimes Under support privacy, we obtain Oe(n) communication for every symmetric Boolean function Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions AI usage disclosure. Work on this project began in spring 2023. The authors made initial progress on the complexity of ORn for small constant n and suspected that extremal combinatorics might provide the key to stronger bounds On April 29, 2026, ChatGPT-5.5 Pro was used to find a viable superlinear lower bound for the OR function, indeed using classic results by Ramsey and Higman The authors subsequently generalized and extended the lower bound without AI Upper bounds were obtained with partial AI assistance, exploring branching program results, and parameter verification in composition constructions AI tools were used for proof verification and editorial assistance. The authors take full responsibility for the contents.

--- Page 2 ---

In a PSM protocol for a function f, each of n parties holds an input xi and independently computes a message mi using a shared random string r The parties send their messages to an evaluator, who has access to neither the inputs nor the shared randomness and must compute f(x1,..., xn) Privacy requires that the evaluator learns nothing else about the inputs We study two information-theoretic notions of privacy, both defined through the transcript: the tuple of messages sent by all parties Perfect privacy requires identical transcript distributions whenever f(x) = f(x′) Support privacy requires only that these distributions have the same support A central goal in this setting is to understand the cost of privacy. We study this cost through communication complexity. For a Boolean function f, we distinguish the individual message complexity Cindiv(f) from the total communication complexity C(f).

1. Bold Header: Perfect Privacy for Symmetric Functions

This allows AI systems to securely compute any symmetric Boolean function without revealing any information about their inputs beyond the function's output, as demonstrated by Theorem 31: For any symmetric Boolean function f: 0, 1 n → 0, 1 there is a perfectly correct, support-private PSM of total complexity Oe(n).

2. Bold Header: Efficient Computation of OR

The system can securely compute the OR function with a communication complexity of Oe(n 3/2), improving on previous quadratic bounds, as stated in Theorem 30: For any symmetric Boolean function f: 0, 1 n → 0, 1 there is a perfectly correct, perfectly private PSM of total complexity Oe(n 3/2).

3. Bold Header: Secure Majority and Modulo Functions

AI can securely compute the Majority (MAJ) and Exact Majority (EMAJ) functions with omega(n log n) communication complexity, as per Corollary 24: The functions MAJn and EMAJn (when n is even) have communication complexity omega(n log n). Furthermore, secure computation of MODq can be achieved with a cost of "C(MODq) = omega(n log q) when q ≤ (1 − c)n for a fixed constant c > 0."

4. Bold Header: Lower Bound Derivation for OR

The system can establish that computing OR requires superlinear communication, as shown by Corollary 20: The PSM communication complexity C(OR) = ω(n). This implies that any protocol achieving perfect correctness and support privacy for OR must have a transcript length exceeding linear bounds.

5. Bold Header: Utilizing Combinatorial Frameworks

The system leverages the f-Cube System representation to prove lower bounds, where Privacy forces the same transcript to appear at many corners of different Boolean cubes, while correctness constrains which corners may coincide. This framework is used to derive bounds like Corollary 24 by relating individual message complexity bounds (Theorem 21, 22, and 23) to total communication complexity via Lemma 6.

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output without learning anything else about the inputs. Perfect privacy requires identical transcript distributions on inputs with the same output. We also study the weaker notion of support privacy, which requires only that these distributions have the same support. We study the communication complexity of symmetric Boolean functions when each of the n parties holds one input bit. Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing OR n. Our technique gives Ω(n n) lower bounds for MAJ n and EMAJ n (with even n), and an Ω(n q) lower bound for MOD q when q at most(1-c)n for a fixed constant c>0. Upper bounds. We construct perfectly private PSM protocols of total communication (n 3/2) for every symmetric Boolean function, improving on the known quadratic bound. For MAJ n, known branching-program constructions yield an upper bound of O(n cubed n n). For EMAJ n and MOD q with prime q, the lower bounds are tight up to constant factors in the stated regimes. Under support privacy, we obtain (n) communication for every symmetric Boolean function. Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions. Concurrent and independent work by Holmgren and Wu proves a ω(n) lower bound for OR n using the same combinatorial core. Both works used AI assistance.