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 $(1-o(1))n\log n$ lower bound for support-private PSM protocols computing $OR_n$, and as a consequence for $MAJ_n$ and $EMAJ_n$ as well. We also prove an $\Omega(n\log q)$ lower bound for $MOD_q$ when $2\le q\le n$, with a constant independent of $q$. An alternative proof technique recovers most of these bounds as well as the previously known approach based on Nechiporuk's method.
Upper bounds. We construct perfectly private PSM protocols of total communication $\widetilde{O}(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\log^3 n\log\log n)$. For $EMAJ_n$ the lower bound is tight. For $MOD_q$ with prime $q$ the lower bound is tight up to a constant factor. The matching upper bound for $OR_n$ was previously known. Under support privacy, we obtain $\widetilde{O}(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 $\omega(n)$ lower bound for $OR_n$ using the same approach as our alternative technique. Both that work and the present work used substantial AI assistance.