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

Journal of Cryptology

The Communication Complexity of Private Simultaneous Messages, Revisited

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

Published Sep 17, 2019• 19 citations
Publisher
DOI
10.1007/s00145-019-09334-y

Related papers

The Communication Complexity of Private Simultaneous Messages, Revisited

Benny Applebaum, Thomas Holenstein, Manoj Mishra +1 more

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

Efficient Multiparty Private Simultaneous Messages for Symmetric Functions

Reo Eriguchi, Kazumasa Shinagawa

Lecture notes in computer science•Jan 1, 2025•2 citations

From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

Benny Applebaum, Pavel Raykov

Lecture notes in computer science•Dec 23, 2015•13 citations

From Private Simultaneous Messages to Zero-Information Arthur–Merlin Protocols and Back

Benny Applebaum, Pavel Raykov

Journal of Cryptology•Jul 18, 2016•6 citations

Improved Private Simultaneous Messages Protocols for Symmetric Functions with Universal Reconstruction

Koji Nuida

Lecture notes in computer science•Nov 24, 2025•0 citations

Quantum Encodings, Private Messages, and Communication Complexity

Tom Gur, Miryam Mi-Ying Huang, Er-Cheng Tang

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.

quant-pharXiv:2609.17690•Sep 17, 2026•1 citation
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 nnn to mmm qubits, we give a QPSM protocol with quantum communication mmm, using exponential pre-shared entanglement. In particular, constant-output channels have O(1)O(1)O(1) quantum communication, and classical-output channels require no quantum communication. (2) With O(n)O(n)O(n) pre-shared entanglement, every one-qubit-output channel has an O(n)O(n)O(n)-quantum-communication QPSM protocol. Conversely, there exists a channel and a constant c>0c>0c>0 for which any protocol with at most cncncn pre-shared entanglement requires Ω(n)Ω(n)Ω(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)O(n)O(n) pre-shared entangled qubits and only O(1)O(1)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.