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

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

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

(29)

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

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)