Name
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 <= 20), we construct k-party PSM protocols for arbitrary functionality f : [N](k) -> {0, 1}, whose communication complexity is O-k(Nk-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 < eta < 1 whose denominator is <= 20, we construct 2-party PSM protocols for arbitrary functionality f : [N] x [N] -> {0, 1}, whose communication complexity is O(N-eta) for one party, O(N1-eta) for the other. Previously the only known unbalanced 2-party PSM has communication complexity O(log(N)), O(N). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-90453-1_7 | THEORY OF CRYPTOGRAPHY, TCC 2021, PT II |
DocType | Volume | ISSN |
Conference | 13043 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Léonard Assouline | 1 | 0 | 0.34 |
| Tianren Liu | 2 | 0 | 0.34 |