Communication Complexity of Private Simultaneous Quantum Messages Protocols

Background. Communication complexity has been an important research area in theoretical computer science for more than four decades, aiming to understand the communication cost of computing functions in a distributed manner [31, 25]. Since the advent of quantum information science, quantum communication complexity has also been studied intensively to determine the advantage of quantum information processing over its classical counterparts. A number of studies have succeeded in demonstrating the quantum advantages from the early days of quantum complexity theory [7, 28, 8].

Recently, much attention has been given to studying the amount of communication overhead required to preserve privacy in the field of cryptography, particularly, multi-party secure computation (MPC), to explore the optimal communication cost for privacy from the viewpoint of communication complexity [13, 12]. MPC is commonly based on a general network model that has complex communication patterns (e.g., in which each of many parties can freely interact with the other parties bidirectionally) unlike standard models in communication complexity (e.g., in which two parties can exchange messages only with each other). Therefore, many studies have focused on a special class of MPC that has simpler communication patterns, such as private simultaneous messages (PSM) protocols [14, 21, 9, 2, 1].

The two-party version of the PSM model was first proposed by Feige, Kilian, and Naor [14], and was later extended by Ishai and Kushilevitz [21]. In the general setting of the PSM model, we consider $k$ parties $P_{1},\ldots,P_{k}$ and a unique referee $R$. The party $P_{i}$ has its private input $x_{i}$, and all parties share a common random string $r$. Each $P_{i}$ generates message $m_{i}$ from $x_{i}$ and $r$, and then, sends $m_{i}$ to the referee $R$ only once. Note that each party is not allowed to interact with other parties. The referee $R$ receives the messages $m_{1},\ldots,m_{k}$, and computes an output value of a predetermined function $F$. The protocol generally has two properties correctness and privacy: Correctness signifies that the referee can compute $F(x_{1},\ldots,x_{k})$ correctly from the messages $m_{1},\ldots,m_{k}$, while privacy signifies that the referee $R$ learns nothing except for $F(x_{1},\ldots,x_{k})$ from the received messages $m_{1},\ldots,m_{k}$ in the information-theoretical sense.

In fact, the communication model of PSM protocols coincides with simultaneous message passing (SMP) protocols, which are known as traditional communication models in communication complexity [31, 25]. In the (number-in-hand) SMP model, $k$ parties $P_{1},\ldots,P_{k}$ that share a common random string $r$ (and sometimes entangled states), send their messages $m_{1},\ldots,m_{k}$ computed from individual inputs $x_{1},\ldots,x_{k}$ and the referee computes $F(x_{1},\ldots,x_{k})$ from $m_{1},\ldots,m_{k}$, as performed in the PSM model. Note that the SMP model does not require the privacy condition unlike the PSM model. The communication complexity of SMP protocols has been widely studied from the viewpoint of classical/quantum information to demonstrate the power of quantum communication [8, 18, 16].

Two-party quantum SMP models were first studied by Buhrman, Cleve, Watrous, and de Wolf [8] in the setting that the two parties do not share any randomness or entanglement. In this model, they demonstrated that the quantum communication complexity of the equality function is exponentially smaller than in the classical case. This result has been strengthened in the literature [4, 15], and Gavinsky [16] demonstrated that there is a relational problem whose quantum communication complexity is exponentially smaller than that of the two-way classical communication model. However, the power of shared entanglement in the SMP model is unclear. In one of the few related studies, Gavinsky, Kempe, Regev, and de Wolf [18] demonstrated that there is a relational problem that has an exponential gap between quantum SMP models with shared entanglement and without shared entanglement. However, the known maximum gap between them for total functions is only a constant multiplicative factor of $2$ [20, 22].

Although various studies have examined quantum versions of MPC so far (e.g., [10, 29, 11]), to the best of the authors’ knowledge, there has been no attempt to analyze quantum communication complexity under the privacy condition in a cryptographic setting, and such analysis is important to understand the advantages of quantum communication in a cryptographic setting.

Contributions. In this paper, we examine the power of quantum communication and shared entanglement under the information-theoretical privacy condition based on a standard communication model, namely, the PSM (or, equivalently, SMP) model. In particular, we propose a quantum counterpart of the classical PSM model called private simultaneous quantum messages (PSQM) model. In the PSQM model, parties $P_{1},\ldots,P_{k}$ which have classical private inputs $x_{1},\ldots,x_{k}$ share a common random string or entangled states in advance, and can send quantum messages to a quantum referee, $R$. Then, $R$ computes a classical output value $F(x_{1},\ldots,x_{k})$ for a given function $F$.

In the PSM (and its related) model, there are few results on lower bounds of communication complexity [1, 13, 3]. As one of such results, Applebaum, Holenstein, Mishra, and Shayevitz [1] proved a lower bound $(3-o(1))n$ of the communication complexity for random functions $F_{n}:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$ in the PSM model. In contrast, every function has the trivial upper bound $2n$ in the SMP model (i.e., the PSM model without the privacy condition). This result implies that the privacy condition creates communication overhead in the PSM model for some functions. Our first result demonstrates that this communication overhead is inevitable even if the parties can send quantum messages as in the PSQM model.

We also present a multiparty PSQM protocol for a total function that reduces the amount of quantum communication by half under the condition that the parties share entanglement compared to the case in which they do not share entanglement.

Actually, this function matches the equality function for the two-party case. It is known that for the equality function, the two-party quantum SMP model with shared entanglement reduces the amount of quantum communication by half compared to the corresponding model without shared entanglement (e.g. [20]). Our result implies that this reduction still holds even if the privacy condition is required.

Moreover, we present a two-party PSQM protocol with shared entanglement for a partial function that reduces the amount of quantum communication exponentially compared to the case in which the parties do not share entanglement.

Related Work. There have been several studies on quantum communication complexity with privacy conditions (e.g., [23, 17]), although they differed from a cryptographic setting. For example, Gavinsky and Ito [17] considered the SMP model with privacy; however it considered the information leakage of quantum messages when the input was randomly chosen, while in the cryptographic setting, privacy should be retained for any input.

In a study related to the PSQM model, Brakerski and Yuen [6] constructed a quantum version of decomposable randomized encoding schemes. In fact, decomposable randomized encoding is equivalent to the PSM model from a communication-complexity perspective. They demonstrated how to garble a general quantum circuit on quantum inputs in a decomposable manner via a constant-depth quantum circuit. In contrast, our study focuses on the communication complexity of computing several classical functions on classical inputs in the communication model.

More recently, Morimae [27] investigated relationships between quantum randomized encoding and other quantum protocols including quantum computing verification and blind quantum computing. For example, he proved that a randomized encoding scheme of the BB84 state generation implies a two-round verification scheme of quantum computing with a classical verifier that additionally performs the encoding operation, and that a quantum randomized encoding scheme with a classical encoding operation implies violation of the no-cloning theorem. His target of quantum randomized encoding schemes is similar to that of [6], that is, encoding for quantum circuits on quantum inputs rather than classical functions on classical inputs.

Let $[n]:=\{1,2,\ldots,n\}$. For any two $m$-bit strings $x=x_{1}\cdots x_{m}$ and $y=y_{1}\cdots y_{m}$, the product $x\cdot y$ denotes $\sum_{i\in[m]}x_{i}y_{i}\leavevmode\nobreak\ (\mbox{mod}\leavevmode\nobreak\ 2)$, and $x\oplus y$ denotes the $m$-bit string whose $i$th bit is the XOR of $x_{i}$ and $y_{i}$.

For any $m$-bit string $x=x_{1}x_{2}\cdots x_{m}$, let

be the corresponding polynomial over $\mathbb{F}_{2}$, where ${\sf q}_{m}$ is some irreducible polynomial of degree $m$ over $\mathbb{F}_{2}$. Note that ${\sf p}(x)$ is regarded as an element in $\mathbb{F}_{2^{m}}$, and ${\sf p}$ is a one-to-one correspondence between $\{0,1\}^{m}\setminus\{0^{m}\}$ and the multiplicative group $\mathbb{F}^{*}_{2^{m}}$.

We assume the reader is familiar with the basics of quantum information and computation such as quantum states and quantum operations (see, e.g, [19, 26]). According to the standard notations, Pauli gates $X$, $Z$, and the Hadamard gate $H$ denote

respectively.

In this section, we present the communication lower bounds of random functions for two-party PSQM protocols (Theorem 1.1).

The proof strategy is based on that of the classical case presented by Applebaum et al. [1]. The proof for the classical case considers two independent executions of a PSM protocol. It then evaluated the upper bounds of the collision probability, that is, the probability that the message in the first execution coincides with the one in the second execution, between two independent random messages. Because the collision probability is lower-bounded by the inverse of the size of the message domain, we can obtain the communication lower bound from the upper bound of the collision probability. Note that this argument is not available for quantum messages since they vary infinitely even over a finite number of qubits.

In order to extend the above argument to the case of quantum messages, we use the purity, $\mathrm{tr}\rho^{2}$, of a quantum message $\rho$ in a PSQM protocol instead of the collision probability. In accordance with its name, the purity is originally a measure of how pure a quantum state is. (For example, any pure state has a purity of $1$, and the $d$-dimensional maximally mixed state has $1/d$.) It is easy to see that the purity of a quantum state $\rho$ is lower-bounded by $1/\dim(\rho)$, and thus, we can obtain the communication lower bounds for a PSQM protocol by evaluating the upper bound of the purity of the quantum messages, similarly to the collision probability for a PSM protocol.

However, the purity of quantum messages is different from the collision probability between classical messages; thus, we must further adapt the proof technique in [1] to the purity. For example, while the collision probability is analyzed by combinatorial techniques in the proof of [1], we need to analyze the trace $\mathrm{tr}\rho^{2}$ combinatorially by extending the original proof (Claim 2). Also, the proof technique in [1] uses a unique collision (which is obtained from the property called non-degeneracy that random functions have with high probability) between two messages in two independent executions with any fixed shared random string. Instead of the unique collision, we consider weighted collisions defined from the inner product of two quantum messages and extend the original argument for the weighted collisions (Lemma 3.4).

Before discussing the details of the proof, we provide several technical definitions and notation required for the proof of the lower bounds. In this section, we denote ${\cal X}_{n,i}$ by ${\cal X}_{i}$. We use $\rho(x_{1},x_{2};r)=\rho_{1}(x_{1};r)\otimes\rho_{2}(x_{2};r)$ to the entire quantum message sent from $P_{1}$ and $P_{2}$ on individual inputs $x_{1}\in{\cal X}_{1}$ and $x_{2}\in{\cal X}_{2}$ with a shared random string $r$ to $R$, where $\rho_{1}(x_{1};r)$ denotes $P_{1}$’s message and $\rho_{2}(x_{2};r)$ denotes $P_{2}$’s message.

Let $\mu$ be a distribution over $\mathcal{X}_{1}\times\mathcal{X}_{2}$ with marginal distributions $\mu_{1}$ and $\mu_{2}$. We define $\mathrm{Supp}(\mu)$ for a distribution $\mu$ as a set $\{x:$. We say that function $F_{n}$ is non-degenerate under distribution $\mu$ if for every distinct $x_{1}\in\mathrm{Supp}(\mu_{1})$ and $x^{\prime}_{1}\in\mathrm{Supp}(\mu_{1})$, there exists $x_{2}\in\mathrm{Supp}(\mu_{2})$ such that $F_{n}(x_{1},x_{2})\neq F_{n}(x^{\prime}_{1},x_{2})$ and for every distinct $x_{2}\in\mathrm{Supp}(\mu_{2})$ and $x^{\prime}_{2}\in\mathrm{Supp}(\mu_{2})$ there exists $x_{1}$ such that $F_{n}(x_{1},x_{2})\neq F_{n}(x_{1},x^{\prime}_{2})$. We say that $F_{n}$ is non-degenerate if the above holds when replacing $\mathrm{Supp}(\mu_{1})$ and $\mathrm{Supp}(\mu_{2})$ by $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$, respectively.

A rectangle $\mathcal{R}$ of size $k\times\ell$ over $\mathcal{X}_{1}\times\mathcal{X}_{2}$ is defined as $((x_{1,1},\ldots,x_{1,k}),(x_{2,1},\ldots,x_{2,\ell}))$, where $x_{1,i}\in\mathcal{X}_{1},x_{2,j}\in\mathcal{X}_{2}$ for every $i,j$, $x_{1,i}\neq x_{1,i^{\prime}}$ for every distinct $i,i^{\prime}$, and $x_{2,j}\neq x_{2,j^{\prime}}$ for every distinct $j,j^{\prime}$. We say that two rectangles $\mathcal{R}=((x_{1,1},\ldots,x_{1,k}),(x_{2,1},\ldots,x_{2,\ell}))$ and $\mathcal{R}^{\prime}=((x^{\prime}_{1,1},\ldots,x^{\prime}_{1,k}),(x^{\prime}_{2,1},\ldots,x^{\prime}_{2,\ell}))$ are $\mathcal{X}_{1}$-disjoint (resp. $\mathcal{X}_{2}$-disjoint) if $x_{1,i}\neq x^{\prime}_{1,i}$ for every $i\in[k]$ (resp. if $x_{2,j}\neq x^{\prime}_{2,j}$ for every $j\in[\ell]$). In particular, we say that $\mathcal{R}$ and $\mathcal{R}^{\prime}$ are disjoint if they are either $\mathcal{X}_{1}$-disjoint or $\mathcal{X}_{2}$-disjoint.

For a rectangle $\mathcal{R}=((x_{1,1},\ldots,x_{1,k}),(x_{2,1},\ldots,x_{2,\ell}))$, let $F_{n}[\mathcal{R}]$ be a matrix whose $(i,j)$-entry is $F_{n}(x_{1,i},x_{2,j})$, and let $\mu(\mathcal{R})=\sum_{i\in[k],j\in[\ell]}\mu(x_{1,i},x_{2,j})$. We say that $\mathcal{R}$ is similar to $\mathcal{R}^{\prime}$ if $F_{n}[\mathcal{R}]=F_{n}[\mathcal{R}^{\prime}]$. We define

where the maximum ranges over all pairs of similar disjoint rectangles $(\mathcal{R}_{1},\mathcal{R}_{2})$. In addition,

where $(X_{1},X_{2})$ and $(X_{1}^{\prime},X_{2}^{\prime})$ are independent.

We can demonstrate the communication lower bound in Theorem 1.1 from the following main technical lemma combined with an appropriate function $F_{n}$, which is provided in the study by Applebaum et al. [1].

From the previous study [1], we can obtain the appropriate function by selecting a function at random, as illustrated in the following theorem.

Considering the uniform distribution $U$ over $\{0,1\}^{n}\times\{0,1\}^{n}$, the communication lower bound from Lemma 3.1 of PSQM protocols for $F_{n}:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$ is bounded by $\log(\alpha(U)^{-1})+H_{\infty}(U)-\log(\beta(U)^{-1})-1$. By Theorem 3.2, we can easily see that this bound is $3n-2\log{n}-O(1)$ for a $(1-o(1))$ fraction of the functions $\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}$, as given in Theorem 1.1.

Now, we provide the proof of the main technical lemma.