Multi-party PSM, Revisited: Improved Communication and Unbalanced Communication

Léonard Assouline (1, 2) , Tianren Liu (3)

1 DI-ENS - Département d'informatique - ENS Paris
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
3 University of Washington [Seattle]

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).

Domaines: Informatique [cs]

Léonard Assouline, Tianren Liu. Multi-party PSM, Revisited: Improved Communication and Unbalanced Communication. TCC 2021: Theory of Cryptography, Nov 2021, Raleigh, United States. pp.194-223, ⟨10.1007/978-3-030-90453-1_7⟩. ⟨hal-03413130⟩