Abstract Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p of what is computed from messages. We design a QR-PSM protocol for any symmetric function $$f: \{0,1\}^n \rightarrow \{0,1\}$$ f : { 0 , 1 } n → { 0 , 1 } of communication complexity $$O(n^2)$$ O ( n 2 ) . As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of $$O(n^2\log n)$$ O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields $$\mathbb {F}_p$$ F p in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p. We show that there is a prime $$p \le (1+o(1))N^22^{2N-2}$$ p ≤ ( 1 + o ( 1 ) ) N 2 2 2 N - 2 such that any length-N pattern of quadratic (non)residues appears modulo p (and hence it can be used for general QR-PSM protocols), which improves the Peralta’s known result (Mathematics of Computation 1992) by a constant factor $$(1+\sqrt{2})^2$$ ( 1 + 2 ) 2 .
Abstract Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p of what is computed from messages. We design a QR-PSM protocol for any symmetric function f:{0,1}n→{0,1} f : { 0 , 1 } n → { 0 , 1 } of communication complexity O(n2) O ( n 2 ) . As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of O(n2logn) O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields Fp F p in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p. We show that there is a prime p≤(1+o(1))N222N−2 p ≤ ( 1 + o ( 1 ) ) N 2 2 2 N - 2 such that any length-N pattern of quadratic (non)residues appears modulo p (and hence it can be used for general QR-PSM protocols), which improves the Peralta’s known result (Mathematics of Computation 1992) by a constant factor (1+2)2 ( 1 + 2 ) 2 .
Private Simultaneous Messages (PSM) is a minimal model for secure computation, where two parties, Alice and Bob, have private inputs x,y and a shared random string. Each of them sends a single message to an external party, Charlie, who can compute f(x,y) for a public function f but learns nothing else. The problem of narrowing the gap between upper and lower bounds on the communication complexity of PSM has been widely studied, but the gap still remains exponential. In this work, we study the communication complexity of PSM from a different perspective and introduce a special class of PSM, referred to as ideal PSM, in which each party’s message length attains the minimum, that is, their messages are taken from the same domain as inputs. We initiate a systematic study of ideal PSM with a complete characterization, several positive results, and applications. First, we provide a characterization of the class of functions that admit ideal PSM, based on permutation groups acting on the input domain. This characterization allows us to derive asymptotic upper bounds on the total number of such functions and a complete list for small domains. We also present several infinite families of functions of practical interest that admit ideal PSM. Interestingly, by simply restricting the input domains of these ideal PSM schemes, we can recover most of the existing PSM schemes that achieve the best known communication complexity in various computation models. As applications, we show that these ideal PSM schemes yield novel communication-efficient PSM schemes for functions with sparse or dense truth-tables and those with low-rank truth-tables. Furthermore, we obtain a PSM scheme for general functions that improves the constant factor in the dominant term of the best known communication complexity. An additional advantage is that our scheme simplifies the existing construction by avoiding the hierarchical design of internally invoking PSM schemes for smaller functions.
In the private simultaneous message (PSM) setting, k players obtain inputs xi∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk) but no other information about (x1,...,xk). The PSM setting was introduced as a minimal model for secure multiparty computation and has connections to Boolean function complexity. In the quantum setting, PSM has been related to non-local quantum computation (NLQC). The communication and correlation cost of implementing PSM remains poorly understood. Here, we give new upper and lower bounds on the (quantum) PSM model. For lower bounds, we show: 1) Nečiporuk's measure lower bounds the entanglement required for k-player quantum PSM with perfect correctness. This leads to quadratic lower bounds for explicit functions. 2) The rank of the communication matrix of f(x1,x2) lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing quantum communication and shared entanglement, these are the first lower bounds on quantum PSM that make use of the privacy condition. For upper bounds, we show: 1) Letting s be the size of a quantum circuit computing f, df be the circuit depth, k the number of players, n the number of bits received by each player, and ε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅logO(df)(s/ε). 2) The square of the Fourier 1 norm of f, ∥f^∥12, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12). In proving the first upper bound, we generalize existing T-depth based techniques for NLQC from 2 to k≥2 parties, and consider cases where the Clifford layers are restricted to having small light cones.
The private simultaneous messages (PSM) model is a simple variant of the secure multiparty computation (MPC). In the k-party PSM model, each party P has a private input xi for i=1,…,k. For a function f, each <p>Pi encrypts xi into a message mi with a random string r shared among <p>P1,…,Pk, and sends mi to the referee R.R computes f(x1,…,xk) from their respective messages m1,…,mk. Then, R learns nothing from m1,…,mk except for the output value f(x1,…,xk). This simple model provides interesting cryptographic applications and is essential for understanding the intrinsic costs (e.g., of communication ∣m1∣+…+∣mk∣ and randomness ∣r∣) to achieve MPC. This study surveys recent results associated with the PSM and closely related models.
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on n-bit inputs, which determines whether the players' n-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633…)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3log23. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥3, we construct a perfectly correct and perfectly private one-shot protocol for k-bit AND using one qudit of dimension at most k per player, and hence at most klog2k qubits in total.
The private simultaneous messages model is a non-interactive version of the multiparty secure computation, which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, k parties P1,…,Pk initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x1,…,xk. Every Pi generates a quantum message from the private input xi and the shared random string (entangled states), and then sends it to the referee R. Receiving the messages, R computes F(x1,…,xk). Then, R learns nothing except for F(x1,…,xk) as the privacy condition. We obtain the following results for this PSQM model. (1) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In particular, we prove a lower bound (3−o(1))n of the communication complexity in two-party PSQM protocols with a shared random string for random Boolean functions of 2n-bit input, which is larger than the trivial upper bound 2n of the communication complexity without the privacy condition. (2) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (3) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model of quantum private simultaneous message protocols (QPSM), where classical communication is free, and quantum communication is the primary complexity measure. We show the following upper and lower bounds. (1) For every quantum channel mapping n to m qubits, we give a QPSM protocol with quantum communication m, using exponential pre-shared entanglement. In particular, constant-output channels have O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0 for which any protocol with at most cn pre-shared entanglement requires Ω(n) quantum communication. (3) In contrast, we identify a structured class of quantum channels, Clifford-induced channels, for which there exist QPSM protocols with O(n) pre-shared entangled qubits and only O(1) quantum communication complexity. Through our connection, we obtain analogous upper and lower bounds on the quantum encoding size of QDRE. Our results show that the amount of pre-shared entanglement plays a central role in quantum encoding size and quantum communication complexity.