Private simultaneous message passing

Private simultaneous message passing (PSM) is a primitive, studied in information-theoretic cryptography, which allows multiple, non-communicating, parties to reveal the output of a function to a referee without revealing the inputs to the function. PSM was introduced as a simple toy model for secure multi-party computation, and is related to the conditional disclosure of secrets setting, among other subjects.

Definition

The private simultaneous message (PSM) setting involves three players; Alice, Bob and the referee. Alice receives an input $x\in \{0,1{\}}^n$, and Bob receives a string $y\in \{0,1{\}}^n$. A choice of Boolean function $f:\{0,1{\}}^{2n}\to \{0,1\}$ is fixed in advance and known to all players. Alice and Bob cannot communicate with one another, but share a string of random bits which we label $r$. Alice and Bob compute messages $m_A=m_A(x,z,r)$ and $m_B=m_B(y,r)$, which they send to the referee. A PSM protocol consists of the encoding maps applied by Alice and Bob.

A protocol is said to be $ϵ$-correct if, for all inputs $(x,y)$, the referee can output a bit $z$ with $Pr[z=f(x,y)]\ge 1-ϵ$.

A protocol is said to be $\delta$-secure if the distribution of the messages, call it $P_M$, is $\delta$-close in total variational distance to a simulator distribution, which itself depends only on $f(x,y)$,

$D(P_M,Si{m}_M(f(x,y)))\le \delta$.

In this article the communication cost of implementing function $f$ in the PSM model with $ϵ$-correctness and $\delta$-security will be denoted $PS{M}_{ϵ,\delta }(f)$. When $ϵ,\delta =0.1$ we abbreviate this as $PS{M}_{0.1,0.1}(f)=PSM(f)$. When $ϵ,\delta =0$ we abbreviate this as $PS{M}_{0,0}(f)=pPSM(f)$

Another variation of the PSM model allows $k$ players, each of whom sends a message to the referee. We will add a superscript $k$, i.e. to denote the communication cost with $k$ players, we write $PS{M}^k(f)$.

Upper and lower bounds on communication cost

There is a large gap between the best upper and lower bounds on the PSM model.

For every function, it is known that the communication cost of PSM is at most $2^{n/2}$. The following upper bounds are known for structured functions:

• If a function $f$ is computable using a non-deterministic memory of size $s$ and $s$ is $\mathrm{\Omega }(n)$, then $f$ can be computed in the PSM model with communication complexity $2^{O(s)}$. This allows the complexity class NL to be implemented efficiently.
• For $p$ a prime, consider a mod-$p$ Branching program of size $a(n)$ that computes $f$. Then there exists a PSM protocol for $f$ with communication complexity $O((\log p)\cdot n\cdot (a(n){)}^2)$. This allows the complexity class $mo{d}_{p}L$ to be implemented efficiently.
• There is an upper bound based on the Fourier 1 norm of $f$, $PSM(f)\le O(||f|{|}_1^2)$.

The simplest lower bounds on the PSM model are inherited from communication complexity: a PSM protocol in particular allows $f$ to be computed by the referee, so is also a (simultaneous message) communication protocol. Communication complexity based lower bounds are at best linear, since without the privacy requirement all functions can be computed in the simultaneous message model with $kn$ bits of communication, where $k$ is the number of players and $n$ the number of bits each player receives. Below, we focus on lower bounds that go beyond communication lower bounds by exploiting the privacy requirement.

• With $k$ players, there is a lower bound from Neciporuk's measure. For random functions, as well as some explicit functions, this leads to $\mathrm{\Omega }\left(\frac{k^{2}n}{2{\log }_2(kn)}\right)$ lower bounds.
• Based on combinatorial properties of the function $f$, the works prove a novel lower bound that uses privacy. For random functions, this bound evaluates to $3n-O(1)$.
• For perfectly secure, but imperfectly correct, PSM, there is a lower bound from the rank of the communication matrix of $f$. Note that perfectly correct PSM would automatically inherit this from the rank lower bound on communication complexity.

Quantum PSM

PSM can also be considered in the context of quantum information theory. In that case, we can allow Alice and Bob to share entanglement or allow them to send quantum messages, or both. In this case the correctness requirement on PSM remains the same (the referee should output $f(x,y)$ with high probability) and the security requirement is similar: the density matrix of the message systems should be close in trace distance to a simulator distribution.

Allowing quantum resources can never increase the communication cost of PSM, because a classically secure PSM protocol remains secure when requiring the quantum definition of security.

Quantum resources can provide an advantage for performing PSM. The first example of this was found by Kawachi and Nishimura, who found a partial function with linear communication cost in the classical setting, but logarithmic cost in the quantum setting. The classical cost here was only proved to be linear when requiring perfect correctness and perfect privacy. This was later improved to allow finite correctness and security errors.

The lower bound on classical PSM based on Neciporuk's measure can be extended to the quantum setting.