Multi-Party PSM, Revisited
Private Simultaneous Messages (PSM) is a minimal model for information-theoretic non-interactive multi-party computation. In the 2-party case, Beimel et al. showed every function f : [N ]× [N ]→ {0, 1} admits a 2-party PSM with communication complexity O( √ N). Recently, Beimel, Kushilevitz and Nissim studied the multi-party case, showed every function f : [N ] → {0, 1} admits a 3-party PSM with communication complexity O(N). We provide new upper bounds for general k-party case. The new upper bounds match previous best results when k = 2 or 3, and improve the communication complexity for infinitely many k > 3. The technique also implies 2-party PSM with unbalanced communication complexity. Concretely, we show – For infinitely many k — in particular, including all k ≤ 19 — we construct k-party PSM protocols for arbitrary function f : [N ] → {0, 1}, whose communication complexity is Ok(N k−1 2 ). We also provide evidence suggesting the existence of such protocol for all k. – For many 0 < η < 1 — including all rational η = d/k such that k ≤ 12 — we construct 2-party PSM protocols for arbitrary function f : [N ]× [N ]→ {0, 1}, whose communication complexity is Oη(N) for one party, Oη(N 1−η) for the other. We also provide evidence suggesting the existence of such protocol for all rational η.