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

The Complexity of Multiparty PSM Protocols and Related Models

Amos Beimel, Eyal Kushilevitz, Pnina Nissim

Published Jan 1, 2018• 41 citations
Publisher
DOI
10.1007/978-3-319-78375-8_10

Related papers

Ad Hoc PSM Protocols: Secure Computation Without Coordination

Amos Beimel, Yuval Ishai, Eyal Kushilevitz

Lecture notes in computer science•Jan 1, 2017•19 citations

Explicit Lower Bounds for Communication Complexity of PSM for Concrete Functions

Kazumasa Shinagawa, Koji Nuida

Lecture notes in computer science•Jan 1, 2024•4 citations

Private simultaneous messages based on quadratic residues

Kazumasa Shinagawa, Reo Eriguchi, Shohei Satake +1 more

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 .

arXiv:2209.01859•Designs Codes and Cryptography•Aug 16, 2023•4 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

Theory and Practice of Multiparty Computation

Ivan Damgård

Lecture notes in computer science•Jan 1, 2006•9 citations

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

Léonard Assouline, Tianren Liu

Lecture notes in computer science•Jan 1, 2021•9 citations
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 \rightarrow \{0,1\}f:{0,1}n→{0,1} f : { 0 , 1 } n → { 0 , 1 } of communication complexity O(n2)O(n^2)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(n2log⁡n)O(n^2\log n)O(n2logn) O ( n 2 log n ) (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields Fp\mathbb {F}_pFp​ 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−2p \le (1+o(1))N^22^{2N-2}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+\sqrt{2})^2(1+2​)2 ( 1 + 2 ) 2 .
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.