License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.64
URN: urn:nbn:de:0030-drops-96464
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9646/
Go to the corresponding LIPIcs Volume Portal

D'Arco, Paolo ; De Prisco, Roberto ; De Santis, Alfredo ; Pérez del Pozo, Angel ; Vaccaro, Ugo

Probabilistic Secret Sharing

pdf-format:
LIPIcs-MFCS-2018-64.pdf (0.5 MB)

Abstract

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

BibTeX - Entry

@InProceedings{darco_et_al:LIPIcs:2018:9646,
  author =	{Paolo D'Arco and Roberto De Prisco and Alfredo De Santis and Angel P{\'e}rez del Pozo and Ugo Vaccaro},
  title =	{{Probabilistic Secret Sharing}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9646},
  URN =		{urn:nbn:de:0030-drops-96464},
  doi =		{10.4230/LIPIcs.MFCS.2018.64},
  annote =	{Keywords: Secret sharing, probabilistic secret sharing, evolving secret sharing}
}

Keywords: Secret sharing, probabilistic secret sharing, evolving secret sharing
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI