On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages
The paper studies communication complexity for symmetric Boolean functions in Multiparty Private Simultaneous Messages (PSM), a model for secure computation where parties encode inputs using shared randomness. The authors establish superlinear lower bounds ($\Omega(n\log n)$) for functions like OR and MAJ, while constructing protocols with total communication $\widetilde{O}(n^{3/2})$ for perfect privacy, improving on previous quadratic bounds.