Summary
Secure multiparty computation (MPC) lets multiple people jointly compute a function without revealing their private inputs. This paper studies communication limits—how much data must be exchanged—for MPC protocols under various conditions, including when quantum communication or random oracles are available. The authors show that even with these powerful tools, communication cannot be significantly reduced beyond known lower bounds for many settings. However, they also provide a new two-party quantum protocol that can reduce communication for some cases, though it requires many cryptographic steps. These findings clarify what advantages quantum or random oracle resources can and cannot provide in secure computations.
What this means in practice
- •For security protocol designers: Understand fundamental communication limits for secure multiparty protocols when incorporating quantum or random oracle tools to guide efficient protocol design.
- •For quantum cryptography engineers: Develop quantum-secure two-party protocols with reduced communication for evaluating certain circuits, enabled by the presented quantum communication construction.
A theory result. No direct application yet.
Abstract
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 $Ω(|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 $Ω(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log λ)$, 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}(λ, \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 $Ω(|C|)$ cryptographic operations.