ALMASTY
Multi-Party PSM, Revisited: Improved Communication and Unbalanced Communication
Thursday, January 13, 2022Léonard Assouline
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≤20), we construct k-party PSM protocols for arbitrary functionality f:[N]^k→{0,1}, whose communication complexity is O_k(N^{(k−1)/2}). This improves the former best known upper bounds of O_k(N^{k/2}) for k≥6, O(N^{7/3}) for k=5, and O(N^{5/3}) for k=4.
- For all rational 0<η<1 whose denominator is ≤20, we construct 2-party PSM protocols for arbitrary functionality f:[N]×[N]→{0,1}, whose communication complexity is O(N^η) for one party, O(N^{1−η}) for the other. Previously the only known unbalanced 2-party PSM has communication complexity O(log(N)),O(N).
damien.vergnaud (at) nulllip6.fr