On the communication complexity of secure computation

DOI10.1007/978-3-662-44381-1_12MaRDI QIDQ2874538zbMATH OpenOpenAlexFDO

Authors Deepesh Data, Manoj Prabhakaran, Vinod M. Prabhakaran

Publication date 7 August 2014

Published in Advances in Cryptology – CRYPTO 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.7584

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Cryptography (94A60)

Abstract: Information theoretically secure multi-party computation (MPC) is a central primitive of modern cryptography. However, relatively little is known about the communication complexity of this primitive. In this work, we develop powerful information theoretic tools to prove lower bounds on the communication complexity of MPC. We restrict ourselves to a 3-party setting in order to bring out the power of these tools without introducing too many complications. Our techniques include the use of a data processing inequality for residual information - i.e., the gap between mutual information and G'acs-K"orner common information, a new information inequality for 3-party 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. Using these techniques we obtain tight bounds on communication complexity by MPC protocols for various interesting functions. In particular, we show concrete functions that have "communication-ideal" protocols, 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, Kilian and Naor (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.

Recommendations

• scientific article; zbMATH DE number 7706034
• Tight bounds on the randomness complexity of secure multiparty computation
• Perfectly-Secure MPC with Linear Communication Complexity
• Communication lower bounds for statistically secure MPC, with or without preprocessing
• On the message complexity of secure multiparty computation

Cited in

(31)

• On the (in)efficiency of non-interactive secure multiparty computation
• The price of low communication in secure multi-party computation
• Secure computation with low communication from cross-checking
• On the message complexity of secure multiparty computation
• On the compressed-oracle technique, and post-quantum security of proofs of sequential work
• On the round complexity of secure quantum computation
• Optimality of a protocol by Feige-Kilian-Naor for three-party secure computation
• A note on the communication complexity of multiparty computation in the correlated randomness model
• Communication lower bounds for statistically secure MPC, with or without preprocessing
• Accumulating automata and cascaded equations automata for communicationless information theoretically secure multi-party computation
• Secure multiparty computation with general interaction patterns
• On the communication required for unconditionally secure multiplication
• Communication and Randomness Lower Bounds for Secure Computation
• Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations
• Communication complexity of secure distributed computation in the presence of noise
• Communication complexity of key agreement on small ranges
• The bottleneck complexity of secure multiparty computation
• On the bottleneck complexity of MPC with correlated randomness
• Some open problems in information-theoretic cryptography
• Automata, Languages and Programming
• The Exact Round Complexity of Secure Computation
• Theory of Cryptography
• scientific article; zbMATH DE number 7706034 (Why is no real title available?)
• On query-to-communication lifting for adversary bounds
• Tight bounds on the randomness complexity of secure multiparty computation
• Explicit lower bounds for communication complexity of PSM for concrete functions
• MPC with low bottleneck-complexity: information-theoretic security and more
• Exponential correlated randomness is necessary in communication-optimal perfectly secure two-party computation
• Efficient multiparty private simultaneous messages for symmetric functions
• Complexity of secure sets
• Card-based protocols imply PSM protocols

This page was built for publication: On the communication complexity of secure computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874538)