Communication and Randomness Lower Bounds for Secure Computation Article Swipe

MAKE IMPACT

Deepesh Data , Vinod M. Prabhakaran , Manoj Prabhakaran · YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.1109/tit.2016.2568207

In secure multiparty computation (MPC), mutually distrusting users\ncollaborate to compute a function of their private data without revealing any\nadditional information about their data to other users. While it is known that\ninformation theoretically secure MPC is possible among $n$ users (connected by\nsecure and noiseless links and have access to private randomness) against the\ncollusion of less than $n/2$ users in the honest-but-curious model, relatively\nless is known about the communication and randomness complexity of secure\ncomputation.\n In this work, we employ information theoretic techniques to obtain lower\nbounds on the amount of communication and randomness required for secure MPC.\nWe restrict ourselves to a concrete interactive setting involving 3 users under\nwhich all functions are securely computable against corruption of a single user\nin the honest-but-curious model. We derive lower bounds for both the perfect\nsecurity case (i.e., zero-error and no leakage of information) and asymptotic\nsecurity (where the probability of error and information leakage vanish as\nblock-length goes to $\\infty$).\n Our techniques include the use of a data processing inequality for residual\ninformation (i.e., the gap between mutual information and G\\'acs-K\\"orner\ncommon information), a new information inequality for 3-user protocols, and the\nidea of distribution switching. Our lower bounds are shown to be tight for\nvarious functions of interest. In particular, we show concrete functions which\nhave "communication-ideal" protocols, i.e., which achieve the minimum\ncommunication simultaneously on all links in the network, and also use minimum\namount of randomness. Also, we obtain the first explicit example of a function\nthat incurs a higher communication cost than the input length in the secure\ncomputation model of "Feige, Kilian, and Naor [STOC, 1994]", who had shown that\nsuch functions exist.\n

Type

article

Language

en

Landing Page

https://doi.org/10.1109/tit.2016.2568207

OA Status

green

Cited By

34

References

67

Related Works

10

OpenAlex ID

https://openalex.org/W2197751114

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2197751114

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.1109/tit.2016.2568207

Digital Object Identifier

Title

Communication and Randomness Lower Bounds for Secure Computation

Work title

Type

article

OpenAlex work type

Language

en

Primary language

Publication year

2016

Year of publication

Publication date

2016-05-13

Full publication date if available

Authors

Deepesh Data, Vinod M. Prabhakaran, Manoj Prabhakaran

List of authors in order

Landing page

https://doi.org/10.1109/tit.2016.2568207

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1512.07735

Direct OA link when available

Concepts

Randomness, Communication complexity, Computer science, Secure multi-party computation, Secure communication, Information leakage, Information theory, Private information retrieval, Theoretical computer science, Computation, Cryptography, Secure two-party computation, Security parameter, Mathematics, Computer network, Algorithm, Computer security, Encryption, Statistics

Top concepts (fields/topics) attached by OpenAlex

Cited by

34

Total citation count in OpenAlex

Citations by year (recent)

2025: 2, 2024: 2, 2023: 5, 2022: 6, 2021: 7

Per-year citation counts (last 5 years)

References (count)

67

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload