Metraipolis › archive › dc_a6416cdfd99c

On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle — arXiv:2611.04052

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04052
License (as archived): CC0-1.0
Archived: 2026-11-04T21:49:37.953Z
SHA-256 of the archived text: ae1137528503dc8cc811196373115cde10e83897a7c0ea80281917259caf0b9e
Stable URL of this page: https://metraipolis.com/documento/dc_a6416cdfd99c

How to cite

On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle — arXiv:2611.04052 — arXiv (en), https://arxiv.org/abs/2611.04052 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a6416cdfd99c (Metraipolis archive dc_a6416cdfd99c, sha256 ae1137528503dc8cc811196373115cde10e83897a7c0ea80281917259caf0b9e)

BibTeX

@misc{dca6416cdfd99c,
  title = {On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle — arXiv:2611.04052},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04052},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a6416cdfd99c; sha256 ae1137528503dc8cc811196373115cde10e83897a7c0ea80281917259caf0b9e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04052. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Information-theoretic MPC among $n$ parties with $t$ corruptions can securely evaluate a circuit $C$ with $O(|C| \cdot t/(n-t))$ online communication in the preprocessing model and $O(|C| \cdot t/(n-2t))$ communication in the honest majority setting. Damgård, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same $\Omega(|C| \cdot t/(n-t))$ lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an $\Omega(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log \lambda)$, beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with $\mathrm{poly}(\lambda, \log |C|)$ communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits $C$ such that every blackbox protocol with $o(|C|)$ quantum communication must perform $\Omega(|C|)$ cryptographic operations.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Cryptography and Security (cs.CR) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.04052 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:38:19.518Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).