Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

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

Léonard Assouline, Tianren Liu

Published Jan 1, 2021• 9 citations
Publisher
DOI
10.1007/978-3-030-90453-1_7

Related papers

Multi-party Distributed Point Functions, Revisited

Elaine Shi, 顾天瑶, Xuanye Zheng +3 more

Lecture notes in computer science•Nov 5, 2026•0 citations

Ideal Private Simultaneous Messages Schemes and Their Applications

Keitaro Hiwatashi, Reo Eriguchi

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.

Leibniz international proceedings in informatics•Jan 1, 2026•1 citation

The Complexity of Multiparty PSM Protocols and Related Models

Amos Beimel, Eyal Kushilevitz, Pnina Nissim

Lecture notes in computer science•Jan 1, 2018•41 citations

New bounds on private simultaneous quantum message passing

Uma Girish, Alex May, Natalie Parham +1 more

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then each send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. 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(x_1,x_2)$ 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$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $ε$ a correctness parameter, we obtain $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones.

quant-pharXiv:2606.12557•Jun 12, 2026•3 citations

Recent Progress in Private Simultaneous Messages Protocols

Akinori Kawachi

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_{\imath}$ has a private input $x_{i}$ for $i=1, \ldots, k$. For a function f, each $\lt p\gt P_{i}$ encrypts $x_{i}$ into a message $m_{i}$ with a random string r shared among $\lt p\gt P_{1}, \ldots, P_{k}$, and sends $m_{i}$ to the referee $R. R$ computes $f\left(x_{1}, \ldots, x_{k}\right)$ from their respective messages $m_{1}, \ldots, m_{k}$. Then, R learns nothing from $m_{1}, \ldots, m_{k}$ except for the output value $f\left(x_{1}, \ldots, x_{k}\right)$. This simple model provides interesting cryptographic applications and is essential for understanding the intrinsic costs (e.g., of communication $\left|m_{1}\right|+\ldots+\left|m_{k}\right|$ and randomness $|r|$) to achieve MPC. This study surveys recent results associated with the PSM and closely related models.

IEEE Information Theory Workshop (ITW)•Oct 17, 2021•2 citations

Multiparty Interactive Communication with Private Channels

Aggarwal Abhinav, Varsha Dani, P Hayes Thomas +1 more

ACM Proceedings•Jan 1, 2019•0 citations
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, kkk players obtain inputs xi∈{0,1}nx_i\in\{0,1\}^nxi​∈{0,1}n and then each send messages to a referee, who should learn f(x1,...,xk)f(x_1,...,x_k)f(x1​,...,xk​) but no other information about (x1,...,xk)(x_1,...,x_k)(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 kkk-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)f(x_1,x_2)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 sss be the size of a quantum circuit computing fff, dfd_fdf​ be the circuit depth, kkk the number of players, nnn the number of bits received by each player, and εεε a correctness parameter, we obtain PSMk∗(f)≤(kn+s)⋅log⁡O(df)(s/ε)\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O(d_f)}(s/ε)PSMk∗​(f)≤(kn+s)⋅logO(df​)(s/ε). 2) The square of the Fourier 1 norm of fff, ∥f^∥12\Vert \hat{f}\Vert_1^2∥f^​∥12​, upper bounds the classical PSM complexity, PSM(f)≤O(∥f^∥12)\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)PSM(f)≤O(∥f^​∥12​). In proving the first upper bound, we generalize existing TTT-depth based techniques for NLQC from 222 to k≥2k\geq 2k≥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ıP_{\imath}P​ has a private input xix_{i}xi​ for i=1,…,ki=1, \ldots, ki=1,…,k. For a function f, each <p>Pi\lt p\gt P_{i}<p>Pi​ encrypts xix_{i}xi​ into a message mim_{i}mi​ with a random string r shared among <p>P1,…,Pk\lt p\gt P_{1}, \ldots, P_{k}<p>P1​,…,Pk​, and sends mim_{i}mi​ to the referee R.RR. RR.R computes f(x1,…,xk)f\left(x_{1}, \ldots, x_{k}\right)f(x1​,…,xk​) from their respective messages m1,…,mkm_{1}, \ldots, m_{k}m1​,…,mk​. Then, R learns nothing from m1,…,mkm_{1}, \ldots, m_{k}m1​,…,mk​ except for the output value f(x1,…,xk)f\left(x_{1}, \ldots, x_{k}\right)f(x1​,…,xk​). This simple model provides interesting cryptographic applications and is essential for understanding the intrinsic costs (e.g., of communication ∣m1∣+…+∣mk∣\left|m_{1}\right|+\ldots+\left|m_{k}\right|∣m1​∣+…+∣mk​∣ and randomness ∣r∣|r|∣r∣) to achieve MPC. This study surveys recent results associated with the PSM and closely related models.