Léonard Assouline
email: leonard.assouline@ens.fr

Tianren Liu
email: tianrenl@uw.edu

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

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 :

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

Introduction

Private Simultaneous Messages (PSM) is a minimal model of secure multi-party computation. It was introduced by Feige, Kilian and Naor [START_REF] Feige | A minimal model for secure computation[END_REF], and was generalized to the multi-party setting by Ishai and Kushilevitz [IK97].

In a PSM protocol for evaluating a k-ary functionality f : [N ] k → {0, 1}, there are k parties. They all share a common random string. For all i ∈ [k], the i-th party holds a private input x i . There is additionally a special party, called the referee. The referee receives one message from each party and is able to compute f (x 1 , . . . , x k ), and should learn no other information about x 1 , . . . , x k .

PSM is studied as an information-theoretic primitive. The key complexity measure is the communication complexity. The common random string is crucial for the model as the common random string is the only mean to protect the privacy against an unbounded adversarial referee, when the k parties cannot communicate with each other.

In the PSM model, there are relatively efficient PSM protocols for computing non-deterministic branching programs [START_REF] Feige | A minimal model for secure computation[END_REF] and modular branching programs [IK97]. But for general functionalities, little is known regarding their communication complexity in the PSM model. Assuming every party holds an input in [N ], the best known lower bound of 2-party PSM is 3 log N - Though the lower bounds are at most polynomial in the total input length, all known upper bounds are exponential, leaving an exponential gap between upper and lower bounds. For any functionality f : [N ] k → {0, 1}, a "naïve" k-party PSM requires O(N k-1 ) communication (the 2-party version was presented in [START_REF] Feige | A minimal model for secure computation[END_REF]). The first novel upper bound is O( √ N ) for 2-party PSM [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF], and it was recently generalized to an O k (N k/2 ) upper bound for k-party PSM [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. In the same paper, Beimel, Kushilevitz and Nissim also further optimize the communication complexity for small k = 3, 4, 5. In particular, they obtain an O(N ) upper bound for 3-party PSM. For k = 4 or 5, they improve the protocol by letting parties jointly emulate their 3-party PSM. Their results are summarized in Table 1.

Our Contributions

In the paper, we present two classes of results: We present new k-party PSM protocols that improve the communication complexity for infinitely many k. We introduce the notion of unbalanced 2-party PSM protocols, which allows a flexible repartition of the communication complexity among the two parties, and we such protocols. k-party PSM protocols. We present a framework for constructing multi-party PSM. The new framework improves the communication complexity upper bounds for infinitely many k. To compute any k-ary functionality f : [N ] k → {0, 1},

• For all k ≤ 20, our framework yields a k-party PSM protocol of communication complexity O(N k-1

2 ).

• For all k such that k + 1 is a prime or a prime power, our framework yields a k-party PSM protocol of communication complexity O k (N k-1

2 ).

• For all k, we conjecture that our framework will yield a k-party PSM protocol of communication complexity O k (N k-1

2 ).

2-party unbalanced PSM protocols. We also present a framework for constructing 2-party PSM protocols with unbalanced communication complexity. The new framework allows us to reduce the message length of one party at the cost of increasing the communication of the other party.

Number of parties [BIKK14]

[BKN18] This work

2 O(N 1/2 ) O(N 1/2 ) O(N 1/2 ) 3 O(N ) O(N ) 4 O(N 5/3 ) O(N 3/2 ) 5 O(N 7/3 ) O(N 2 ) k ≥ 6 O(poly(k) • N k/2 ) 2 O(k) • N k-1 2
for infinitely many k including all k ≤ 20 We offer an almost smooth trade-off between the communication complexity of the two parties. To compute any functionality f :

[N ] × [N ] → {0, 1},
• For every rational η ∈ (0, 1) whose denominator is no more than 20, our framework yields a 2-party PSM protocol, where one party sends O(N η ) bits and the other sends O(N 1-η ) bits.

• For every rational η ∈ (0, 1), we conjecture that our framework will yield a 2-party PSM protocol, where one party sends O η (N η ) bits and the other sends O η (N 1-η ) bits.

To some extent, such a trade-off was known in the literature when η = 0. The first 2-party PSM protocol is of communication complexity O(N ) but is strongly unbalanced: one of the two parties only sends O(log N ) bits [START_REF] Feige | A minimal model for secure computation[END_REF].

Proof Overview

This section presents the main ideas behind our new multi-party PSM protocols. We start with a warm-up example of a 3-party PSM, which is originally constructed by [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. We present it in a way that matches the framework we will later introduce. Then we present a new 5-party PSM to demonstrate the power of our framework. The 5-party PSM example relies on new technique such as "hard terms cancelling". It can be easily generalized into a framework for constructing k-party PSM protocols for any odd k. But we do not formally present this framework in the paper. Instead, in section 3, we develop a modified framework that supports odd as well as even values of k. The modified framework evenly divides every party's input into two halves, this idea was first introduced in [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF]. When we formally present the modified framework in Section 3.1, we use a 4-party PSM as an example.

In section 4, we develop another framework for constructing unbalanced 2-party PSM protocols. Most terminologies and techniques are shared between the framework for k-party and the framework for unbalanced 2-party. Informally, the unbalanced 2-party PSM framework is the "tensor product" of two copies of the k-party framework. When we present the new framework in Section 4.1, we use as an exmaple a 2-party PSM with unbalanced communication O(N 1/3 ), O(N 2/3 ).

Background: 3-Party PSM [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. In this 3-party PSM protocol, three parties hold x 1 , x 2 , x 3 ∈ [N ] respectively. The protocol takes O(N ) communication and allows the referee to learn f (x 1 , x 2 , x 3 ).

Fix a finite field F. Let the i-th party locally computes a unit vector x i ∈ F N . That is, all entries in x i are zero except for x i [x i ] = 1. Let F be the truth table of f represented as an N × N × N array, we have f (x 1 , x 2 , x 3 ) = F, x 1 ⊗ x 2 ⊗ x 3 , where ⊗ denotes the tensor product and •, • denotes the inner product.

Therefore, it is sufficient to construct a 3-party PSM protocol, where the i-th party has input x i ∈ F N (not necessarily being an unit vector) and the referee learns F, x 1 ⊗ x 2 ⊗ x 3 for some public F ∈ F N ×N ×N . We start by letting the i-th party sample random r i ∈ F N and send the one-time padded xi := x i + r i to the referee. Then the referee can compute F, x1 ⊗ x2 ⊗ x3 . We call this term a "masked term", because it is computed from the masked inputs x1 , x2 , x3 . This masked term can be decomposed as the sum of several "pure terms"

F, x1 ⊗ x2 ⊗ x3 = F, x 1 ⊗ x 2 ⊗ x 3 + F, x 1 ⊗ x 2 ⊗ r 3 + F, x 1 ⊗ r 2 ⊗ x 3 + F, r 1 ⊗ x 2 ⊗ x 3 + F, x 1 ⊗ r 2 ⊗ r 3 + F, r 1 ⊗ x 2 ⊗ r 3 + F, r 1 ⊗ r 2 ⊗ x 3 + F, r 1 ⊗ r 2 ⊗ r 3 . (1)
We classify the pure terms into two categories:

Target Term The term F, x 1 ⊗ x 2 ⊗ x 3 . It is the term that the referee should learn as a consequence of the 3-party PSM protocol.

Easy Term All the other terms fall into this category. As the name suggested, there also exist "hard terms", which will be introduced in the next example of 5-party PSM.

The easy terms are called "easy" because each of them can be securely revealed to the referee using only O(N ) communication. More formally, let the parties additionally sample random r 1 , . . . , r 7 ∈ F from their common random string such that r 1 + • • • + r 7 = 0. There exist subprotocols revealing each of

r 1 + F, x 1 ⊗ x 2 ⊗ r 3 , r 2 + F, x 1 ⊗ r 2 ⊗ x 3 , r 3 + F, r 1 ⊗ x 2 ⊗ x 3 , r 4 + F, x 1 ⊗ r 2 ⊗ r 3 , r 5 + F, r 1 ⊗ x 2 ⊗ r 3 , r 6 + F, r 1 ⊗ r 2 ⊗ x 3 , r 7 + F, r 1 ⊗ r 2 ⊗ r 3 (2)
to the referee without leaking any other information, taking at most O(N ) communication.

Assume that such sub-protocols exist, we can easily finish the 3-party PSM: The i-th party sends xi := x i + r i , they use the the aforementioned sub-protocols to reveal (2). The correctness follows almost directly from (1).

The only missing piece is to contruct sub-protocols for computing the terms in (2). Let us discuss them individually:

• For the last term r 7 + F, r 1 ⊗ r 2 ⊗ r 3 , any party (e.g. the first party) can compute it and send it to the referee.

• For the term r 4 + F, x 1 ⊗ r 2 ⊗ r 3 , the first party computes it and sends it to the referee. Similarly for r 5 + F, r 1 ⊗ x 2 ⊗ r 3 and r 6 + F, r 1 ⊗ r 2 ⊗ x 3 .

• For the term r 1 + F, x 1 ⊗ x 2 ⊗ r 3 , both first and second party need to participate. Since the first party knows F, x 1 , r 3 , it can locally compute a vector g ∈ F N such that

r 1 + F, x 1 ⊗ x 2 ⊗ r 3 = r 1 + g, x 2 .
Then they can jointly reveal it to the referee using the PSM for inner product (more details are provided in Section B.1). Similarly for r 2 + F, x 1 ⊗ r 2 ⊗ x 3 and r 3 + F, r 1 ⊗ x 2 ⊗ x 3 .

Example: 5-Party PSM. We will sketch a 5-party PSM protocol for any f :

[N ] 5 → {0, 1} with communication complexity O(N 2 ).
Let F be a finite field. Following the same observation we made in the 3-party PSM example, it is sufficient to construct a PSM protocol for any function of the form (x 1 , . . . , x 5 ) → F, x 1 ⊗• • •⊗x 5 , where ⊗ denotes the tensor product, the i-th party having input x i ∈ F N , F is public and fixed being the truth table of f .

For each Ω ⊆ {1, 2, 3, 4, 5}, parties sample a dimension-|Ω| tensor R Ω ∈ F N |Ω| from the common random string. Define XΩ := R Ω + i∈Ω x i . For example, X{2} := R {2} + x 2 and X{3,4} := R {3,4} + x 3 ⊗ x 4 . Since the communication budget is O(N 2 ), they can perform a PSM sub-protocol so that the referee learns XΩ for all Ω such that |Ω| ≤ 2.

Learning those tensors allows the referee to compute many terms, including F, X{1,2} ⊗ X{3,4} ⊗ X{5} . This term can be decomposed into the sum of the following 8 terms:

F, X{1,2} ⊗ X{3,4} ⊗ X{5} = F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ R {5} + F, x 1 ⊗ x 2 ⊗ R {3,4} ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ R {3,4} ⊗ R {5} + F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ x 5 + F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ R {5} + F, R {1,2} ⊗ R {3,4} ⊗ x 5 + F, R {1,2} ⊗ R {3,4} ⊗ R {5} .
(3) Any term that is formed in the same way as the left-hand side of (3), i.e. F,

XS 1 ⊗ • • • ⊗ XSt for some S 1 + • • • + S t = {1, 2, 3, 4, 5}, is called a masked term. It can be computed by the referee if |S i | ≤ 2 for all i.
Any term that is formed in the same way as the right-hand side of (3), i.e.

F, R S 1 ⊗ • • • ⊗ R St ⊗ x i 1 ⊗ • • • ⊗ x iw for some S 1 + • • • + S t + {i 1 , . . . , i w } = {1, 2, 3, 4, 5}
, is called a pure term. As hinted by equation (3), every masked term is equal to the sum of 2 t pure terms.

The pure terms fall naturally into three categories. In particular, we introduce a new category called hard terms.

Target term The term F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 is called the target term.

Easy term A pure term F, R S 1 ⊗ • • • ⊗ R St ⊗ x i 1 ⊗ • • • ⊗ x iw is easy if w ≤ 3.
Every easy term can be computed using a PSM protocol with communication complexity O(N 2 ). For example, F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ x 5 is an easy term. The 5 th party, based on its view, can compute a tensor G ∈ F N 2 such that F, R {1,2} ⊗ x 3 ⊗ x 4 ⊗ x 5 = G, x 3 ⊗ x 4 . And G, x 3 ⊗ x 4 can be computed using a PSM protocol (Section B.1) with communication complexity O(N 2 ).

Hard term Any pure term that is neither the target term nor an easy term.

Let us ignore the easy terms for now. Then equation (3) can be rewritten as

F, X{1,2} ⊗ X{3,4} ⊗ X{5} = F, x 1 ⊗ • • • ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ R {5} + easy terms.
There is only one hard term left. We would like to cancel out the hard term by combining a few masked terms. Let us consider the following masked terms:

F, X{1,2} ⊗ X{3} ⊗ X{4,5} , F, X{1,2} ⊗ X{3,5} ⊗ X{4} and F, X{1,2} ⊗ X{3} ⊗ X{4} ⊗ X{5} . F, X{1,2} ⊗ X{3} ⊗ X{4,5} = F, x 1 ⊗ • • • ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ R {3} ⊗ x 4 ⊗ x 5 + easy terms, F, X{1,2} ⊗ X{3,5} ⊗ X{4} = F, x 1 ⊗ • • • ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4} ⊗ x 5 + easy terms, F, X{1,2} ⊗ X{3} ⊗ X{4} ⊗ X{5} = F, x 1 ⊗ • • • ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ R {3} ⊗ x 4 ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4} ⊗ x 5 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ R {5}
+ easy terms.

By carefully combining these masked tensors, we have

F, X{1,2} ⊗ X{3,4} ⊗ X{5} + F, X{1,2} ⊗ X{3} ⊗ X{4,5} + F, X{1,2} ⊗ X{3,5} ⊗ X{4} -F, X{1,2} ⊗ X{3} ⊗ X{4} ⊗ X{5} = 2 • F, x 1 ⊗ • • • ⊗ x 5 + easy terms. (4)
Equation (4) shows us how to construct the desired PSM protocol. All of the masked tensors on the left-hand side of (4) can be computed by the referee. The parties perform a PSM sub-protocol so that the referee learns the sum of these easy terms. (The details are demonstrated in the last example of 3-party PSM, and are explained in Section 3.2.) Then from equation (4), the referee learns 2

• F, x 1 ⊗ • • • ⊗ x 5 .
As long as F is a finite field in which 2 = 0, the referee has learned the target term. The protocol takes a communication cost of O(N 2 ) field elements.

Related Works

Besides [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF][START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF], our construction of PSM protocols is also inspired by the progress in Conditional Disclosure of Secrets (CDS). Until recently, CDS had a similar exponential gap between known upper and lower bounds. CDS can be viewed as a variant of PSM where the referee knows all but 1 bit of the input: Consider the 2-party case and let [N ] Gay, Kerenidis and Wee constructed 2-party CDS with smooth communication complexity trade-off between the two party [START_REF] Gay | Communication complexity of conditional disclosure of secrets and attribute-based encryption[END_REF]. In particular, for any η ∈ [0, 1], they constructed a 2-party CDS protocol where one party sends O(N η ) bits and the other sends O(N 1-η ) bits.

In [ABF + 19, CGO21], constructions of ad hoc PSM are presented. In this framework, there are k parties, but only a subset of them will perform the computation. This notion, expanded in [START_REF] Beimel | Ad hoc PSM protocols: Secure computation without coordination[END_REF], was shown to imply obfuscation.

Preliminaries

Let N := {0, 1, . . .} denote the set of all natural numbers, and let [n] := {1, . . . , n}. In this paper, F denotes a field, R denotes a finite commutative ring. For some prime power p, let F p denote the unique finite field of order p. A vector will be denoted by a bold face lowercase letter. For a vector v, let v[i] denote its i-th entry.

Tensor

A tensor refers to the generalization of vectors and matrices which have multiple indices. Roughly speaking, a tensor is a multi-dimensional array. In the paper, a tensor will be denoted by a bold face capital letter. A k-dimensional tensor T ∈ F n 1 ×n 2 ×...×n k is essentially an array of size

n 1 × n 2 × • • • × n k . The entries in T are indexed by (i 1 , . . . , i k ) ∈ [n 1 ] × • • • × [n k ]
, and denoted by T[i 1 , . . . , i k ]. A tensor can also be viewed as a representation of a multi-linear function: any k-linear function f :

F n 1 × F n 2 × . . . × F n k → F can be uniquely determined by its coefficient tensor F ∈ F n 1 ×...×n k , such that f (v 1 , . . . , v k ) = i 1 ∈[n 1 ],••• ,i k ∈[n k ] F[i 1 , . . . , i k ] • v 1 [i 1 ] • . . . • v k [i k ].
(5)

The inner product of two tensors S, T ∈ F n 1 ×n 2 ×...×n k is defined as

S, T := i 1 ∈[n 1 ],••• ,i k ∈[n k ] S[i 1 , . . . , i k ] • T[i 1 , . . . , i k ]. Given two tensors S ∈ F n 1 ×...×n k and T ∈ F m 1 ×...×m , we define S ⊗ T, their tensor product. It is a tensor in F n 1 ×...×n k ×m 1 ×...×m such that (S ⊗ T)[i 1 , . . . , i k , j 1 , . . . , j ] = S[i 1 , . . . , i k ] • T[j 1 , . . . , j ].
Using the notation of inner product and tensor product, Equation (5) can also be written as

f (v 1 , . . . , v k ) = F, v 1 ⊗ . . . ⊗ v k .

Private Simultaneous Messages

Definition 1 (private simultaneous message). A k-party functionality is a mapping f : X 1 × . . . × X k → Y, where X 1 , . . . , X k are its input spaces and Y is its output space.

A private simultaneous message (PSM) protocol for a functionality f consists of a randomness space W and a tuple of deterministic functions (M 1 , . . . , M k , R)

M i : X i × W → {0, 1} cc i , for all i ∈ [k], R : {0, 1} cc 1 × . . . {0, 1} cc k → {0, 1},
where cc i is the communication complexity of the i-th party, cc := cc 1 + . . . + cc k is the total communication complexity.

A perfectly secure PSM protocol for f satisfies the following properties:

(correctness.) For all input tuple (x 1 , . . . , x k ) ∈ X 1 × . . . × X k and randomness w ∈ W, R(M 1 (x 1 , w), . . . , M k (x k , w)) = f (x 1 , . . . , x k ) (privacy.
) There exists a randomized simulator S, such that for any input (x 1 , . . . ,

x k ) ∈ X 1 × . . . × X k , the joint distribution of M 1 (x 1 , w), . . . , M k (x k , w) is the same as the distributions of S(f (x 1 , . . . , x k ))
, where the distributions are taken over w ← W and the coin tosses of S.

Randomized Encoding

Randomized encoding is a primitive closely relate to PSM. The randomized encoding of a function f is a randomized function f . The output f (x, w), where w denotes the randomness, contains sufficient information to recover f (x) and no other information about x.

Definition 2 (randomized encoding). A randomized encoding for a function f : X → Y consists of a randomized encoding function f : X × W → Ŷ and a deterministic decoding function R : Ŷ → Y, where W denotes the randomness space and Ŷ denotes the coding space.

A perfectly secure randomized encoding satisfies the following properties:

(correctness.) For all x ∈ X and randomness w ∈ W,

R( f (x, w)) = f (x)
(privacy.) There exists a randomized simulator S, such that for any input x ∈ X , the joint distribution of f (x, w) is the same as the distributions of S(f (x)), where the distributions are taken over w ← W and the coin tosses of S.

Follows directly from the definitions, (M 1 , . . . ,

M k , R) is a PSM protocol for f if and only if ( f , R) is a randomized encoding for f , where f (x 1 , . . . , x k , w) := (M 1 (x 1 , w), . . . , M k (x k , w)).
In other words, PSM is a special form of randomized encoding, where the input is divided into a few portions, and each bit of the encoding only depends on the randomness and one portion of the input.

New Multi-party PSM Protocols

In this section, we present one of our main results: for many k, every functionality f :

[N ] k → {0, 1} admits a PSM protocol of communication complexity O k (N k-1 2 ). Theorem 3.1. Let f : [N ] k → {0, 1} be an arbitrary k-party functionality.
• There is a k-party PSM protocol for f with communication and randomness complexity

O(N k-1 2 ), if k ≤ 20.
• There is a k-party PSM protocol for f with communication and randomness complexity

O k (N k-1
2 ), if k + 1 is a prime or a prime power.

In this section, we prove a stronger statement. Let F be a finite field, consider the following auxiliary k-party functionality Aux k N :

k-party functionality Aux k N • The i-th party has input x 2i-1 , x 2i ∈ F √ N • The output is F, x 1 ⊗ • • • ⊗ x 2k
, where F is public and fixed

As shown in the beginning of Section 3.1, a PSM protocol for Aux k N implies a PSM for f : [N ] k → {0, 1} with the same communication complexity. The reduction consists of having F be the truth table of f . We will present a framework of constructing k-party PSM for Aux

k N , whose communication complexity is O k (N k-1
2 ). Roughly speaking, the framework reduces the problem to a system of linear equations. A solution of the system implies a PSM protocol with the desired communication complexity. Therefore, we should rule out the possibility that the induced system has no solution. We partially achieve such a goal. We solve the induced system for infinitely many k:

• For all k ≤ 20, we checked that the induced system of linear equations is solvable. For small k we solve the system by hand, and for larger k we verified it with a computer program.

• For all k such that k + 1 is a prime power, we prove that the system is solvable.

Backed by the above observations, we strongly believe the induced system is solvable for all k.

Conjecture 1. Let f : [N ] k → {0, 1} be an arbitrary k-party functionality. There is a k-party PSM protocol for f with communication and randomness complexity O k (N k-1

2 ).

Organization Section 3.1 presents our framework for constructing multi-party PSM, introduces new notations, and gives a 4-party PSM as a concrete example. The following Sections 3.2, 3.3, 3.4 are independent. Section 3.2 provides more technical detail of the PSM protocols yielded by our framework. Section 3.3 shows how the framework works for small k, and Section 3.4 shows how the framework works for any integer k such that k + 1 is a prime power.

A Framework for Multi-party PSM

As mentioned in the beginning of Section 3, the functionality f : [N ] k → {0, 1} can be reduced to functionality Aux k N . The reduction works as follows: Let x 1 , . . . , x k be the input, the j-th party has input x j ∈ [N ]. We evenly divide

x j into x 2j-1 , x 2j ∈ [ √ N ]. For each i ∈ [2k], let x i := e x i ∈ F √ N
be the x i -th standard unit vector. We reduce f to Aux k N :

f (x 1 , . . . , x 2k ) = F, x 1 ⊗ . . . ⊗ x 2k
where F is the truth-table of f . For the remainder of the section, it is thus sufficient to construct a PSM protocol for Aux k N . For each non-empty Ω ⊆ [2k], our protocol will sample a random dimension-|Ω| tensor

R Ω ∈ R ( √ N ) |Ω| from the common random string 1 . Define XΩ := R Ω + i∈Ω x i . E.g., X{2} := R {2} + x 2 , X{3,4} := R {3,4} + x 3 ⊗ x 4 . Within the communication complexity budget O(N k-1
2 ), we can let the referee learn XΩ for all Ω such that |Ω| ≤ k -1 (more details in Section 3.2). The referee does not learn extra information as XΩ is one-time padded by R Ω . For example when k = 4, we can let the referee learn tensors X{1} , X{2} , . . . , X{8} , X{1,2} , X{1,3} , . . . , X{7,8} , X{1,2,3} , X{1,2,4} , . . . , X{6,7,8} . The referee learns those tensor by having subsets of the parties recursively perform PSM ptocols with a smaller number of parties, so that the referee learns the required information. Learning those tensors allows the referee to compute many terms including F, X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} , which equals to the 1 A note on the randomness complexity: The final protocol uses RΩ only if |Ω| ≤ k -1.

sum of the following 8 terms,

F, X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} = F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ x 7 ⊗ x 8 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ R {7,8} + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ R {7,8} + F, R {1,2,3} ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ x 7 ⊗ x 8 + F, R {1,2,3} ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ R {7,8} + F, R {1,2,3} ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 + F, R {1,2,3} ⊗ R {4,5,6} ⊗ R {7,8} . (6)
Before we continue, let us introduce a few notations to describe the terms appearing in (6). The term (tensor) on the left hand side of the equation will be called a masked term (masked tensor). The terms (tensors) on the right hand side of the equation will be called pure terms (pure tensors).

Definition (masked tensor & masked term). A masked tensor is a tensor product XΩ 1 ⊗ . . . ⊗ XΩt2 such that Ω 1 , . . . , Ω t are disjoint and their union equals [2k]. The shape of a masked tensor XΩ 1 ⊗ . . . ⊗ XΩt is the multiset {|Ω 1 |, . . . , |Ω t |}. The inner product of a masked tensor and F is called a masked term.

For any multiset P such that sum(P ) = 2k, let X(P ) denote the sum of all masked tensors of shape P , let F, X(P ) denote the sum of all masked terms of shape P . We thus have F, X(P ) = F, X(P ) .

Definition (pure tensor & pure term). A pure tensor is a tensor product R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗ x iw such that {i 1 , . . . , i w }, Ω 1 , . . . , Ω t are disjoint and their union equals [2k]. The shape of a pure tensor

R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗ x iw is the multiset {|Ω 1 |, . . . , |Ω t |}.
The inner product of a pure tensor and F is called a pure term.

For any multiset P such that sum(P ) ≤ 2k, let R(P ) denote the sum of all pure tensors of shape P , let F, R(P ) denote the sum of all pure terms of shape P . We thus have F, R(P ) = F, R(P ) .

The pure terms (pure tensors) can be grouped into 3 natural categories: target term (target tensor) F, x 1 ⊗ . . . ⊗ x 2k is called the target term as it is desired functionality output. The corresponding tensor x 1 ⊗ . . . ⊗ x 2k is called the target tensor.

easy terms (easy tensors)

A pure tensor R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗
x iw is called an easy tensor if at most k +1 out of the 2k dimensions are contributed by vector x i 's (i.e., w ≤ k +1). The corresponding term is called an easy term. Every easy term admits a PSM protocol with communication complexity no more than O(poly(k)

• N k-1
2 ) field elements (more details in Section 3.2). hard terms (hard tensors) The rest.

With this terminology, we can give an overview of our PSM protocol. As the referee can learn XΩ for all Ω such that |Ω| ≤ k -1, the referee can compute any masked term of shape P if max(P ) ≤ k -1. As suggested by Equation (6), every masked term is the linear combination of a few pure terms. Ideally, the referee only has to combine some computable masked terms, so that all the hard terms cancel out, resulting a linear combination of the target term and easy terms: a linear combination of masked terms = target term + some easy terms.

(7)

Once we are in this ideal case, the easy terms can be easily removed by standard techniques, resulting the desired k-party PSM protocol for Aux k N . (More details are presented in Section 3.2.) Therefore, the task is reduced to a linear algebra problem: is the target term (resp. tensor) spanned by the referee-computable masked terms (resp. tensors) and easy terms (resp. tensors)?

When solving such linear algebra problem, it is fair to assume that the solution is symmetric. (Otherwise, assume that a solution that looks like ( 7) is asymmetric, it can be symmetrized by applying the symmetric sum on both sides.)

We have defined the (symmetric) sum of terms or tensors of the same shape. For example when k = 4, X(3, 3, 2) is defined as the sum of all masked tensors XΩ 1 ⊗ XΩ 2 ⊗ XΩ 3 such that the multiset

{|Ω 1 |, |Ω 2 |, |Ω 3 |} equals {3, 3, 2}, i.e. X(3, 3, 2) := X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} + X{1,2,3} ⊗ X{4,5,7} ⊗ X{6,8} + X{1,2,3} ⊗ X{4,5,8} ⊗ X{5,6} + X{1,2,3} ⊗ X{4,6,7} ⊗ X{5,8} + . . . + X{3,4,5} ⊗ X{6,7,8} ⊗ X{1,2} .
Let's revisit Equation (6), F, X{1,2,3} ⊗ X{4,5,6} ⊗ X{7,8} a masked term of shape {3, 3, 2}

= F, x 1 ⊗ • • • ⊗ x 8 a pure term of shape {} + F, x 1 ⊗ • • • ⊗ x 6 ⊗ R {7,8} a pure term of shape {2} + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 + F, R {1,2,3} ⊗ x 4 ⊗ • • • ⊗ x 8 pure terms of shape {3} + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ R {4,5,6} ⊗ R {7,8} + F, R {1,2,3} ⊗ x 4 ⊗ x 5 ⊗ x 6 ⊗ R {7,8} pure terms of shape {3, 2} + F, R {1,2,3} ⊗ R {4,5,6} ⊗ x 7 ⊗ x 8 a pure term of shape {3, 3} + F, R {1,2,3} ⊗ R {4,5,6} ⊗ R {7,8}
a pure term of shape {3, 3, 2}

.

By applying a symmetric sum on both sides, we get

F, X(3, 3, 2) = 280 • F, R() the target term + 10 • F, R (2)
hard pure terms

+ 10 • F, R(3) + F, R(3, 2) + F, R(3, 3) + F, R(3, 3, 2)
easy pure terms .

As another example of the symmetric sum of masked term that the referee can compute,

F, X(2, 2, 2, 2) = 105 • F, R() target term + 15 • F, R (2)
hard pure terms

+ 3 • F, R(2, 2) + F, R(2, 2, 2) + F, R(2, 2, 2, 2)
easy pure terms

.

By carefully combining the above two equations, we get

3 • F, X(3, 3, 2) -2 • F, X(2, 2, 2, 2) = 630 • F, R() + easy terms, (8)
which induces a 4-party PSM whose communication complexity is O(N 3/2 ), if we let F to be any field in which 630 = 0. (Section 3.2 explains how Equation (8) implies a 4-party PSM with desired communication complexity.)

In the general k-party case, for each legit shape P of masked term (i.e., P is a multiset consisting of positive integers and sum(P ) = 2k),

F, X(P ) = Q⊆P α(Q) • F, R(P \ Q) , (9)
where P \ Q is the multiset subtraction and

α(Q) := (sum(Q))! i∈Q i! • m∈Z + (number of m's in Q)! (10)
is the following combinatoric number: α(Q) is the number of ways to partition sum(Q) distinct elements into some unordered subsets S 1 , . . . , S t such that Q = {|S 1 |, . . . , |S t |}. Equations ( 9), (10) are proved in Appendix A.

The Induced PSM Protocol

In order to develop the previous section smoothly, we skipped some technique details in Section 3.1.

In this section, we will show how to construct a k-party PSM protocol assuming that the target term is spanned by referee-computable masked terms and easy pure terms. By our assumption, there are referee-computable masked terms X(1) , . . . , X(t) , easy pure terms R (1) , . . . , R (s) , and coefficients a 1 , . . . a t , b 1 , . . . , b s ∈ F such that

F, x 1 ⊗ • • • ⊗ x 2k = t j=1 a j X(j) + s j=1 b j R (j) . (11)
A k-party PSM for f , together with its correctness and security, is yielded by the following facts:

• Fact I: s j=1 b j R (j) and XΩ for all 0 < |Ω| ≤ k -1 form a randomized encoding of F, x 1 ⊗ • • • ⊗ x 2k . That is, they contain the sufficient information to recover F, x 1 ⊗ • • • ⊗ x 2k , and they are garbled with additional randomness so that no other information can be recovered.

• Fact II: For every Ω ⊆ [2k] such that 0 < |Ω| ≤ k -1, there is a PSM protocol for XΩ with communication complexity poly(k) • N k-1 2 field elements.

• Fact III: There is a PSM protocol for s j=1 b j R (j) with communication complexity poly(k)

• s • N k-1 2 field elements.
The k-party PSM for f works as the follows: For each Ω ⊆ [2k] such that 0 < |Ω| ≤ k -1, use the PSM guaranteed by Fact II to reveal XΩ to the referee. Use the PSM guaranteed by Fact III to reveal s j=1 b j R (j) to the referee. Then Fact I allows the referee to compute the output from Equation (11).

Proof of Fact I. Equation (11) shows that F, x 1 ⊗• • •⊗x 2k can be computed from the encoding. Moreover, the distribution of the encoding is perfectly simulatable: The joint distribution of tensors XΩ for 0 < |Ω| ≤ k -1 is uniform distribution, as they are independently one-time padded. Then the value of s j=1 b j R (j) is uniquely determined by equation (11).

Proof of Fact II. Each coordinate of X Ω is defined as

X{j 1 ,...,jt} [i 1 , . . . , i t ] = R {j 1 ,...,jt} [i 1 , . . . , i t ] + x j 1 [i 1 ] • . . . • x jt [i t ],
which is an arithmetic formula of size O(k). Thus each coordinate has a PSM protocol with communication complexity poly(k) field elements [IK00].

Proof of Fact III. Sample random c 1 , . . . , c s ∈ F from the common random string such that c 1 + . . . + c s = 0. Then it's sufficient to construct a PSM protocol for computing b j R (j) + c j for each j. Say this easy pure term

R (j) is F, R Ω 1 ⊗ . . . ⊗ x i 1 ⊗ . . . ⊗ x iw .
By our definition of an easy term, w ≤ k + 1. There exists a special party, such that the other parties hold at most k -1 of x i 1 , . . . , x iw . When w = k + 1, the special party is the one who holds two of x i 1 , . . . , x iw (the existence is guaranteed by the pigeonhole principle). W.l.o.g. assume that the other parties hold x i 1 , . . . , x i w such that w ≤ k -1. Then the special party knows a dimension-w tensor G (which is determined by its input and b

j , R Ω 1 , R Ω 2 , . . . ) such that b j R (j) + c j = G, x i 1 ⊗ . . . ⊗ x i w + c j ,
which admits a PSM protocol (presented in Section B.1) with communication complexity O(poly(k)• N w /2 ) field elements.

When k is Small

As shown in Section 3.1, to construct PSM protocol for Aux k N with communication complexity

O k (N k-1
2 ), it is sufficient to prove the target term is spanned by the referee-computable masked terms and easy pure terms. In this section, we verify the condition holds for all k ≤ 20, which proves the first bullet of Theorem 3.1. However, we do not have a general construction of such linenar systems of equations for an arbitrary k.

The case when k = 2 was solved by [START_REF] Beimel | On the cryptographic complexity of the worst functions[END_REF]. Our framework yields the same protocol from F, X(1, 1, 1, 1) = F, R() + easy terms.

The case when k = 3 was solved by [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF]. Our framework yields a similar protocol from F, X(2, 2, 2) = F, R() + easy terms.

The case when k = 4 is solved in section 3.1.

For k = 5, consider the following two masked terms,

F, X(4, 4, 2) = 1575 • F, R() + 35 • F, R(2) + easy terms, F, X(4, 2, 2, 2) = 3150 • F, R() + 210 • F, R(2) + easy terms.
We have 6 • F, X(4, 4, 2) -F, X(4, 2, 2, 2) = 6300 • F, R() + easy terms, which induces a 5-party PSM with communication complexity O(N 2 ).

For k = 6, consider the following masked terms

    F, R() F, R(2) F, R (4)

  + easy terms

Therefore, 14 • F, X(4, 4, 4, 2) -175 • F, X(6, 6, 2) -105 • F, X(6, 4, 4) = -11036025 • F, R() + easy terms, which induces a 7-party PSM with communication complexity O(N3 ). For larger k, we wrote a simple program 3 to check if the target term can be spanned by refereecomputable masked terms and easy terms. For simplicity, our program requires specifying the finite field in advance. Our program verifies that the framework yields a PSM protocol with c.c. O(N k-1 2 ) for every k ≤ 20. For example when k = 20, our program found: which induces a PSM protocol with c.c. O(N 9.5 ).

F, R() = 2895 • F, X(

When k + 1 is a Prime Power

As shown in Section 3.1, to construct PSM protocol for Aux k N with communication complexity

O k (N k-1
2 ), it is sufficient to prove the target term is spanned by the referee-computable masked terms and easy pure terms. In this section, we prove that the condition holds for all k such that k + 1 is a prime power, which proves the second bullet of Theorem 3.1.

When k + 1 is a prime p or a prime power p e , we obtain a simple k-party PSM, by doing computations in the finite field F p .

Proof. Consider the symmetric sum of all masked terms of shape {k -1, 1, . . . , 1} F, X(k -1, 1, . . . ,

1 k+1 1's ) = k+1 i=0 α(k -1, 1, . . . , 1 k+1-i 1's ) • F, R(1, . . . , 1 i 1's ) + k+1 i=0 α( 1, . . . , 1 k+1-i 1's ) • F, R(k -1, 1, . . . , 1 i 1's ) = α(k -1, 1, . . . , 1 k+1 1's ) • F, R() + k-2 i=1 α(k -1, 1, . . . , 1 k+1-i 1's ) • F, R(1, . . . , 1 i 1's
) + easy terms.

(12) (Recall that a pure term of shape P is easy iff sum(P ) ≥ k -1.) W.l.o.g. assume k > 2. By definition, α(k -1, 1, . . . , In this section, we prove a stronger statement. Let F be a finite field, consider the following auxiliary 2-party functionality Aux 2 k,N :

1 t 1's ) = k-1+t k-1 . Lemma 3.3 shows that α(k -1, 1, . . . , 1 k+1 1's ) = 2k k-1 ≡ 1 mod p, while α(k -1, 1, . . . , 1 k+1-i 1's ) = 2k-i k-1 is a multiple of p for all 1 ≤ i ≤ k -2. Therefore, F, X(k -1, 1, . . . , 1 k+1 1's ) = F, R() +
2-party functionality Aux 2 k,N • Alice has input x 1 , . . . , x k ∈ F k √ N • Bob has input y 1 , . . . , y k ∈ F k √ N • The output is F, x 1 ⊗ . . . ⊗ x k ⊗ y 1 ⊗ . . . ⊗ y k , where F is public and fixed A PSM protocol for Aux 2 k,N implies a PSM for f : [N ] × [N ] → {0, 1}
with the same communication complexity of each party. The reduction consists of having F be the truth table of f . We present a framework for the construction of 2-party PSM protocols for Aux 2 k,N , where Alice sends O η (N η ) bits and Bob sends O η (N 1-η ) bits, for all η ∈ { 1 k , . . . , k-1 k }. Similar to the framework in Section 3, the framework in this section also reduces the problem to a system of linear equations. A solution of the system implies a 2-party PSM protocol with the desired communication complexity. By verifying with a computer, we find that our framework works well for all η whose denominator is no larger than 20. Backed by those observations, we believe that our framework allows for a smooth trade-off between the communication complexity of Alice and Bob: Conjecture 2. For any functionality f : [N ] × [N ] → {0, 1}, and any 0 < η < 1, there is a 2-party PSM protocol for f with unbalanced communication complexity O η (N η ), O η (N 1-η ).

Organization Section 4.1 presents our framework for constructing multi-party PSM, introduces new notations, and gives as a concrete example a 2-party PSM with communication O(N 1/3 ), O(N 2/3 ). The following Sections 4.2, 4.3 are independent. Section 4.2 provides more technical detail of the PSM protocols yielded by our framework. Section 4.3 shows how the framework works for small k.

A Framework for 2-party PSM

Consider a rational η = d k ∈ (0, 1). Let F be a finite commutative ring that we will fix later. All the operations are within ring F unless otherwise specified.

As mentioned in the beginning of Section 4, there is an non-interactive reduction from the functionality f :

f (x 1 , . . . , x k , y 1 , . . . , y k ) = F, x 1 ⊗ . . . ⊗ x k ⊗ y 1 ⊗ . . . ⊗ y k .
where F is the truth-table of f . For the remainder of the section, it is thus sufficient to construct a PSM protocol for Aux 2 k,N . For every Ω ⊆ [k], our protocol will sample random R Ω , S Ω ∈ F ( k √ N ) |Ω| from the common random string. Let XΩ := R Ω + i∈Ω x i and ȲΩ := S Ω + i∈Ω y i .

As the communication complexity of Alice is O η (N d k ), she can send XΩ to the referee for every Ω that |Ω| ≤ d. So far no information is leaked as XΩ is one-time padded by R Ω . Similarly, Bob can send ȲΩ for every Ω that |Ω| ≤ k -d.

There are many meaningful terms that the referee can compute once he receives ( XΩ ) |Ω|≤d and ( ȲΩ ) |Ω|≤k-d . For example, when η = d/k = 1/3, the referee can compute:

F, X{1} ⊗ X{2} ⊗ X{3} ⊗ Ȳ{1,2} ⊗ Ȳ{3} = F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ S {3} + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ S {1,2} ⊗ S {3} + . . . (28 other terms) + F, R {1} ⊗ R {2} ⊗ R {3} ⊗ S {1,2} ⊗ S {3} .
(13) Before we continue, we have to introduce a few notations. We will define shape, masked tensor, pure tensor, easy & hard tensor, etc., in the same way as in Section 3.1.

Definition (masked tensor & masked term

). An Alice-side masked tensor is a tensor product XΩ 1 ⊗ . . . ⊗ XΩt such that Ω 1 , . . . , Ω t are disjoint and their union equals [k]. The shape of an Alice-side masked tensor XΩ 1 ⊗ . . . ⊗ XΩt is the multiset {|Ω 1 |, . . . , |Ω t |}. Bob-side masked tensors are defined symmetrically.

The tensor product of an Alice-side masked tensor and a Bob-side masked tensor is called a masked tensor. The inner product of F and a masked tensor is called a masked term.

An Alice-side masked tensor of shape P is referee-computable if max(P ) ≤ d. A Bob-side masked tensor of shape Q is referee-computable if max(Q) ≤ k -d. An masked tensor (and its corresponding masked term) is called referee-computable if it's the tensor product of a refereecomputable Alice-side masked tensor and a referee-computable Bob-side masked tensor.

Definition (pure tensor & pure term). An Alice-side pure tensor is a tensor product R Ω 1 ⊗ . . . ⊗ R Ωt ⊗ x i 1 ⊗ . . . ⊗ x iw such that {i 1 , . . . , i w }, Ω 1 , . . . , Ω t are disjoint and their union equals [k]. The shape of an Alice-side masked tensor R Ω 1 ⊗. . .⊗R Ωt ⊗x i 1 ⊗. . .⊗x iw is the multiset {|Ω 1 |, . . . , |Ω t |}.
Bob-side pure tensors are defined symmetrically.

The tensor product of an Alice-side pure tensor and a Bob-side pure tensor is called a pure tensor. The inner product of a pure tensor and F is called a pure term.

For any legit shape, let R(P ) denote the sum of all Alice-side pure tensor whose shape is P . Similarly, define Bob-side pure tensor sum S(P ).

Let's go back to the example when η = 1/3: examine the pure terms on the right side of equation ( 13), and check which of them has a 2-party PSM with communication complexity O(N

1 3 ), O(N 2 3 ).
• The term F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 is the desired functionality.

• The term F, x 1 ⊗ x 2 ⊗ x 3 ⊗ S {1,2} ⊗ y 3 has a PSM protocol with communication complexity O(N 1 3 ). Because Alice knows a vector g (which is determined by F, Alice's input and randomness

(R Ω ) Ω , (S Ω ) Ω ) such that F, x 1 ⊗ x 2 ⊗ x 3 ⊗ S {1,2} ⊗ y 3 = g, y 3 . • The term F, S {1} ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 admits a PSM protocol with unbalanced commu- nication complexity O(N 1 3 ), O(N 2 3 ). Because Bob knows a dimension-2 tensor G such that F, S {1} ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 = x 2 ⊗ x 3 , G . (This PSM is presented in Section B.2.)
The discussion above hints at the right classification of pure tensors.

target tensor The only Alice-side target tensor is

x 1 ⊗ • • • ⊗ x k . The only Bob-side target tensor is y 1 ⊗ • • • ⊗ y k . The only target tensor is x 1 ⊗ • • • ⊗ x k ⊗ y 1 ⊗ • • • ⊗ y k .
easy tensor An Alice-side pure tensor of shape P is called easy if sum(P )

≥ d. A Bob-side pure tensor of shape Q is called easy if sum(Q) ≥ k -d. A pure tensor R ⊗ S is called easy if either R or S is easy.
hard tensor The rest.

The inner product of F and a target/easy/hard tensor is called a target/easy/hard term. Then, equation ( 13) can be rewritten by grouping and ignoring the easy terms:

F, X{1} ⊗ X{2} ⊗ X{3} ⊗ Ȳ{1,2} ⊗ Ȳ{3} = F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ y 3 + F, x 1 ⊗ x 2 ⊗ x 3 ⊗ y 1 ⊗ y 2 ⊗ S {3} + easy terms
.

By a symmetric sum, we get

F, X(1, 1, 1) ⊗ Ȳ(2, 1) = 3 • F, R() ⊗ S() target + F, R() ⊗ S(1) + easy terms.
Similarly, we have decomposed another referee-computable term

F, X(1, 1, 1) ⊗ Ȳ(1, 1, 1) = F, R() ⊗ S() target + F, R() ⊗ S(1) + easy terms.
Combine them to cancel out the hard terms:

F, X(1, 1, 1) ⊗ Ȳ(2, 1) -F, X(1, 1, 1) ⊗ Ȳ(1, 1, 1) = 2 • F, R() ⊗ S() + easy terms.
Thus, by setting F to be any finite field where 2 = 0, the above equation induces a 2-party PSM protocol with unbalanced communication complexity O(N

1 3 ), O(N 2 3 ).
In general, a masked term F, X(P ) ⊗ Ȳ(Q) can be decomposed into pure terms by

X(P ) = P ⊆P α(P ) X(P \ P ), Ȳ(Q) = Q ⊆Q α(Q ) Ȳ(Q \ Q ), F, X(P ) ⊗ Ȳ(Q) = P ⊆P Q ⊆Q α(P )α(Q ) F, X(P \ P ) ⊗ Ȳ(Q \ Q ) .
with the combinatoric number α defined as in Section 3.1. The first two equations are essentially the same as equation ( 9) and they imply the third equation.

To construct a PSM protocol of the desired unbalanced communication complexity, it is sufficient to show the target term is spanned by the referee-computable masked terms and the easy terms. Namely, the target term = a linear combination of referee-computable masked terms + a linear combination of easy terms.

(

) 14
The details of how this sufficient condition implies a PSM with desired communication complexity is presented in Section 4.2.

This sufficient condition of form ( 14) is unfortunately too combinatorically hard to use in practice, especially since we are going to use a program to search for the proof for different values of η. There are too many distinct masked terms and pure terms -their number is equal to the number of pairs of legit shapes (P, Q).

Fortunately, we come up with a simpler sufficient condition. A PSM protocol of the desired unbalanced communication complexity exists if both of the following hold:

• The Alice-side target tensor is spanned by referee-computable Alice-side masked tensors and Alice-side easy tensors;

• The Bob-side target tensor is spanned by referee-computable Bob-side masked tensors and Bob-side easy tensors.

The proof is quite straight-forward: Assume the new sufficient condition, a linear combination of referee-computable Alice-side masked tensors = R() + Alice-side easy tensors, a linear combination of referee-computable Bob-side masked tensors = S() + Bob-side easy tensors.

The tensor product of the above two equations is a linear combination of referee-computable masked tensors = R() ⊗ S() + a linear combination of easy tensors.

Multiplying both sides of the above equation with F yields the desired sufficient condition of form (14).

When η has a Small Denominator

Section 4.1 proves a sufficient condition that implies 2-party PSM protocols with the desired unbalanced communication complexity. In this section, we will verify that the sufficient condition holds for all rational η ∈ (0, 1) whose denominator is no larger than 20. Theorem 4.1 follows as a consequence.

For η = 1/3, the 2-party PSM protocol in Section 4.1 is also induced by X(1, 1, 1) = R() + Alice-side easy tensors, Ȳ(2, 1) -Ȳ(1, 1, 1) = 2 • S() + Bob-side easy tensors.

For η = 1/4, a 2-party PSM protocol with c.c. O(N 1/4 ), O(N 3/4 ) is induced by

X(1, 1, 1, 1) = R() + Alice-side easy tensors, Ȳ(1, 1, 1, 1) + 2 • Ȳ(3, 1)
+ Ȳ(2, 2) -Ȳ(2, 1, 1) = 6 • S() + Bob-side easy tensors.

For η = 1/5, a 2-party PSM protocol with desired c.c. is induced by For larger denominators, we wrote a computer program 4 to assist us in the proof. For example, for η = 7/20, a 2-party PSM with desired c.c. is induced by ΣR() = Alice-side easy tensors + 18 • Σ X(7, 7, 6) + 10 • Σ X(7, 7, 5, 1) + 14 • Σ X(7, 7, 4, 2) + 14 • Σ X(7, 7, 4, 1, 1) + 17 • Σ X(7, 7, 3, 3) + 20 • Σ X(7, 7, 3, 2, 1) + 20 • Σ X(7, 7, 3, 1, 1, 1) + 10 • Σ X(7, 7, 2, 2, 2) + 10 • Σ X(7, 7, 2, 2, 1, 1) + 10 • Σ X(7, 7, 2, 1, 1, 1, 1) + 10 • Σ X(7, 7, 1, 1, 1, 1, 1, 1) + 6 • Σ X(7, 6, 6, 1) + 19 • Σ X(7, 6, 5, 2) + 19 • Σ X(7, 6, 5, 1, 1) + 21 • Σ X(7, 6, 4, 3) + 22 • Σ X(7, 6, 4, 2, 1) + 22 • Σ X(7, 6, 4, 1, 1, 1) + 7 • Σ X(7, 6, 3, 3, 1) + 15 • Σ X(7, 6, 3, 2, 2) + 15 • Σ X(7, 6, 3, 2, 1, 1) + 15 • Σ X(7, 6, 3, 1, 1, 1, 1) + 19 • Σ X(7, 6, 2, 2, 2, 1) + 19 • Σ X(7, 6, 2, 2, 1, 1, 1) + 19 • Σ X(7, 6, 2, 1, 1, 1, 1, 1) + 19 • Σ X(7, 6, 1, 1, 1, 1, 1, 1, 1) mod 23 ΣS() = Bob-side easy tensors + 13 • Σ Ȳ(13, 7) + 20 • Σ Ȳ(13, 6, 1) + 2 • Σ Ȳ(13, 5, 2) + 22 • Σ Ȳ(13, 5, 1, 1) + 1 • Σ Ȳ(13, 4, 3) + 17 • Σ Ȳ(13, 4, 2, 1) + 3 • Σ Ȳ(13, 4, 1, 1, 1) + 19 • Σ Ȳ(13, 3, 3, 1) + 21 • Σ Ȳ(13, 3, 2, 2) + 1 • Σ Ȳ(13, 3, 2, 1, 1) + 11 • Σ Ȳ(13, 3, 1, 1, 1, 1) + 12 • Σ Ȳ(13, 2, 2, 2, 1) + 17 • Σ Ȳ(13, 2, 2, 1, 1, 1) + 3 • Σ Ȳ(13, 2, 1, 1, 1, 1, 1) + 10 • Σ Ȳ(13, 1, 1, 1, 1, 1, 1, 1)+11•Σ Ȳ(12, 8)+17•Σ Ȳ(12, 7, 1)+1•Σ Ȳ(12, 6, 2)+11•Σ Ȳ(12, 6, 1, 1)+17•Σ Ȳ(11, 9)+14•Σ Ȳ(11, 8, 1)+6•Σ Ȳ(11, 7, 2)+20•Σ Ȳ(11, 7, 1, 1)+ 7 • Σ Ȳ(11, 6, 3) + 4 • Σ Ȳ(11, 6, 2, 1) + 21 • Σ Ȳ(11, 6, 1, 1, 1) + 2 • Σ Ȳ(10, 10) + 4 • Σ Ȳ(10, 9, 1) + 15 • Σ Ȳ(10, 8, 2) + 4 • Σ Ȳ(10, 8, 1, 1) + 1 • Σ Ȳ(10, 7, 3) + 17 • Σ Ȳ(10, 7, 2, 1) + 3 • Σ Ȳ(10, 7, 1, 1, 1) + 21 • Σ Ȳ(10, 6, 4) + 8 • Σ Ȳ(10, 6, 3, 1) + 4 • Σ Ȳ(10, 6, 2, 2) + 21 • Σ Ȳ(10, 6, 2, 1, 1) + 1 • Σ Ȳ(10, 6, 1, 1, 1, 1) + 20 • Σ Ȳ(9, 9, 2) + 13 • Σ Ȳ(9, 9, 1, 1) + 4 • Σ Ȳ(9, 8, 3)+22•Σ Ȳ(9, 8, 2, 1)+12•Σ Ȳ(9, 8, 1, 1, 1)+14•Σ Ȳ(9, 7, 4)+13•Σ Ȳ(9, 7, 3, 1)+18•Σ Ȳ(9, 7, 2, 2)+14•Σ Ȳ(9, 7, 2, 1, 1)+16•Σ Ȳ(9, 7, 1, 1, 1, 1)+11•Σ Ȳ(9, 6, 5)+ 13 • Σ Ȳ(9, 6, 4, 1) + 12 • Σ Ȳ(9, 6, 3, 2) + 17 • Σ Ȳ(9, 6, 3, 1, 1) + 20 • Σ Ȳ(9, 6, 2, 2, 1) + 13 • Σ Ȳ(9, 6, 2, 1, 1, 1) + 5 • Σ Ȳ(9, 6, 1, 1, 1, 1, 1) + 19 • Σ Ȳ(8, 8, 4) + 16 • Σ Ȳ(8, 8, 3, 1) + 8 • Σ Ȳ(8, 8, 2, 2) + 19 • Σ Ȳ(8, 8, 2, 1, 1) + 2 • Σ Ȳ(8, 8, 1, 1, 1, 1) + 17 • Σ Ȳ(8, 7, 5) + 18 • Σ Ȳ(8, 7, 4, 1) + 6 • Σ Ȳ(8, 7, 3, 2) + 20 • Σ Ȳ(8, 7, 3, 1, 1) + 10 • Σ Ȳ(8, 7, 2, 2, 1) + 18 • Σ Ȳ(8, 7, 2, 1, 1, 1) + 14 • Σ Ȳ(8, 7, 1, 1, 1, 1, 1) + 18 • Σ Ȳ(8, 6, 6) + 6 • Σ Ȳ(8, 6, 5, 1) + 13 • Σ Ȳ(8, 6, 4, 2) + 5 • Σ Ȳ(8, 6, 4, 1, 1) + 1 • Σ Ȳ(8, 6, 3, 3) + 17 • Σ Ȳ(8, 6, 3, 2, 1) + 3 • Σ Ȳ(8, 6, 3, 1, 1, 1)+20•Σ Ȳ(8, 6, 2, 2, 2)+13•Σ Ȳ(8, 6, 2, 2, 1, 1)+5•Σ Ȳ(8, 6, 2, 1, 1, 1, 1)+9•Σ Ȳ(8, 6, 1, 1, 1, 1, 1, 1)+5•Σ Ȳ(7, 7, 6)+1•Σ Ȳ(7, 7, 5, 1)+6•Σ Ȳ(7, 7, 4, 2)+ 20 • Σ Ȳ(7, 7, 4, 1, 1) + 4 • Σ Ȳ(7, 7, 3, 3) + 22 • Σ Ȳ(7, 7, 3, 2, 1) + 12 • Σ Ȳ(7, 7, 3, 1, 1, 1) + 11 • Σ Ȳ(7, 7, 2, 2, 2) + 6 • Σ Ȳ(7, 7, 2, 2, 1, 1) + 20 • Σ Ȳ(7, 7, 2, 1, 1, 1, 1) + 13 • Σ Ȳ(7, 7, 1, 1, 1, 1, 1, 1)+15•Σ Ȳ(7, 6, 6, 1)+13•Σ Ȳ(7, 6, 5, 2)+5•Σ Ȳ(7, 6, 5, 1, 1)+18•Σ Ȳ(7, 6, 4, 3)+7•Σ Ȳ(7, 6, 4, 2, 1)+8•Σ Ȳ(7, 6, 4, 1, 1, 1)+20•Σ Ȳ(7, 6, 3, 3, 1)+10• Σ Ȳ(7, 6, 3, 2, 2)+18•Σ Ȳ(7, 6, 3, 2, 1, 1)+14•Σ Ȳ(7, 6, 3, 1, 1, 1, 1)+9•Σ Ȳ(7, 6, 2, 2, 2, 1)+7•Σ Ȳ(7, 6, 2, 2, 1, 1, 1)+8•Σ Ȳ(7, 6, 2, 1, 1, 1, 1, 1)+19•Σ Ȳ(7, 6, 1, 1, 1, 1, 1, 1, 1) mod 23

X(1, 1, 1, 1, 1) = R() + Alice-side easy tensors, 6 • Ȳ(4, 1) + 2 • Ȳ(3, 2) -2 • Ȳ(3, 1, 1) -Ȳ(2, 2, 1) + Ȳ(2, 1, 1, 1) -Ȳ(1, 1, 1,
We checked every rational η = d/k such that k ≤ 20, and verified that our framework does in fact yield a 2-party PSM protocol with unbalanced communication complexity O(N η ), O(N 1-η ).

Open Problems

This paper presents two frameworks: a framework of constructing k-party PSM protocols for general f :

[N ] k → {0, 1} with c.c. O k (N k-1
2 ), and a framework of constructing 2-party PSM protocols for general f : [N ] × [N ] → {0, 1} where one party sends O η (N η ) bits and the other party sends O η (N 1-η ) bits. An immediate open problem is to prove our frameworks work for all integer k and all rational η. Currently, we can only prove it works for some k and η.

For simplicity, our analysis only considers the symmetric sum of terms. The symmetric sum incurs a blow-up exponential on k. Thus the communication complexity of our k-party PSM protocols is exp(k) • N k-1 2 . While [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF] achieves communication complexity poly(k) • N k 2 . Our protocols are less efficient in the domain where log N < k. A possible approach of getting rid of the exponential dependency in k is to break the symmetry. The potential of such an approach is evidenced by the 5-party PSM protocol in Section 1.2, which is asymmetric.

There is no clear reason why our framework will not yields more efficient PSM protocols. Can our multi-party framework yield PSM protocols with communication complexity O k (N k 2 -1 ), when k is sufficiently large? Can our 2-party framework might yield PSM protocol with communication O η (N η ) for some rational η < 1 2 ? Our technique transfers such questions into some linear systems. Each question has an affirmative answer (for a given k or η) if and only if the corresponding linear system is solvable. We have modified our program to generate and solve these linear systems, but all the system we have tried are unsolvable. The failure suggests that our new upper bounds might be tight, or are tight for a natural class of PSM protocols.

The question of the communication complexity trade-off for multi-party PSM remains widely open. In our k-party PSM protocol, every party sends O k (N k-1 2 ) bits. A variant of [START_REF] Feige | A minimal model for secure computation[END_REF] provides a k-party PSM protocol where the i-th party sends Õk (N i-1 ) bits, whose geometric average is Õk (N k-1

2 ). Should a future work achieves the smooth trade-off between the two, there is little doubt that it will bring us a deep insight into PSM.

Finally, this work belongs to a not-fully-successful attempt at constructing PSM with subexponential communication complexity, which is probably the moonshot open problem in the PSM literature.

[IK97]

(Q) • F, i∈[t] R S i ⊗ j / ∈ i∈[t] S i x j = Q⊆P α(Q) • F, R(P \ Q) .
Proof of Equation (10). Let n = sum(Q). By definition, α(Q) is the number of unsorted partitions E = {S 1 , . . . , S t } of [n] such that the multiset {|S 1 |, . . . , |S t |} (i.e. the shape of E) equals Q.

To compute α(Q), we count the number of ways to arranging 1, . . . , n into a sequence.

• First, pick an unsorted partitions E of [n] s.t. the shape of E equals Q. The number of choices is α(Q).

• Then, sort the sets in the partion E = {S 1 , . . . , S t }. Sort them by their sizes, i.e.

|S 1 | ≤ |S 2 | ≤ • • • ≤ |S t |.
For any m, if several sets are of the size m, their order has to be specified, the number of such choices is (number of m's in Q)!.

• Finally, arrange the elements in each S i into a sub-sequence, the number of possible sequences is |S i |!. Concatenate these sub-sequences in order.

α(Q) • m∈Z + (number of m's in Q)! • i∈Q i! = n! B Auxiliary PSM Protocols for x 1 ⊗ . . . ⊗ x k , Y + s B.

The Multi-party Variant

In this section, we present an auxiliary PSM protocol that is used as a subroutine by our multi-party PSM in Section 3. The functionality is x 1 ⊗ . . . ⊗ x k , Y + s. It is a (k + 1)-party functionality where the i-th party has as input x i ∈ F N for i ∈ [k], and the (k + 1)-th party has as inputs Y ∈ F N ו••×N k times and s ∈ F. We will present a PSM protocol for this functionality with a communication complexity of O(poly(k) • N k ) field elements. This protocol is implicitly used in [START_REF] Beimel | The complexity of multiparty PSM protocols and related models[END_REF].

First, we consider the special case when k = 1. That is, there are only two parties. Say we call them Alice and Bob. Alice has x ∈ F N , Bob has y ∈ F N , s ∈ F. The functionality output is x, y + s. The PSM protocol works as follows:

• Random a, b ∈ F N , c ∈ F are sampled from the common random string, which is known by both Alice and Bob.

• Alice sends x := x + a, z := c -b, x to the referee.

• Bob sends ȳ := y + b, w := s -c -a, ya, b to the referee.

• The referee outputs x, ȳ + z + w.

For the case k ≥ 2, the first k parties need to jointly emulate Alice. The protocol works as follows:

• Random A, B, C ∈ F N ו••×N are sampled from the common random string. Define c ∈ F as the sum of entries in C.

• The (k + 1)-th party sends Ȳ := Y + B, z := s -c -A, Y -A, B to the referee.

• The first k parties jointly reveal X := x 1 ⊗ . . . ⊗ x k + A, w := c -B, x 1 ⊗ . . . ⊗ x k to the referee.

Since every coordinate of X can be computed by an arithmetic formula of size O(k), each of these coordinates can be computed by the referee by using a PSM protocol with communi- Due to the randomness of C, we know W is a randomized encoding of w. Thus, it is equivalent for the first k parties to jointly reveal W to the referee. Since every coordinate of W can be computed by an arithmetic formula of size O(k), each of them can be revealed by using the Ishai-Kushilevitz PSM protocol [IK00], which has a communication complexity of O(poly(k)) field elements. The referee learns w after receiving O(poly(k) • N k ) field elements.

• The referee outputs X, Ȳ + z + w.

The correctness of the protocol can be verified in the following equation:

X, Ȳ + z + w = x 1 ⊗ . . . ⊗ x k + A, Y + B + s -c -A, Y -A, B + c -B, x 1 ⊗ . . . ⊗ x k = x 1 ⊗ . . . ⊗ x k , Y + s.
The privacy is guaranteed by the following simulator:

• Simulate X, Ȳ, W as uniform random, since they are one-time-padded by A, B, C.

• Given X, Ȳ, W and the function output, w, z are uniquely determined since w = (W) and X, Ȳ + z + w = output.

• Simulate the transcripts of the inner Ishai-Kushilevitz PSM protocols using its own simulator, which takes X, W as input.

B.2 The 2-party Variant

In this section, we present an auxiliary PSM protocol that is used as a subroutine by our unbalanced 2-party PSM in Section 4. The functionality is x 1 ⊗ . . . ⊗ x k , Y + s. It is a 2-party functionality where the first party, namely Alice, has as inputs x 1 , . . . , x k ∈ F N and the second party, namely Bob, has as inputs Y ∈ F N ו••×N k times and s ∈ F. We will present a PSM protocol for this functionality with unbalanced communication complexity, where Alice sends O(kN ) field elements and Bob sends (N + 1) k field elements.

As the first step, we consider a harder problem instead. Bob's input is replaced by a multi-affine function f : F N ו • •×F N → F. Corresponding, the functionality is replaced by f (x 1 , . . . , x k ). Every multi-affine function f can be uniquely represented by its coefficient tensor F ∈ F (N +1)ו••×(N +1) such that for any z 1 , . . . ,

z k ∈ F N , f (z 1 , . . . , z k ) = z 1 1 ⊗ • • • ⊗ z k 1, F .
Here z i 1 denotes the concatenation of z i and 1, which is a dimension-(N + 1) vector. Notice that, if we let the "first" N × • • • × N subtensor of F equal Y, let its "last" entry F[N + 1, . . . , N + 1] = s, and let all other entries in F be 0, we have

f (x 1 , . . . , x k ) = x 1 1 ⊗ • • • ⊗ x k 1, F = x 1 ⊗ . . . ⊗ x k , Y + s.
The protocol works as follows:

• Random r 1 , . . . , r k ∈ F N and a random multi-affine function g are sampled from the common random string.

• Alice sends xi = x i + r i to the referee, for all i ∈ [k].

• Bob computes the multi-affine function g, such that g(z 1 , . . . , z k ) := f (z 1 -r 1 , . . . , z k -r k ).

Bob sends ḡ = g + h to the referee.

• Alice additionally sends s = h(x 1 , . . . , xk ) to the referee.

• The referee outputs ḡ(x 1 , . . . , xk ) -s.

The correctness follows directly from the following equation: The privacy is guaranteed by the following simulator:

• Simulate x1 , . . . , xk , ḡ as uniform random, since they are one-time padded by r 1 , . . . , r k , h.

• Given x1 , . . . , xk , ḡ and the function output, simulate s by computing s from the equation ḡ(x 1 , . . . , xk ) -s = output.

refereeFigure 1 :

 1 Figure 1: Illustration of a multi-party PSM protocol

  • F, X(5, 4, 3) -160 • F, X(4, 4, 4) -45 • F, X(3, 3, 3, 3) = 1155000 • F, R() + easy terms, which induces a 6-party PSM with communication complexity O(N 2.5 ). For k = 7, consider the following masked terms   F, X(4, 4, 4, 2) F, X(6, 6, 2) F, X(6, 4, 4)

4

  Unbalanced 2-party PSM Protocols The two parties in 2-party PSM are conventionally called Alice and Bob. Let x ∈ [N ] denote Alice's and y ∈ [N ] denote Bob's input. In this section, we show that every functionality f : [N ] × [N ] → {0, 1} admits a 2-party PSM protocol, where Alice sends O(N η ) bits and Bob sends O(N 1-η ) bits. Theorem 4.1. For any functionality f : [N ] × [N ] → {0, 1}, and any η = d/k such that d, k are integers and 0 < d < k ≤ 20, there is a 2-party PSM protocol for f with unbalanced communication complexity O(N η ), O(N 1-η ).

√N

  [N ] × [N ] → {0, 1} to functionality Aux 2 k,N . The reduction works as follows: Let x, y ∈ [N ] be the input of Alice and Bob respectively. Evenly divide x into x 1 , . . . , x k ∈ [ k √ N ], similarly divide y into y 1 , . . . , y k ∈ [ k √ N ]. For each j ∈ [k], let x j := e x j ∈ F √ N be the x j -th standard unit vector. Similarly let y i := e y i ∈ F k for every i ∈ [k]. The functionality f can be reduced to Aux 2 k,N by doing:

  1, 1) = 24 • S() + Bob-side easy tensors.For η = 2/5, a 2-party PSM protocol with desired c.c. is induced by 2 • X(2, 2, 1) -X(2, 1, 1, 1) = 20 • R() + Alice-side easy tensors, 3 • Ȳ(3, 2) + Ȳ(3, 1, 1) -Ȳ(2, 2, 1) -Ȳ(1, 1, 1, 1, 1) = 24 • S() + Bob-side easy tensors.

  cation complexity of O(poly(k)) field elements [IK00]. The referee learns X after receiving O(poly(k) • N k ) field elements. The term w := c-B, x 1 ⊗. . .⊗x k equals the sum of all entries in W := C-B• p.w. (x 1 ⊗. . .⊗ x k ), where • p.w. denotes the point-wise product. In other words, we defines W∈ F N ו••×N as W[i 1 , . . . , i k ] = C[i 1 , . . . , i k ] -B[i 1 , . . . , i k ]x 1 [i 1 ] . . . x k [i k ].

ḡ(x 1

 1 , . . . , xk ) -s = g(x 1 , . . . , xk ) + h(x 1 , . . . , xk ) -h(x 1 , . . . , xk ) = g(x 1 , . . . , xk ) = f (x 1 -r 1 + r 1 , . . . , x k -r k + r k ) = f (x 1 , . . . , x k ).

Table 1 :

 1 The communication complexity of computing general f : [N ] k → {0, 1} in multi-party

	PSM model
		Communication complexity	Communication complexity
		of one party	of the other party
	[FKN94]	O(log N )	N
	[BIKK14]	O(N 1/2 )	O(N 1/2 )
	This work	O(N η )	O(N 1-η )

Table 2 :

 2

The unbalanced communication complexity of general f :

[N ] × [N ] → {0, 1} in 2-party PSM model

  For any prime p and positive integer e, binomial coefficient p e +t p e -2 is a multiple of p for all 0 ≤ t ≤ p e -3, while binomial coefficient 2p e -2 p e -2 ≡ 1 mod p.

	Proof.
				p e t		=	p e t	•	p e -1 t -1	.
	Lemma 3.3. Proof. For every 0 ≤ t ≤ p e -3,
				p e + t p e -2	=	t j=0	t j		p e p e -2 -j
										multiple of p
	is a multiple of p. While
	2p e -2 p e -2	=	p e -3 j=0	p e -2 j	p e p e -2 -j	+	p e -2 p e -2	p e 0	≡ 1 mod p.
					multiple of p

easy terms mod p, which induces a k-party PSM protocol with c.c. O k (N k-1 2 ).

Lemma 3.2. any prime p and positive integer e, p e t is a multiple of p for all 0 < t < p e .

  Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. In Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, Ramat-Gan, Israel, June 17-19, 1997, Proceedings, pages 174-184. IEEE Computer Society, 1997.

	[IK00]	Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation
		with applications to round-efficient secure computation. In 41st Annual Symposium on
		Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach,
		California, USA, pages 294-304. IEEE Computer Society, 2000.
	[LVW17] Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Conditional disclosure of secrets
		via non-linear reconstruction. In CRYPTO Part I, pages 758-790, 2017.
	A Proof of Equation (9) and (10)
	Proof of Equation (9). By definition:
			F, X(P ) =
					( * )
			F,	(R S i +	x j )
			( * )	i∈[t]	j∈S i
		=		F,	R S ⊗	x j
			( * ) G⊆E	S∈G	j / ∈	S
					S∈G
		=	Q⊆P G={S 1 ,...,St} s.t. {|S 1 |,...,|St|}=P \Q x Q⊆P G={S 1 ,...,St} s.t. β(P, G) • F, i∈[t] R S i ⊗ j / ∈ i∈[t] S i α
			{|S 1 |,...,|St|}=P \Q

F, XS 1 ⊗ . . . ⊗ XSt where ( * ) denotes "for all unordered E = {S 1 , . . . , S t } being a partition of [2k] such that {|S 1 |, . . . , |S t |} = P ". Thus, F, X(P ) = j , where β(P, G) accounts for the redundancy: define β(P, G) as the number of unordered partitions E of [2k] such that G ⊆ E and P is the shape of E. It is equivalent to count the number of F := E \ G. That is, β(P, G) also equals the number of unordered partitions F of [2k] \ S∈G S such that Q is the shape of F . Thus by definition, β(P, G) = α(Q). The proof is concluded by F, X(P ) =

We implicitly exchange the order of indices in tensor product. E.g. when k = 2, the masked tensor X{1,4} ⊗ X{2,3} is defined by ( X{1,4} ⊗ X{2,3} )[j1, j2, j3, j4] = X{1,4} [j1, j4] • X{2,3} [j2, j3].

The source code can be downloaded from https://github.com/tianren/psm.

The source code can be downloaded from https://github.com/tianren/psm.

Acknowledgement

We would like to thank Hoeteck Wee, Vinod Vaikuntanathan amd Michel Abdalla for helpful discussions. TL was supported by NSF grants CNS-1528178, CNS-1929901, CNS-1936825 (CAREER), CNS-2026774, a JP Morgan AI research Award, and a Simons Foundation Collaboration Grant on Algorithmic Fairness. Part of this work was performed while TL was in MIT, during which he was supported in part by NSF Grants CNS-1350619, CNS-1414119 and CNS-1718161, an MIT-IBM grant and a DARPA Young Faculty Award. LA was supported by a doctoral grant from the French Ministère de l'Enseignement Supérieur et de la Recherche.

The Induced PSM Protocol

In order to develop the previous section smoothly, we skipped the technique details on how the condition (14) implies a 2-party PSM of the desired communication complexity. In this section, we will show how to construct such a 2-party PSM protocol assuming that the target term is spanned by referee-computable masked terms and easy pure terms.

By the condition (14), there are referee-computable masked terms Z(1) , . . . , Z(t) , easy pure terms T (1) , . . . , T (s) , and coefficients a 1 , . . . a t , b 1 , . . . , b s ∈ F such that

A 2-party PSM for f , together with its correctness and security, is yielded by the following facts:

• Fact I: s j=1 b j T (j) together with XΩ for all 0 < |Ω| ≤ d and ȲΩ for all 0 < |Ω| ≤ k -d form a randomized encoding of the functionality output.

• Fact II: There is a PSM protocol for s j=1 b j T (j) , in which Alice sends k Proof of Fact II. Sample random c 1 , . . . , c s ∈ F from the common random string such that c 1 + . . . + c s = 0. Then it's sufficient to construct a PSM protocol for computing b j T (j) + c j for each j.

Because T (j) is an easy term, we have T (j) = F, R (j) ⊗ S (j) , where R (j) is an Alice-side pure tensor, S (j) is a Bob-side pure tensor, and either R (j) is an Alice-side easy tensor, S (j) is a Bob-side easy tensor. W.l.o.g., assume R (j) is an Alice-side easy tensor.

Say this Alice-side easy pure term R

By the definition of an Alice-side easy term, w ≤ k -d. Then Bob knows a dimension-w tensor G (which is determined by S (j) , b j , R Ω 1 , R Ω 2 , . . . ) such that b j T (j) + c j = G, x i 1 ⊗ . . . ⊗ x iw + c j , which admits a PSM protocol (presented in Section B.2) in which Alice sends O(w • N 1/k ) field elements, Bob sends N w/k field elements.