1 Search Results for "Halevi, Shai"

Weighted Secret Sharing from Wiretap Channels

Authors: Fabrice Benhamouda, Shai Halevi, and Lev Stambler

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

Secret-sharing allows splitting a piece of secret information among a group of shareholders, so that it takes a large enough subset of them to recover it. In weighted secret-sharing, each shareholder has an integer weight, and it takes a subset of large-enough weight to recover the secret. Schemes in the literature for weighted threshold secret sharing either have share sizes that grow linearly with the total weight, or ones that depend on huge public information (essentially a garbled circuit) of size (quasi)polynomial in the number of parties. To do better, we investigate a relaxation, (α, β)-ramp weighted secret sharing, where subsets of weight β W can recover the secret (with W the total weight), but subsets of weight α W or less cannot learn anything about it. These can be constructed from standard secret-sharing schemes, but known constructions require long shares even for short secrets, achieving share sizes of max(W,|secret|/ε), where ε = β-α. In this note we first observe that simple rounding let us replace the total weight W by N/ε, where N is the number of parties. Combined with known constructions, this yields share sizes of O(max(N,|secret|)/ε). Our main contribution is a novel connection between weighted secret sharing and wiretap channels, that improves or even eliminates the dependence on N, at a price of increased dependence on 1/ε. We observe that for certain additive-noise (ℛ,𝒜) wiretap channels, any semantically secure scheme can be naturally transformed into an (α,β)-ramp weighted secret-sharing, where α,β are essentially the respective capacities of the channels 𝒜,ℛ. We present two instantiations of this type of construction, one using Binary Symmetric wiretap Channels, and the other using additive Gaussian Wiretap Channels. Depending on the parameters of the underlying wiretap channels, this gives rise to (α, β)-ramp schemes with share sizes |secret|⋅log N/poly(ε) or even just |secret|/poly(ε).

Cite as

Fabrice Benhamouda, Shai Halevi, and Lev Stambler. Weighted Secret Sharing from Wiretap Channels. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 8:1-8:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

  author =	{Benhamouda, Fabrice and Halevi, Shai and Stambler, Lev},
  title =	{{Weighted Secret Sharing from Wiretap Channels}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-183365},
  doi =		{10.4230/LIPIcs.ITC.2023.8},
  annote =	{Keywords: Secret sharing, ramp weighted secret sharing, wiretap channel}
  • Refine by Author
  • 1 Benhamouda, Fabrice
  • 1 Halevi, Shai
  • 1 Stambler, Lev

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

  • Refine by Keyword
  • 1 Secret sharing
  • 1 ramp weighted secret sharing
  • 1 wiretap channel

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail