1 Search Results for "Strulovich, Omer"


Document
Lossy Chains and Fractional Secret Sharing

Authors: Yuval Ishai, Eyal Kushilevitz, and Omer Strulovich

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)


Abstract
Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f : 2^{[n]} -> {0,...,m-1} by guaranteeing that from the point of view of each set T \subseteq [n] of parties, the secret is uniformly distributed over a set of f(T) + 1 potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n,log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X_0,...,X_n) which starts with a random secret X_0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X_0 conditioned on the value of X_t should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate.

Cite as

Yuval Ishai, Eyal Kushilevitz, and Omer Strulovich. Lossy Chains and Fractional Secret Sharing. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 160-171, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{ishai_et_al:LIPIcs.STACS.2013.160,
  author =	{Ishai, Yuval and Kushilevitz, Eyal and Strulovich, Omer},
  title =	{{Lossy Chains and Fractional Secret Sharing}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{160--171},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.160},
  URN =		{urn:nbn:de:0030-drops-39319},
  doi =		{10.4230/LIPIcs.STACS.2013.160},
  annote =	{Keywords: Cryptography, secret sharing, Markov chains}
}
  • Refine by Author
  • 1 Ishai, Yuval
  • 1 Kushilevitz, Eyal
  • 1 Strulovich, Omer

  • Refine by Classification

  • Refine by Keyword
  • 1 Cryptography
  • 1 Markov chains
  • 1 secret sharing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

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