Ideal Private Simultaneous Messages Schemes and Their Applications

In this work, we initiate a theory of ideal PSM schemes with a complete characterization, several positive results, and applications. As an interesting implication, our results provide a unified perspective on existing PSM constructions achieving the best known communication complexity, and moreover yield novel and more efficient constructions. First, we show a necessary and sufficient condition for functions to admit ideal PSM, using group-theoretic terminology. Specifically, we prove that such functions are essentially limited to a family of functions induced by certain permutation groups on the input domain. This characterization allows us to derive asymptotic upper bounds on the number of functions admitting ideal PSM and a complete list when the domain size $N$ is small (e.g., up to $N\le 23$ for boolean functions). We also provide several infinite families of functions of special interest that admit ideal PSM schemes, including the sum function mentioned above. As applications, we propose novel communication-efficient PSM schemes for functions with sparse/dense or low-rank truth-tables, improving upon the previous construction for functions with bounded tiling number [41]. Furthermore, we reduce the constant factor in the dominant term of the best known communication complexity for general functions [7], from $12\sqrt{N}$ to $8\sqrt{N}$. Below, we elaborate on our results.

We provide a brief history of the problem of determining the optimal communication complexity of PSM schemes. Feige et al. [29] formalized the notion of PSM schemes and presented the feasibility result of two-party PSM for general functions. Ishai and Kushilevitz [33] extended this to the multi-party setting and showed a $k$-party PSM scheme for functions represented by branching programs. These constructions, along with several variants including PSM for arithmetic formulas, are summarized in [34]. Subsequently, Beimel et al. [7] successfully devised a two-party PSM scheme for general functions $f:X\times X\to \{0,1\}$ with communication complexity $O(\sqrt{|X|})$. This result was later generalized and improved by [9, 3], leading to $k$-party PSM schemes with communication complexity $O({|X|}^{(k-1)/2})$, omitting factors that depend only on $k$. Another direction aims at obtaining more communication-efficient PSM schemes for functions of special interest. For example, a series of works [6, 13, 24, 46, 25] presented several “tailor-made” constructions for symmetric functions, whose outputs are independent of the order of inputs. PSM schemes have been used to obtain many other cryptographic primitives, e.g., secure computation with general interaction patterns [32], constant-round secure computation [36, 35], and conditional disclosure of secrets [38, 39]. The model of PSM schemes has also been generalized into different scenarios such as ad-hoc PSM [5, 8] where only a subset of the parties actually send messages, and robust PSM (also known as non-interactive secure computation) [6, 13] where an external party may corrupt some parties.

There are known lower bounds on the communication complexity of PSM. Applebaum et al. [2] proved a lower bound of $3\log N-O(\log \log N)$ for the two-party case, and Ball and Randolph [4] showed a lower bound that is roughly $k^2\log N$ for $k$-party PSM when $k=\omega (\log \log N)$. Tighter upper and lower bounds are known for concrete functions with small input domains and/or a small number of parties, including the $n$-bit AND function [29, 23, 47], the multi-input equality function [47], and the majority function [47].

A secret sharing scheme [45, 14] is a cryptographic primitive, which divides a secret $x$ into $k$ shares in such a way that $x$ can be recovered from any authorized set of shares while no information on $x$ is revealed from any unauthorized set of shares. The collection of all authorized sets, namely sets of shares that can recover a secret, is called its access structure. A secret sharing scheme is called ideal if each share is taken from the same domain as secrets [15]. Since the size of each share cannot be smaller than the secret size [37], ideal secret sharing schemes necessarily achieve the optimal share size. A series of works have shown that several classes of access structures admit ideal secret sharing schemes [42, 48, 11, 27, 28, 26, 18], and found interesting connections to combinatorics and information theory [10, 16, 40]. Despite all these progresses, the exact characterization of access structures admitting ideal secret sharing schemes is a longstanding open problem.

In a (two-party) PSM scheme, each of two parties has common randomness $r\in R$ and an input $x_i\in X_i$. Then, each party sends a single message $m_i\in M_i$ to an external party, from which he learns $f(x_0,x_1)$ for a public function $f:X_0\times X_1\to Y$. The PSM scheme specifies a randomized algorithm $\mathrm{𝖦𝖾𝗇}$ to sample $r$, message functions ${\mathrm{𝖬𝗌𝗀}}_i:X_i\times R_i\to M_i$ that computes $m_i$ from $(x_i,r)$, and an evaluation function $\mathrm{𝖤𝗏𝖺𝗅}:M_0\times M_1\to Y$ that outputs $f(x_0,x_1)$ from $(m_0,m_1)$. The privacy requirement is that the distribution of messages does not leak any information on the inputs other than $f(x_0,x_1)$. We say that the PSM scheme is ideal if parties’ messages are taken from the same domain as inputs, i.e., $M_i=X_i$. A function $f$ is called an ideal PSM function if there exists an ideal PSM scheme for $f$. The communication complexity of ideal PSM schemes cannot be reduced further if $f$ is non-degenerate, by which we mean that its truth-table has no identical rows or columns. Throughout the paper, we only consider non-degenerate functions as the computation of degenerate functions is reduced to the computation of a smaller non-degenerate function.

We introduce a special class of ideal PSM schemes. As will be shown later, these schemes are canonical in the sense that every function admitting ideal PSM can be realized by some ideal PSM scheme in this class. Each of them is parameterized by a tuple $𝒢=(G_0,G_1,\psi )$, where $G_i$ is a subgroup of the group ${𝒮}_{X_i}$ of all permutations over $X_i$, and $\psi$ is an isomorphism from $G_0$ to $G_1$, that is, $\psi$ maps a permutation belonging to $G_0$ to another permutation belonging to $G_1$. We define a group ${\mathrm{\Gamma }}_{𝒢}$ as ${\mathrm{\Gamma }}_{𝒢}=\{({\pi }_0,{\pi }_1)\in G_0\times G_1:{\pi }_1=\psi ({\pi }_0)\}.$ Then, ${\mathrm{\Gamma }}_{𝒢}$ naturally acts on $X_0\times X_1$ as it is a subgroup of ${𝒮}_{X_0}\times {𝒮}_{X_1}$, and thus specifies the set of orbits, $Y_{𝒢}=\{{\mathrm{Orb}}_{{\mathrm{\Gamma }}_{𝒢}}(x_0,x_1):(x_0,x_1)\in X_0\times X_1\}$, where ${\mathrm{Orb}}_{{\mathrm{\Gamma }}_{𝒢}}(x_0,x_1)=\{({\pi }_0(x_0),{\pi }_1(x_1)):({\pi }_0,{\pi }_1)\in {\mathrm{\Gamma }}_{𝒢}\}$. We define $f_{𝒢}:X_0\times X_1\to Y_{𝒢}$ as a function that maps each input to its orbit, namely

We can construct an ideal PSM scheme ${\mathrm{\Pi }}_{𝒢}$ for $f_{𝒢}$ as follows:

• $\mathrm{■}$

  $\mathrm{𝖦𝖾𝗇}$ samples a permutation $\pi =({\pi }_0,{\pi }_1)$ chosen from ${\mathrm{\Gamma }}_{𝒢}$ uniformly at random.

• $\mathrm{■}$

  ${\mathrm{𝖬𝗌𝗀}}_i$ applies the permutation $\pi$ to an input $x_i$, namely ${\mathrm{𝖬𝗌𝗀}}_i(x_i,\pi )={\pi }_i(x_i)$.

• $\mathrm{■}$

  $\mathrm{𝖤𝗏𝖺𝗅}$ outputs the orbit of messages $(m_0,m_1)$, namely $\mathrm{𝖤𝗏𝖺𝗅}(m_0,m_1)={\mathrm{Orb}}_{{\mathrm{\Gamma }}_{𝒢}}(m_0,m_1)$.

Since an orbit of $(x_0,x_1)$ is invariant under a permutation $\pi \in {\mathrm{\Gamma }}_{𝒢}$, ${\mathrm{\Pi }}_{𝒢}$ correctly computes $f_{𝒢}$. Furthermore, if $f_{𝒢}(x_0,x_1)=f_{𝒢}(x_0^{\prime },x_1^{\prime })$, then $(x_0,x_1)$ and $(x_0^{\prime },x_1^{\prime })$ are mapped to each other by some permutation $\pi \in {\mathrm{\Gamma }}_{𝒢}$ as their orbits are identical, implying the privacy of ${\mathrm{\Pi }}_{𝒢}$.

We show that every ideal PSM function $f:X_0\times X_1\to Y$ is equivalent (that is, identical up to permutations of inputs and outputs) to $f_{𝒢}$ for some $𝒢$. We obtain this characterization by proving that the following conditions are equivalent:

1. 1.

   $f$ is an ideal PSM function.

2. 2.

   For any two inputs $(x_0,x_1),(x_0^{\prime },x_1^{\prime })$ such that $f(x_0,x_1)=f(x_0^{\prime },x_1^{\prime })$, there exists a pair of permutations $\pi =({\pi }_0,{\pi }_1)\in {𝒮}_{X_0}\times {𝒮}_{X_1}$ such that

   • $\mathrm{■}$

     $\pi (x_0,x_1)=({\pi }_0(x_0),{\pi }_1(x_1))=(x_0^{\prime },x_1^{\prime })$.

   • $\mathrm{■}$

     $\pi \in I_f$, i.e., the values of $f$ are invariant under $\pi$.

3. 3.

   $f$ is equivalent to $f_{𝒢}$ for some $𝒢$.

We have already seen the implication 3 $\Rightarrow$ 1.

To prove the implication 1 $\Rightarrow$ 2, we observe that since $M_i=X_i$ in an ideal PSM scheme, the message function ${\mathrm{𝖬𝗌𝗀}}_i(\cdot ,r)$ induces a permutation ${\pi }_r^i$ over $X_i$ for a random string $r\in R$. We construct $S$ as a group generated by all such permutations $({\pi }_r^0,{\pi }_r^1)$’s. We also observe that an ideal PSM scheme for $f$ can be transformed into an ideal PSM scheme whose evaluation function is identical to $f$, namely $\mathrm{𝖤𝗏𝖺𝗅}(m_0,m_1)=f(m_0,m_1)$. Then, the correctness property ensures that any permutation in $S$ preserves the outputs of $f$ since $f({\pi }_r^0(x_0),{\pi }_r^1(x_1))=\mathrm{𝖤𝗏𝖺𝗅}({\mathrm{𝖬𝗌𝗀}}_0(x_0,r),{\mathrm{𝖬𝗌𝗀}}_1(x_1,r))=f(x_0,x_1)$. Furthermore, the privacy property ensures that if $f(x_0,x_1)=f(x_0^{\prime },x_1^{\prime })$, then there exist random strings $r,r^{\prime }\in R$ such that $({\mathrm{𝖬𝗌𝗀}}_0(x_0,r),{\mathrm{𝖬𝗌𝗀}}_1(x_1,r))=({\mathrm{𝖬𝗌𝗀}}_0(x_0^{\prime },r^{\prime }),{\mathrm{𝖬𝗌𝗀}}_1(x_1^{\prime },r^{\prime }))$. This implies that there exists a permutation $\pi \in S$ that maps $(x_0,x_1)$ to $(x_0^{\prime },x_1^{\prime })$.

To prove the implication 2 $\Rightarrow$ 3, we show a one-to-one correspondence between the set of orbits under the action of $I_f$ and the range of $f$, that is,

Indeed, if ${\mathrm{Orb}}_{I_f}(x_0,x_1)={\mathrm{Orb}}_{I_f}(x_0^{\prime },x_1^{\prime })$, then the values of $f$ on them are identical since $f$ is invariant under any permutation in $I_f$. Conversely, if $f(x_0,x_1)=f(x_0^{\prime },x_1^{\prime })$, then there exists a permutation $\pi \in I_f$ that maps $(x_0,x_1)$ to $(x_0^{\prime },x_1^{\prime })$, and hence their orbits are identical. Furthermore, we can construct a tuple $𝒢=(G_0,G_1,\psi )$ such that ${\mathrm{\Gamma }}_{𝒢}=I_f$. Indeed, if $f$ is non-degenerate, then any permutation ${\pi }_0$ appearing in the first component of $I_f$ uniquely determines its counterpart ${\pi }_1$ such that $({\pi }_0,{\pi }_1)\in I_f$. In particular, $I_f$, ${\mathrm{𝗉𝗋}}_0(I_f)$, and ${\mathrm{𝗉𝗋}}_1(I_f)$ are isomorphic to each other, where ${\mathrm{𝗉𝗋}}_i:{𝒮}_{X_0}\times {𝒮}_{X_1}\to {𝒮}_{X_i}$ is a projection map. We set $G_0={\mathrm{𝗉𝗋}}_0(I_f)$, $G_1={\mathrm{𝗉𝗋}}_1(I_f)$, and $\psi ={\mathrm{𝗉𝗋}}_1\circ {\mathrm{𝗉𝗋}}_0^{-1}$. Note that $G_i$ forms a group as ${\mathrm{𝗉𝗋}}_i$ is a homomorphism. Then, we have $I_f={\mathrm{\Gamma }}_{𝒢}$ where $𝒢=(G_0,G_1,\psi )$. Therefore, we obtain that $f_{𝒢}(x_0,x_1)={\mathrm{Orb}}_{I_f}(x_0,x_1)$ and hence $f_{𝒢}$ is equivalent to $f$.

As a demonstration, we consider the sum function $f(x_0,x_1)=x_0+x_1$ over an abelian group $X$. For $r\in X$, let ${\sigma }_r:X\to X$ denote a permutation that shifts each element $x\in X$ by $r$. It is easy to verify that if $f(x_0^{\prime },x_1^{\prime })=f(x_0,x_1)$, then $(x_0^{\prime },x_1^{\prime })=({\sigma }_r(x_0),{\sigma }_{-r}(x_1))$ and $({\sigma }_r,{\sigma }_{-r})\in I_f$, where $r:=x_0^{\prime }-x_0$. Thus, our characterization ensures that $f$ is an ideal PSM function. Note that $f$ is equivalent to $f_{𝒢}=f_{(G_0,G_1,\psi )}$ where both $G_0$ and $G_1$ are the set consisting of all ${\sigma }_r$’s, and $\psi :G_0\to G_1$ is defined as $\psi ({\sigma }_r)={\sigma }_{-r}$. Interestingly, this argument does not require presenting any explicit PSM protocol for $f$.

The above characterization reduces the enumeration of ideal PSM functions $f:X_0\times X_1\to Y$ to the enumeration of all tuples $𝒢$’s. For ease of exposition, we assume that $|X_0|=|X_1|=:N$. See Section 5 for a general case.

First, we provide asymptotic upper bounds on the total number of such functions. Here, we focus on connected functions, that is, there exists no partition of $X_0\times X_1$ into rectangles each of which corresponds to disjoint sets of values of $f$. In the boolean case $Y=\{0,1\}$, this assumption excludes only a few trivial functions and does not affect the asymptotic results. Thanks to our characterization, we can obtain an upper bound by counting the number of all $𝒢=(G_0,G_1,\psi )$, where $G_i$ is a subgroup of ${𝒮}_{X_i}$ and $\psi$ is an isomorphism between $G_0$ and $G_1$. However, since the total number of subgroups of ${𝒮}_N$ is $2^{\mathrm{\Theta }(N^2)}$ [43], naively enumerating all subgroups cannot provide a non-trivial upper bound beyond the trivial bound of $2^{N^2}$, which is the number of all functions with domain $X_0\times X_1$. To remove duplicate counts of $𝒢$’s that correspond to equivalent functions, we first observe that if $𝒢$ and ${𝒢}^{\prime }$ are conjugate, then the corresponding functions $f_{𝒢}$ and $f_{{𝒢}^{\prime }}$ are equivalent. Hence, it suffices to enumerate only conjugacy classes. As a more effective technique, we consider a minimal subgroup $H_{𝒢}$ of ${\mathrm{\Gamma }}_{𝒢}$ that induces the same set of orbits as ${\mathrm{\Gamma }}_{𝒢}$. Then, $H_{𝒢}$ uniquely determines $f_{𝒢}$, that is, $f_{𝒢}$ and $f_{{𝒢}^{\prime }}$ are equivalent if $H_{𝒢}=H_{{𝒢}^{\prime }}$. It thus suffices to bound the number of all such subgroups $H_{𝒢}$’s. A key observation is that $H_{𝒢}$ belongs to a special class of permutation groups called orbit-minimal groups. It is shown in [43] that any orbit-minimal group over a set $X$ is generated by only $\log |X|$ permutations. As a result, any $H_{𝒢}$ is generated by at most $\log |X_0\times X_1|=\log (N^2)$ pairs of permutations in ${𝒮}_{X_0}\times {𝒮}_{X_1}$. We thus obtain a non-trivial upper bound on the number of ideal PSM functions as

Furthermore, we obtain a tighter upper bound in the special case where both $|X_0|$ and $|X_1|$ are primes. We observe that it suffices to enumerate $𝒢=(G_0,G_1,\psi )$ such that $G_0$ and $G_1$ are transitive groups, when connected functions are considered. For a prime $N$, the total number of transitive subgroups of ${𝒮}_N$ is at most $2^{O(\log N)}$ [44]. Moreover, we show that the possible types of transitive groups relevant to our setting are limited, and in particular, their sizes are upper bounded by $2^{O({\log }^{2}N)}$. Consequently, in this special case, we obtain the following bound:

Next, we provide a complete list of ideal PSM functions $f:X_0\times X_1\to Y$ for small domains. We use an open software package called GAP to enumerate all the conjugacy classes of $𝒢$. For a general range $Y$, we obtain a complete list up to $\max \{|X_0|,|X_1|\}\le 15$ except for the case of $|X_0|=|X_1|=12$. In the boolean case $Y=\{0,1\}$, we devise a more computationally efficient method to enumerate $𝒢$. As a result, we obtain a list of boolean functions admitting ideal PSM up to $\max \{|X_0|,|X_1|\}\le 23$. Specifically, if $f$ is an ideal PSM function, i.e., $f=f_{𝒢}$ for some $𝒢=(G_0,G_1,\psi )$, then the truth-table $T_f$, viewed as a $|X_0|$-by-$|X_1|$ matrix, satisfies the following property: If $v\in {\{0,1\}}^{|X_1|}$ is a column of $T_f$, then so is a permuted vector ${\pi }_0(v)$ for any ${\pi }_0\in G_0$. Conversely, for any pair of columns $v,v^{\prime }$ of $T_f$, there exists a permutation ${\pi }_0\in G_0$ such that $v^{\prime }={\pi }_0(v)$. Leveraging this property, we can enumerate ideal PSM functions as follows: For each transitive group $G_0$, we construct a graph ${𝔊}_{G_0}=(V_{G_0},E_{G_0})$ where $V_{G_0}={\{0,1\}}^n$ and $E_{G_0}=\{(v,v^{\prime })\in V_{G_0}\times V_{G_0}:\exists {\pi }_0\in G_0,v^{\prime }={\pi }_0(v)\}.$ From the above property, the truth-table of any $f_{𝒢}$ with $𝒢=(G_0,G_1,\psi )$ corresponds to some connected component of ${𝔊}_{G_0}$. We then collect the connected components of ${𝔊}_{G_0}$ for all $G_0$’s, which contain all desired functions.

We present several infinite families of ideal PSM functions. The simplest family is the group product, which computes

where each $x_i$ and $y_i$ are taken from a possibly non-abelian group $G$ and we set $z_i=x_i$ for $i\in S_0$ and $z_i=y_i$ for $i\in S_1$. Feige et al. [29] constructed an ideal PSM scheme for this function by randomizing a sequence of group elements while preserving their product.

Next, we show that a function computing private set intersection cardinality admits ideal PSM. Specifically, for parameters $n,d_0,d_1\in \mathbb{N}$, we define

where $A_i$ is taken from the set of all $d_i$-sized subsets of a common set $U$ of $n$ elements. To see that ${\mathrm{𝖯𝖲𝖨𝖢}}_{n,(d_0,d_1)}$ is an ideal PSM function, suppose that $|A_0\cap A_1|=|A_0^{\prime }\cap A_1^{\prime }|$ and let $B=A_0\cap A_1$ and $B^{\prime }=A_0^{\prime }\cap A_1^{\prime }$. Then, we can choose a permutation $\pi$ on $U$ such that $\pi (A_0)=A_0^{\prime }$ and $\pi (A_1)=A_1^{\prime }$, and apply our characterization result. The existence of such $\pi$ is guaranteed by the fact that both $A_0\cup A_1$ and $A_0^{\prime }\cup A_1^{\prime }$ admit partitions whose corresponding blocks have the same sizes, that is, $|A_0\setminus B|=|A_0^{\prime }\setminus B^{\prime }|$, $|A_1\setminus B|=|A_1^{\prime }\setminus B^{\prime }|$, and $|B|=|B^{\prime }|$. In particular, ${\mathrm{𝖯𝖲𝖨𝖢}}_{n,(1,1)}$ is equivalent to the functionality of testing whether two given elements are identical, which implies that the equality function is an ideal PSM function.

Finally, we introduce a class of functions that generalizes the index function [29, 38]. Let $H$ and $G$ be abelian groups and let $ℱ$ be any set of families $\varphi :H\to G$ that are closed under sums (that is, $\varphi \pm {\varphi }^{\prime }\in ℱ$ for any $\varphi ,{\varphi }^{\prime }\in ℱ$) and are closed under input shifts (that is, ${\varphi }_s\in ℱ$ for any $\varphi \in ℱ,s\in H$, where ${\varphi }_s(x):=\varphi (x-s)$). We set $X_0=H\times G$ and $X_1=ℱ$, and define a function $f:(H\times G)\times ℱ\to G$ as

This class of functions includes the original index function considered in [29], an augmented form of the inner product, and multi-linear polynomials as special instances. To show that these functions admit ideal PSM, we define two families of permutations over $X_0\times X_1$:

• $\mathrm{■}$

  ${\pi }^s:((x,r),\varphi )\mapsto ((x+s,r),{\varphi }_s)$ for any $s\in H$.

• $\mathrm{■}$

  ${\sigma }^{\tau }:((x,r),\varphi )\mapsto ((x,r+\tau (x)),\varphi +\tau )$ for any $\tau \in ℱ$.

Intuitively, the first family of permutations allows us to freely move Alice’s input $(x,r)$ to any $(x^{\prime },r)$ while preserving the outputs of $f$. The second family allows us to freely move Bob’s input $\varphi$ to any ${\varphi }^{\prime }$. Thus, for any pair of inputs $(x_0,x_1),(x_0^{\prime },x_1^{\prime })$ with $f(x_0,x_1)=f(x_0^{\prime },x_1^{\prime })$, we can find a permutation that maps $(x_0,x_1)$ to $(x_0^{\prime },x_1^{\prime })$ preserving the outputs of $f$ and apply our characterization result.

In general, if we obtain a PSM scheme for a function $F:X_0^{\prime }\times X_1^{\prime }\to Y$, then the scheme naturally induces a PSM scheme for any function $f:X_0\times X_1\to Y$ that can be embedded into $F$, simply by restricting the input domains. Here, by saying that $f$ is embedded into $F$, we mean that there are injections ${\tau }_i:X_i\to X_i^{\prime }$ such that $f(x_0,x_1)=F({\tau }_0(x_0),{\tau }_1(x_1))$ for all $(x_0,x_1)\in X_0\times X_1$. Thus, the ideal PSM schemes described above particularly induce PSM schemes for functions that are embedded into the corresponding functions. We refer to such a construction template of PSM as the “embedding-to-ideal-PSM” construction. Interestingly, most of the existing PSM schemes achieving the state-of-the-art communication complexity in various computation models follow the embedding-to-ideal-PSM template. For example, the best known schemes for branching programs [29] and arithmetic formulas [34, 19] are obtained from the ideal PSM scheme for the group product. The nearly optimal scheme for polynomials [38] is obtained from the ideal PSM scheme for a generalized index function, where $ℱ$ is the set of all multi-linear polynomials.

By embedding target functions to ideal PSM functions, we obtain novel communication-efficient PSM schemes for functions with sparse/dense or low-rank truth-tables. First, we consider a function $f:X_0\times X_1\to \{0,1\}$ whose truth-table $T_f$, viewed as a $|X_0|$-by-$|X_1|$ matrix, contains at most $d$ ones in each row for a small $d\ll N_1:=|X_1|$. By appending each row with an appropriate number of ones, we can embed $f$ into a function $f^{\prime }:X_0\times X_1^{\prime }\to \{0,1\}$ whose truth-table contains exactly $d$ ones in each row, where $N_1^{\prime }:=|X_1^{\prime }|=N_1+d$. Note that the truth-table of ${\mathrm{𝖯𝖲𝖨𝖢}}_{N_1^{\prime },(d,1)}$ is a $\left(\genfrac{}{}{0pt}{}{N_1^{\prime }}{d}\right)$-by-$N_1^{\prime }$ matrix, which consists of all row vectors of weight $d$. We can then embed $f^{\prime }$ (and hence $f$) into ${\mathrm{𝖯𝖲𝖨𝖢}}_{N_1^{\prime },(d,1)}$. The ideal PSM scheme for ${\mathrm{𝖯𝖲𝖨𝖢}}_{N_1^{\prime },(d,1)}$ induces a PSM scheme for $f$ with communication complexity $O(\log \left(\genfrac{}{}{0pt}{}{N_1^{\prime }}{d}\right))=O(d\log (N_1+d))$. Prior to this work, the only general construction in [7] can apply in this setting which results in communication complexity of $O(\sqrt{N_1})$. Thus, our construction achieves a strict improvement when $d=o(\sqrt{N_1}/\log N_1)$. Note that these schemes also apply to functions such that the rows (or the columns) are dense, that is, they contain at least $n-d$ ones for a small $d$.

Next, Narayanan et al. [41] showed a PSM scheme for a function $f:X_0\times X_1\to Y$ whose communication complexity is $O(k\log |Y|)$, where $k$ is the tiling number of $f$. Here, the tiling number refers to the smallest number of disjoint monochromatic rectangles covering the truth-table $T_f$. Let $q$ be the smallest prime power larger than $|Y|$ (we can choose $q$ so that $q=O(|Y|)$). If the rank of the truth-table $T_f$ is at most $r$ over ${𝔽}_q$, then we can decompose $T_f={𝐌}_0{𝐌}_1^{\top }$ where ${𝐌}_i\in {𝔽}_q^{|X_i|\times r}$. Thus, by defining an injection

where ${𝐌}_i[x]$ denotes the $x$-th row of ${𝐌}_i$, we can embed $f$ into the inner product function over ${𝔽}_q^r$. The inner product is a special case of the generalized index function and hence admits ideal PSM. As a result, we obtain a PSM scheme for $f$ with communication complexity $O(r\log |Y|)$. Since it holds that $k\ge r$ for any $f$, our construction achieves a more refined communication complexity than [41].

Finally, Beimel et al. [7] showed a PSM scheme for a general function $f:X\times X\to \{0,1\}$ with communication complexity $O(\sqrt{N})$, where $X=\{0,1,\mathrm{\dots },N-1\}$. According to the description in [3], the more precise communication complexity is at least $12\sqrt{N}$. In contrast, we show that any function $f$ can be embedded into an ideal PSM function $G_f:X^{\prime }\times X^{\prime }\to \{0,1\}$ with $\log |X^{\prime }|=4\sqrt{N}+1$. Precisely, we consider a multi-linear function $\widehat{f}:{({\{0,1\}}^{\sqrt{N}})}^4\to \{0,1\}$ such that

for any $i_0,j_0,i_1,j_1\in \{0,1,\mathrm{\dots },\sqrt{N}-1\}$, where ${𝐞}_i$ denotes a one-hot vector whose $i$-th element is one. Then, we set $X^{\prime }={({\{0,1\}}^{\sqrt{N}})}^4\times \{0,1\}$ and define a function $G_f:X^{\prime }\times X^{\prime }\to \{0,1\}$ as

for any ${𝐱}_0,{𝐱}_1,{𝐢}_0,{𝐢}_1,{𝐲}_0,{𝐲}_1,{𝐣}_0,{𝐣}_1\in {\{0,1\}}^{\sqrt{N}}$ and $a,b\in \{0,1\}$. To show that $G_f$ admits ideal PSM, we construct the following families of permutations over $X^{\prime }\times X^{\prime }$ under which the outputs of $G_f$ are invariant:

• $\mathrm{■}$

  For any ${𝐭}_0,{𝐭}_1\in {\{0,1\}}^{\sqrt{N}}$, ${\pi }^{{𝐭}_0,{𝐭}_1}$ freely shifts part of Alice’s input $({𝐱}_0,{𝐱}_1)$ by $({𝐭}_0,{𝐭}_1)$.

• $\mathrm{■}$

  For any ${𝐬}_0,{𝐬}_1\in {\{0,1\}}^{\sqrt{N}}$, ${\sigma }^{{𝐬}_0,{𝐬}_1}$ freely shifts part of Bob’s input $({𝐲}_0,{𝐲}_1)$ by $({𝐬}_0,{𝐬}_1)$.

• $\mathrm{■}$

  For any ${𝐩}_0,{𝐩}_1,{𝐪}_0,{𝐪}_1\in {\{0,1\}}^{\sqrt{N}}$, ${\tau }^{{𝐩}_0,{𝐩}_1,{𝐪}_0,{𝐪}_1}$ freely shifts part of Alice’s and Bob’s inputs, $({𝐢}_0,{𝐢}_1)$ and $({𝐣}_0,{𝐣}_1)$, by $({𝐩}_0,{𝐩}_1)$ and $({𝐪}_0,{𝐪}_1)$, respectively.

• $\mathrm{■}$

  For any $r\in \{0,1\}$, ${\rho }^r$ maps part of Alice’s and Bob’s inputs $(a,b)$ to $(a\oplus r,b\oplus r)$.

Thus, we can map an input to any other input by composing permutations from the above families as long as their corresponding outputs of $G_f$ are equal, which shows the existence of ideal PSM for $G_f$. Since the communication complexity of the resulting ideal PSM scheme is $\log |X^{\prime }\times X^{\prime }|=8\sqrt{N}+2$, our construction improves the constant factor in the dominant term of the best known communication complexity. An additional benefit is that Alice and Bob can compute their messages simply by applying a composition of the permutations defined above to their inputs. As a result, the message functions of our scheme can be expressed in closed form and simplifies the hierarchical design of [7, 3], which relies on nested invocations of PSM schemes for smaller functions.

If $H$ is a subgroup of a group $G$, then we write $H\le G$. We denote the group of all permutations over a finite set $X$ by ${𝒮}_X$. If $|X|=N$, then we also denote it by ${𝒮}_N$ and call it the permutation group of degree $N$. We denote the inverse of a permutation $\pi$ by ${\pi }^{-1}$ and the composition of $\pi$ and ${\pi }^{\prime }$ by ${\pi }^{\prime }\circ \pi$. We say that $G$ is generated by a subset $S\subseteq G$ if every element of $G$ can be expressed by a composition of finitely many elements of $S$ or their inverses. Each permutation $\pi \in {𝒮}_X$ naturally acts on the set $X$. If $n=|X|$, then $\pi$ also acts on the set $Y^n$ of $n$-dimensional vectors over a set $Y$: for each $v={(v_x)}_{x\in X}\in Y^n$, define $\pi (v)={(v_x^{\prime })}_{x\in X}\in Y^n$ as $v_{\pi (x)}^{\prime }=v_x$ for all $x\in X$. For a subset $S\subseteq {𝒮}_X$, we define the orbit of $x\in X$ under the action of $S$ on $X$ by ${\mathrm{Orb}}_S(x)=\{\pi (x):\pi \in S\}.$ We say that $G\le {𝒮}_X$ is transitive if for any $x,x^{\prime }\in X$, there exists $\pi \in G$ such that $\pi (x)=x^{\prime }$, that is, the orbit of any $x\in X$ is equal to $X$. A (not necessarily transitive) subgroup $G\le {𝒮}_X$ is called orbit-minimal if for any proper subgroup $H⪇G$, it holds that $|\{{\mathrm{Orb}}_H(x):x\in X\}|>|\{{\mathrm{Orb}}_G(x):x\in X\}|$. Let $X_0,X_1$ be sets. We naturally identify ${𝒮}_{X_0}\times {𝒮}_{X_1}$ as a subgroup of ${𝒮}_{X_0\times X_1}$ via $\tau (x_0,x_1)=({\tau }_0(x_0),{\tau }_1(x_1))$ where $\tau =({\tau }_0,{\tau }_1)\in {𝒮}_{X_0}\times {𝒮}_{X_1}$ and $(x_0,x_1)\in X_0\times X_1$. We denote a natural projection from ${𝒮}_{X_0}\times {𝒮}_{X_1}$ onto ${𝒮}_{X_i}$ by ${\mathrm{𝗉𝗋}}_i$. For $S\subseteq {𝒮}_{X_0}\times {𝒮}_{X_1}$, we similarly define the orbit of $(x_0,x_1)$ under the action of $S$ on $X_0\times X_1$, denoted by ${\mathrm{Orb}}_S(x_0,x_1)$.

Let $f:X_0\times X_1\to Y$ be a function. For subsets $A_0\subseteq X_0$ and $A_1\subseteq X_1$, we denote $f(A_0\times A_1)=\{f(x_0,x_1):(x_0,x_1)\in A_0\times A_1\}$ and denote $\mathrm{Range}(f)=f(X_0\times X_1)$. We also denote $f^{-1}(y)=\{(x_0,x_1)\in X_0\times X_1:f(x_0,x_1)=y\}$ for $y\in \mathrm{Range}(f)$. We define an equivalence relation $\simeq$ on the set of all functions whose domain is $X_0\times X_1$ as follows:

for some pair of permutations $({\tau }_0,{\tau }_1)\in {𝒮}_{X_0}\times {𝒮}_{X_1}$ and some bijection $\sigma :\mathrm{Range}(f)\to \mathrm{Range}(g)$. The truth-table of $f:X_0\times X_1\to Y$ is defined as a matrix $T_f$ whose rows and columns are indexed by $X_0$ and $X_1$ and whose $(x_0,x_1)$-th entry $T_f[x_0,x_1]$ is $f(x_0,x_1)$ for any $(x_0,x_1)\in X_0\times X_1$. For each $x_0\in X_0$, we denote the row vector of $T_f$ corresponding to $x_0$ by $T_f[x_0,\ast ]\in Y^{|X_1|}$. Similarly, we denote the column vector of $T_f$ corresponding to $x_1\in X_1$ by $T_f[\ast ,x_1]\in Y^{|X_0|}$. We say that a function $f:X_0\times X_1\to Y$ is degenerate if there exist $i\in \{0,1\}$ and $x_i\ne x_i^{\prime }\in X_i$ such that $f(x_i,x_{1-i})=f(x_i^{\prime },x_{1-i})$ for all $x_{1-i}\in X_{1-i}$, where the inputs are supposed to be sorted according to the index. We say that $f$ is non-degenerate if $f$ is not degenerate. We say that $f:X_0\times X_1\to Y$ is disconnected if there exist $i\in \{0,1\}$ and a partition $X_i=A_i\cup B_i$ such that $f(A_i\times X_{1-i})\cap f(B_i\times X_{1-i})=\mathrm{\varnothing }$. We say that $f$ is connected if $f$ is not disconnected. Note that if $Y=\{0,1\}$, then non-degenerate disconnected functions are limited to those whose truth tables are $(\mathrm{1\; 0})$ or its transpose, or functions that are equivalent to them. For $\pi =({\pi }_0,{\pi }_1)\in {𝒮}_{X_0}\times {𝒮}_{X_1}$ and $x=(x_0,x_1)\in X_0\times X_1$, we simply write $\pi (x)=({\pi }_0(x_0),{\pi }_1(x_1))$ and $f(\pi (x))=f({\pi }_0(x_0),{\pi }_1(x_1))$. We define the invariant group of $f$, denoted by $I_f$, as the subgroup consisting of all pairs of permutations in ${𝒮}_{X_0}\times {𝒮}_{X_1}$ under which the outputs of $f$ are invariant, i.e., $I_f=\{\pi \in {𝒮}_{X_0}\times {𝒮}_{X_1}:f(\pi (x))=f(x),\forall x\in X_0\times X_1\}.$

We introduce Private Simultaneous Messages (PSM) schemes. Each of two parties holds an input $x_i$ and they both share a common string $r$ sampled by a randomized algorithm $\mathrm{𝖦𝖾𝗇}$. Then, each party runs an algorithm $\mathrm{𝖬𝗌𝗀}$ to compute a message $m_i$. They send the messages to an external party, who then runs an algorithm $\mathrm{𝖤𝗏𝖺𝗅}$ to obtain $f(x_0,x_1)$. The privacy requirement is that the joint distribution of messages leaks no extra information. We provide the formal definition below.