Welcome to the resource topic for 2019/657
Title:
Multi-Party PSM, Revisited: Improved Communication and Unbalanced Communication
Authors: Leonard Assouline, Tianren Liu
Abstract:We improve the communication complexity in the Private Simultaneous Messages (PSM) model, which is a minimal model of non-interactive information-theoretic multi-party computation. The state-of-the-art PSM protocols were recently constructed by Beimel, Kushilevitz and Nissim (EUROCRYPT 2018). We present new constructions of k-party PSM protocols. The new protocols match the previous upper bounds when k=2 or 3 and improve the upper bounds for larger k. We also construct 2-party PSM protocols with unbalanced communication complexity. More concretely, - For infinitely many k (including all k \leq 20), we construct k-party PSM protocols for arbitrary functionality f:[N]^k\to\{0,1\}, whose communication complexity is O_k(N^{\frac{k-1}{2}}). This improves the former best known upper bounds of O_k(N^{\frac{k}{2}}) for k\geq 6, O(N^{7/3}) for k=5, and O(N^{5/3}) for k=4. - For all rational 0<\eta<1 whose denominator is \leq 20, we construct 2-party PSM protocols for arbitrary functionality f:[N]\times[N]\to\{0,1\}, whose communication complexity is O(N^\eta) for one party, O(N^{1-\eta}) for the other. Previously the only known unbalanced 2-party PSM has communication complexity O(\log(N)), O(N).
ePrint: https://eprint.iacr.org/2019/657
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .