On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages
Paper proves superlinear PSM lower bounds for symmetric Boolean functions and near-linear support-private upper bounds.
The paper studies communication complexity of symmetric Boolean functions in multiparty private simultaneous messages, also known as decomposable randomized encoding. It proves a superlinear lower bound for support-private protocols computing OR_n, Omega(n log n) bounds for majority and even-n exact majority, and Omega(n log q) for MOD_q in a stated regime. Perfectly private constructions improve the quadratic bound to roughly n to the 3/2 total communication for every symmetric Boolean function, while support privacy achieves near-linear communication. Concurrent independent work by Holmgren and Wu also proves a superlinear lower bound for OR_n.
- Support-private PSM for OR_n requires superlinear communication.
- Perfectly private protocols use about n to the 3/2 communication for every symmetric function.
- Support privacy yields near-linear communication for every symmetric Boolean function.
- Concurrent work independently proves a superlinear lower bound for OR_n.
From the original article
1 min read at arxiv.orgMultiparty 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.
By Marshall Ball · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.