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