4 Search Results for "Damgård, Ivan"

Document
DOI: 10.4230/LIPIcs.ITC.2023.7
Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks

Authors: Ivan Damgård, Daniel Escudero, and Antigoni Polychroniadou

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
We consider the task of designing secure computation protocols in an unstable network where honest parties can drop out at any time, according to a schedule provided by the adversary. This type of setting, where even honest parties are prone to failures, is more realistic than traditional models, and has therefore gained a lot of attention recently. Our model, Phoenix, enables a new approach to secure multiparty computation with dropouts, allowing parties to drop out and re-enter the computation on an adversarially-chosen schedule and without assuming that these parties receive the messages that were sent to them while being offline - features that are not available in the existing models of Sleepy MPC (Guo et al., CRYPTO '19), Fluid MPC (Choudhuri et al., CRYPTO '21 ) and YOSO (Gentry et al. CRYPTO '21). Phoenix does assume an upper bound on the number of rounds that an honest party can be off-line - otherwise protocols in this setting cannot guarantee termination within a bounded number of rounds; however, if one settles for a weaker notion, namely guaranteed output delivery only for honest parties who stay on-line long enough, this requirement is not necessary. In this work, we study the settings of perfect, statistical and computational security and design MPC protocols in each of these scenarios. We assume that the intersection of online-and-honest parties from one round to the next is at least 2t+1, t+1 and 1 respectively, where t is the number of (actively) corrupt parties. We show the intersection requirements to be optimal. Our (positive) results are obtained in a way that may be of independent interest: we implement a traditional stable network on top of the unstable one, which allows us to plug in any MPC protocol on top. This approach adds a necessary overhead to the round count of the protocols, which is related to the maximal number of rounds an honest party can be offline. We also present a novel, perfectly secure MPC protocol in the preprocessing model that avoids this overhead by following a more "direct" approach rather than first building a stable network and then using existing protocols. We introduce our network model in the UC-framework, show that the composition theorem still holds, and prove the security of our protocols within this setting.
Cite as

Ivan Damgård, Daniel Escudero, and Antigoni Polychroniadou. Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 7:1-7:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2023.7,
  author =	{Damg\r{a}rd, Ivan and Escudero, Daniel and Polychroniadou, Antigoni},
  title =	{{Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.7},
  URN =		{urn:nbn:de:0030-drops-183355},
  doi =		{10.4230/LIPIcs.ITC.2023.7},
  annote =	{Keywords: Secure Multiparty Computation, Unstable Networks}
}
Document
DOI: 10.4230/LIPIcs.ITC.2023.13
Secure Communication in Dynamic Incomplete Networks

Authors: Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
In this paper, we explore the feasibility of reliable and private communication in dynamic networks, where in each round the adversary can choose which direct peer-to-peer links are available in the network graph, under the sole condition that the graph is k-connected at each round (for some k). We show that reliable communication is possible in such a dynamic network if and only if k > 2t. We also show that if k = cn > 2 t for a constant c, we can achieve reliable communication with polynomial round and communication complexity. For unconditionally private communication, we show that for a passive adversary, k > t is sufficient (and clearly necessary). For an active adversary, we show that k > 2t is sufficient for statistical security (and clearly necessary), while k > 3t is sufficient for perfect security. We conjecture that, in contrast to the static case, k > 2t is not enough for perfect security, and we give evidence that the conjecture is true. Once we have reliable and private communication between each pair of parties, we can emulate a complete network with secure channels, and we can use known protocols to do secure computation.
Cite as

Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov. Secure Communication in Dynamic Incomplete Networks. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 13:1-13:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2023.13,
  author =	{Damg\r{a}rd, Ivan and Ravi, Divya and Tschudi, Daniel and Yakoubov, Sophia},
  title =	{{Secure Communication in Dynamic Incomplete Networks}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.13},
  URN =		{urn:nbn:de:0030-drops-183419},
  doi =		{10.4230/LIPIcs.ITC.2023.13},
  annote =	{Keywords: Secure Communication, Dynamic Incomplete Network, Information-theoretic}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.2
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.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}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.10
Broadcast Secret-Sharing, Bounds and Applications

Authors: Ivan Bjerre Damgård, Kasper Green Larsen, and Sophia Yakoubov

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

Abstract
Consider a sender 𝒮 and a group of n recipients. 𝒮 holds a secret message 𝗆 of length l bits and the goal is to allow 𝒮 to create a secret sharing of 𝗆 with privacy threshold t among the recipients, by broadcasting a single message 𝖼 to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset 𝒜 of recipients of size q, 𝒮 may share a random key with all recipients in 𝒜. (The keys shared with different subsets 𝒜 must be independent.) We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q. Our main question is: how large must 𝖼 be, as a function of the parameters? We show that (n-t)/q l is a lower bound, and we show an upper bound of ((n(t+1)/(q+t)) -t)l, matching the lower bound whenever t = 0, or when q = 1 or n-t. When q = n-t, the size of 𝖼 is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires 𝒮 to share a key with every subset of size n-t. We show that this overhead cannot be avoided when 𝖼 has minimal size. We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (n-t)/q λ + l - negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes ((n(t+1))/(q+t) -t)λ + l. BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.
Cite as

Ivan Bjerre Damgård, Kasper Green Larsen, and Sophia Yakoubov. Broadcast Secret-Sharing, Bounds and Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{damgard_et_al:LIPIcs.ITC.2021.10,
  author =	{Damg\r{a}rd, Ivan Bjerre and Larsen, Kasper Green and Yakoubov, Sophia},
  title =	{{Broadcast Secret-Sharing, Bounds and Applications}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{10:1--10:20},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.10},
  URN =		{urn:nbn:de:0030-drops-143299},
  doi =		{10.4230/LIPIcs.ITC.2021.10},
  annote =	{Keywords: Secret-Sharing, Ad-hoc Threshold Encryption}
}
  • Refine by Author
  • 2 Damgård, Ivan
  • 2 Damgård, Ivan Bjerre
  • 2 Yakoubov, Sophia
  • 1 Escudero, Daniel
  • 1 Larsen, Kasper Green
  • Show More...

  • Refine by Classification
  • 3 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 1 Ad-hoc Threshold Encryption
  • 1 Dynamic Incomplete Network
  • 1 Information-theoretic
  • 1 Lower bounds
  • 1 Multiparty Computation
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 2 2023

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact