Cryptology ePrint Archive: Report 2019/657

Multi-Party PSM, Revisited

Leonard Assouline and Tianren Liu

Abstract: 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]\times[N]\to\{0,1\}$ admits a 2-party PSM with communication complexity $O(\sqrt N)$. Recently, Beimel, Kushilevitz and Nissim studied the multi-party case, showed every function $f:[N]^3\to\{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 \leq 19$ --- we construct $k$-party PSM protocols for arbitrary function $f:[N]^k\to\{0,1\}$, whose communication complexity is $O_k(N^{\frac{k-1}{2}})$. We also provide evidence suggesting the existence of such protocol for all $k$.

- For many $0<\eta<1$ --- including all rational $\eta = d/k$ such that $k\leq 12$ --- we construct 2-party PSM protocols for arbitrary function $f:[N]\times[N]\to\{0,1\}$, whose communication complexity is $O_\eta(N^\eta)$ for one party, $O_\eta(N^{1-\eta})$ for the other. We also provide evidence suggesting the existence of such protocol for all rational $\eta$.

Category / Keywords: cryptographic protocols / information-theoretic

Date: received 3 Jun 2019, last revised 4 Jun 2019

Contact author: liutr at mit edu,leonard assouline@ens-lyon fr

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2019/657

[ Cryptology ePrint archive ]