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

arXiv:2611.04052

On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle

Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Published Nov 2, 2026• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2611.04052

Related papers

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

quant-pharXiv:2610.02101•Oct 2, 2026•1 citation

On the Communication Complexity of Key-Agreement Protocols

Iftach Haitner, Noam Mazor, Rotem Oshman +2 more

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any l-query protocol can be revealed by an O(l^2)-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly l^2 queries, the honest parties need to exchange Omega(l) bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven (in the random-oracle model) is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.

arXiv:2105.01958•Leibniz international proceedings in informatics•Jan 1, 2019•9 citations

TurboPack: Honest Majority MPC with Constant Online Communication

Daniel E. Escudero, Vipul Goyal, Antigoni Polychroniadou +1 more

We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires 12 elements in total per multiplication gate with circuit-dependent preprocessing, or 20 elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in n, the number of parties, with the best prior existing solution involving 1.5n elements per multiplication gate. Only one recent work packing [28] achieves constant online communication complexity, but the constants are large (108 elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 7, 2022•31 citations

Communication and Randomness Lower Bounds for Secure Computation

Deepesh Data, Vinod M. Prabhakaran, Manoj Prabhakaran

In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.

arXiv:1512.07735•IEEE Transactions on Information Theory•May 13, 2016•37 citations

Unconditionally Secure MPC for Boolean Circuits With Constant Online Communication

Zhenkai Hu, Kang Yang, Yu Yu

Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires$12 log (5n/4$) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number$n$of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.

IEEE Computer Security Foundations Workshop (CSFW)•Jul 8, 2024•1 citation

Lower Bounds on Quantum Multiparty Communication Complexity

Troy Lee, Gideon Schechtman, Adi Shraibman

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•22 citations
Information-theoretic MPC among nnn parties with ttt corruptions can securely evaluate a circuit CCC with O(∣C∣⋅t/(n−t))O(|C| \cdot t/(n-t))O(∣C∣⋅t/(n−t)) online communication in the preprocessing model and O(∣C∣⋅t/(n−2t))O(|C| \cdot t/(n-2t))O(∣C∣⋅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∣⋅t/(n−t))Ω(|C| \cdot t/(n-t))Ω(∣C∣⋅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∣)Ω(|C|)Ω(∣C∣) communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when n=O(log⁡λ)n = O(\log λ)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 poly(λ,log⁡∣C∣)\mathrm{poly}(λ, \log |C|)poly(λ,log∣C∣) communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits CCC such that every blackbox protocol with o(∣C∣)o(|C|)o(∣C∣) quantum communication must perform Ω(∣C∣)Ω(|C|)Ω(∣C∣) cryptographic operations.
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a TTT-query adversary with SSS qubits of non-uniform advice can recover a random key kkk from the nnn-qubit binary phase state ∣ψk⟩∝∑xR(k,x)∣x⟩|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle∣ψk​⟩∝∑x​R(k,x)∣x⟩ with probability at most O(T2+STN)O(\frac{T^2 + \sqrt{ST}}{N})O(NT2+ST​​) for N=2nN=2^nN=2n. In contrast, the best known bound for post-quantum one-way functions is O(T2+STN)O(\frac{T^2 + ST}{N})O(NT2+ST​), with a trivial attack at S=NS = NS=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: nnn qubits of communication suffice for security against preprocessing attacks with space up to N2N^2N2 rather than NNN. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(T2N+STN)O(\frac{T^2}N + \sqrt{\frac{ST}N})O(NT2​+NST​​). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(SN)O(\frac{\sqrt{S}}N)O(NS​​) bound for the pseudorandomness of random binary phase states against space SSS distinguishers.
Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any l-query protocol can be revealed by an O(l^2)-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly l^2 queries, the honest parties need to exchange Omega(l) bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven (in the random-oracle model) is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.
We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires 12 elements in total per multiplication gate with circuit-dependent preprocessing, or 20 elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in n, the number of parties, with the best prior existing solution involving 1.5n elements per multiplication gate. Only one recent work packing [28] achieves constant online communication complexity, but the constants are large (108 elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties.
In secure multiparty computation (MPC), mutually distrusting users collaborate to compute a function of their private data without revealing any additional information about their data to the other users. While it is known that information theoretically secure MPC is possible among n users having access to private randomness and are pairwise connected by secure, noiseless, and bidirectional links against the collusion of less than n/2 users (in the honest-but-curious model; the threshold is n/3 in the malicious model), relatively little is known about the communication and randomness complexity of secure computation, i.e., the amount of communication and randomness required to compute securely. In this paper, we employ information theoretic techniques to obtain lower bounds on communication and randomness complexity of secure MPC. We restrict ourselves to a concrete interactive setting involving three users under which all functions are securely computable against corruption of individual users in the honest-but-curious model. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to ∞). Our techniques include the use of a data processing inequality for residual information (i.e., the gap between mutual information and Gács-Körner common information), a new information inequality for three-user protocols, and the idea of distribution switching by which lower bounds computed under certain worst case scenarios can be shown to apply for the general case. Our lower bounds are shown to be tight for various functions of interest. In particular, we show concrete functions which have communication-ideal protocols, i.e., which achieve the minimum communication simultaneously on all links in the network. Also, we obtain the first explicit example of a function that incurs a higher communication cost than the input length, in the secure computation model of Feige et al. (26th Annual ACM Symposium on Theory of Computing, 1994), who had shown that such functions exist. We also show that our communication bounds imply tight lower bounds on the amount of randomness required by MPC protocols for many interesting functions.
Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires12log(5n/412 log (5n/412log(5n/4) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the numbernnnof parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.