1 Search Results for "Schwartzbach, Nikolaj Ignatieff"


Document
More Communication Lower Bounds for Information-Theoretic MPC

Authors: Ivan Bjerre Damgård, Boyang Li, and Nikolaj Ignatieff Schwartzbach

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)


Abstract
We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation in the standard model with n = 2t+1 parties of which t are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn or not learn the output. Specifically, we show that there is a function H^* such that for any protocol that evaluates y_i = b_i ⋅ f(x₁,...,x_n) with perfect passive security (where b_i is a private boolean input), the total communication must be at least 1/2 ∑_{i = 1}ⁿ H_f^*(x_i) bits of information. The second lower bound applies to the perfect maliciously secure setting with n = 3t+1 parties. We show that for any n and all large enough S, there exists a reactive functionality F_S taking an S-bit string as input (and with short output) such that any protocol implementing F_S with perfect malicious security must communicate Ω(nS) bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any n and all large enough g ∈ ℕ there exists a reactive functionality F_C doing computation specified by a Boolean circuit C with g gates, where any perfectly secure protocol implementing F_C must communicate Ω(n g) bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lg n off for Boolean circuits). Both results also extend to the case where the threshold t is suboptimal. Namely if n = kt+s the bound is weakened by a factor O(s), which corresponds to known optimizations via packed secret-sharing.

Cite as

Ivan Bjerre Damgård, Boyang Li, and Nikolaj Ignatieff Schwartzbach. More Communication Lower Bounds for Information-Theoretic MPC. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2021.2,
  author =	{Damg\r{a}rd, Ivan Bjerre and Li, Boyang and Schwartzbach, Nikolaj Ignatieff},
  title =	{{More Communication Lower Bounds for Information-Theoretic MPC}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{2:1--2:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.2},
  URN =		{urn:nbn:de:0030-drops-143211},
  doi =		{10.4230/LIPIcs.ITC.2021.2},
  annote =	{Keywords: Multiparty Computation, Lower bounds}
}
  • Refine by Author
  • 1 Damgård, Ivan Bjerre
  • 1 Li, Boyang
  • 1 Schwartzbach, Nikolaj Ignatieff

  • Refine by Classification
  • 1 Security and privacy → Information-theoretic techniques

  • Refine by Keyword
  • 1 Lower bounds
  • 1 Multiparty Computation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail