How to Share a Secret, Infinitely View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-10-21

AUTHORS

Ilan Komargodski , Moni Naor , Eylon Yogev

ABSTRACT

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document} and there are n parties, there are schemes where the size of the share each party gets is roughly logn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log n$$\end{document} bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties n must be given in advance to the dealer.In this work we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the tth\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${t}^{th}$$\end{document} party arriving the smallest possible share as a function of t. Our main result is such a scheme for the k-threshold access structure where the share size of party t is (k-1)·logt+poly(k)·o(logt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k-1)\cdot \log t + \mathsf {poly}(k)\cdot o(\log t)$$\end{document}. For k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document} we observe an equivalence to prefix codes and present matching upper and lower bounds of the form logt+loglogt+logloglogt+O(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log t + \log \log t + \log \log \log t + O(1)$$\end{document}. Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size 2t-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{t-1}$$\end{document}. More... »

PAGES

485-514

Book

TITLE

Theory of Cryptography

ISBN

978-3-662-53643-8
978-3-662-53644-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53644-5_19

DOI

http://dx.doi.org/10.1007/978-3-662-53644-5_19

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1084895842


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/21", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "History and Archaeology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Historical Studies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Komargodski", 
        "givenName": "Ilan", 
        "id": "sg:person.012204235441.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yogev", 
        "givenName": "Eylon", 
        "id": "sg:person.015120037757.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-10-21", 
    "datePublishedReg": "2016-10-21", 
    "description": "Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k=2\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k=2$$\\end{document} and there are n parties, there are schemes where the size of the share each party gets is roughly logn\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\log n$$\\end{document} bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties n must be given in advance to the dealer.In this work we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the tth\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$${t}^{th}$$\\end{document} party arriving the smallest possible share as a function of t. Our main result is such a scheme for the k-threshold access structure where the share size of party t is (k-1)\u00b7logt+poly(k)\u00b7o(logt)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$(k-1)\\cdot \\log t + \\mathsf {poly}(k)\\cdot o(\\log t)$$\\end{document}. For k=2\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$k=2$$\\end{document} we observe an equivalence to prefix codes and present matching upper and lower bounds of the form logt+loglogt+logloglogt+O(1)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\log t + \\log \\log t + \\log \\log \\log t + O(1)$$\\end{document}. Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size 2t-1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{t-1}$$\\end{document}.", 
    "editor": [
      {
        "familyName": "Hirt", 
        "givenName": "Martin", 
        "type": "Person"
      }, 
      {
        "familyName": "Smith", 
        "givenName": "Adam", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53644-5_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53643-8", 
        "978-3-662-53644-5"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "structure", 
      "secret sharing scheme", 
      "scheme", 
      "threshold access structure", 
      "size", 
      "bits", 
      "sharing scheme", 
      "secret pieces", 
      "only qualified subsets", 
      "qualified subsets", 
      "secrets", 
      "access structure", 
      "example", 
      "parties n", 
      "advances", 
      "work", 
      "set of parties", 
      "set", 
      "function", 
      "main results", 
      "results", 
      "share size", 
      "equivalence", 
      "code", 
      "lower bounds", 
      "bounds", 
      "form", 
      "dealers", 
      "pieces", 
      "information", 
      "parties", 
      "subset", 
      "collection", 
      "share", 
      "number", 
      "cases", 
      "goal", 
      "possible share", 
      "smallest possible share"
    ], 
    "name": "How to Share a Secret, Infinitely", 
    "pagination": "485-514", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084895842"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53644-5_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53644-5_19", 
      "https://app.dimensions.ai/details/publication/pub.1084895842"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_27.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53644-5_19"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53644-5_19'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53644-5_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53644-5_19'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53644-5_19'


 

This table displays all metadata directly associated to this object as RDF triples.

118 TRIPLES      23 PREDICATES      64 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53644-5_19 schema:about anzsrc-for:21
2 anzsrc-for:2103
3 schema:author N500d304ea6af4c3ab7b71b3545b0094a
4 schema:datePublished 2016-10-21
5 schema:datePublishedReg 2016-10-21
6 schema:description Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document} and there are n parties, there are schemes where the size of the share each party gets is roughly logn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log n$$\end{document} bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties n must be given in advance to the dealer.In this work we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the tth\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${t}^{th}$$\end{document} party arriving the smallest possible share as a function of t. Our main result is such a scheme for the k-threshold access structure where the share size of party t is (k-1)·logt+poly(k)·o(logt)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k-1)\cdot \log t + \mathsf {poly}(k)\cdot o(\log t)$$\end{document}. For k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document} we observe an equivalence to prefix codes and present matching upper and lower bounds of the form logt+loglogt+logloglogt+O(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log t + \log \log t + \log \log \log t + O(1)$$\end{document}. Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size 2t-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{t-1}$$\end{document}.
7 schema:editor Ne601081e26ea4e71a69bc7e0f39721ff
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3a2d8e952172416fbb3e880e64b3d566
12 schema:keywords access structure
13 advances
14 bits
15 bounds
16 cases
17 code
18 collection
19 dealers
20 equivalence
21 example
22 form
23 function
24 goal
25 information
26 lower bounds
27 main results
28 number
29 only qualified subsets
30 parties
31 parties n
32 pieces
33 possible share
34 qualified subsets
35 results
36 scheme
37 secret pieces
38 secret sharing scheme
39 secrets
40 set
41 set of parties
42 share
43 share size
44 sharing scheme
45 size
46 smallest possible share
47 structure
48 subset
49 threshold access structure
50 work
51 schema:name How to Share a Secret, Infinitely
52 schema:pagination 485-514
53 schema:productId N28846c5a502d4f269940584e538e2e58
54 Nbe541b722bb042eb85aa951b1dd8ca73
55 schema:publisher Nea11bf3c9a00469b8bac6eca5848e653
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084895842
57 https://doi.org/10.1007/978-3-662-53644-5_19
58 schema:sdDatePublished 2022-05-20T07:44
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher Nc1530d5ed2314550a0416f24618fc897
61 schema:url https://doi.org/10.1007/978-3-662-53644-5_19
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N28846c5a502d4f269940584e538e2e58 schema:name doi
66 schema:value 10.1007/978-3-662-53644-5_19
67 rdf:type schema:PropertyValue
68 N2b83b7ef005f4f57ab7da9dfdfdec76a rdf:first N699b08e913a5438890571c8b4a2385ca
69 rdf:rest rdf:nil
70 N3a2d8e952172416fbb3e880e64b3d566 schema:isbn 978-3-662-53643-8
71 978-3-662-53644-5
72 schema:name Theory of Cryptography
73 rdf:type schema:Book
74 N4c9fcf5055054bb8b57b9110361dc53e rdf:first sg:person.015120037757.44
75 rdf:rest rdf:nil
76 N500d304ea6af4c3ab7b71b3545b0094a rdf:first sg:person.012204235441.12
77 rdf:rest Nd1ab9b76bc854625b80df6af36d5488a
78 N5881eeb186f540448c8c792fee068a2c schema:familyName Hirt
79 schema:givenName Martin
80 rdf:type schema:Person
81 N699b08e913a5438890571c8b4a2385ca schema:familyName Smith
82 schema:givenName Adam
83 rdf:type schema:Person
84 Nbe541b722bb042eb85aa951b1dd8ca73 schema:name dimensions_id
85 schema:value pub.1084895842
86 rdf:type schema:PropertyValue
87 Nc1530d5ed2314550a0416f24618fc897 schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Nd1ab9b76bc854625b80df6af36d5488a rdf:first sg:person.07776170271.83
90 rdf:rest N4c9fcf5055054bb8b57b9110361dc53e
91 Ne601081e26ea4e71a69bc7e0f39721ff rdf:first N5881eeb186f540448c8c792fee068a2c
92 rdf:rest N2b83b7ef005f4f57ab7da9dfdfdec76a
93 Nea11bf3c9a00469b8bac6eca5848e653 schema:name Springer Nature
94 rdf:type schema:Organisation
95 anzsrc-for:21 schema:inDefinedTermSet anzsrc-for:
96 schema:name History and Archaeology
97 rdf:type schema:DefinedTerm
98 anzsrc-for:2103 schema:inDefinedTermSet anzsrc-for:
99 schema:name Historical Studies
100 rdf:type schema:DefinedTerm
101 sg:person.012204235441.12 schema:affiliation grid-institutes:grid.13992.30
102 schema:familyName Komargodski
103 schema:givenName Ilan
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12
105 rdf:type schema:Person
106 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
107 schema:familyName Yogev
108 schema:givenName Eylon
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
110 rdf:type schema:Person
111 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
112 schema:familyName Naor
113 schema:givenName Moni
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
115 rdf:type schema:Person
116 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
117 schema:name Weizmann Institute of Science, Rehovot, Israel
118 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...