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": [
      "parties", 
      "dealers", 
      "secrets", 
      "pieces", 
      "collection", 
      "example", 
      "share", 
      "work", 
      "form", 
      "secret sharing scheme", 
      "sharing scheme", 
      "scheme", 
      "structure", 
      "bits", 
      "advances", 
      "cases", 
      "goal", 
      "information", 
      "qualified subsets", 
      "access structure", 
      "threshold access structure", 
      "size", 
      "number", 
      "parties n", 
      "set", 
      "results", 
      "code", 
      "lower bounds", 
      "bounds", 
      "secret pieces", 
      "only qualified subsets", 
      "subset", 
      "set of parties", 
      "possible share", 
      "function", 
      "main results", 
      "share size", 
      "equivalence", 
      "shares of size", 
      "smallest possible share", 
      "party t"
    ], 
    "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-01-01T19:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_159.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.

120 TRIPLES      23 PREDICATES      66 URIs      59 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 Nc22a3e66cd3245039d964ebc57222264
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 N74f8ee319a1d4c188d1fa169ac5daf62
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N25dff4c5f472456fbcd37dd05d8cd911
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 party t
33 pieces
34 possible share
35 qualified subsets
36 results
37 scheme
38 secret pieces
39 secret sharing scheme
40 secrets
41 set
42 set of parties
43 share
44 share size
45 shares of size
46 sharing scheme
47 size
48 smallest possible share
49 structure
50 subset
51 threshold access structure
52 work
53 schema:name How to Share a Secret, Infinitely
54 schema:pagination 485-514
55 schema:productId N73fe4bbcdd11423494014bc52878bb94
56 Nfc49e214166047f39a47a0c8bd5507bf
57 schema:publisher N9032e96a934b4dde90e4dd02c3fb2714
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084895842
59 https://doi.org/10.1007/978-3-662-53644-5_19
60 schema:sdDatePublished 2022-01-01T19:09
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N97c77ab744d94efb83cf9e0776934bc2
63 schema:url https://doi.org/10.1007/978-3-662-53644-5_19
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N15111280c4254cd38ccf91b71d192257 schema:familyName Hirt
68 schema:givenName Martin
69 rdf:type schema:Person
70 N16bf864352f8489b823e86a6fd8c5dbd schema:familyName Smith
71 schema:givenName Adam
72 rdf:type schema:Person
73 N25dff4c5f472456fbcd37dd05d8cd911 schema:isbn 978-3-662-53643-8
74 978-3-662-53644-5
75 schema:name Theory of Cryptography
76 rdf:type schema:Book
77 N264ccb08fd134c009a0f7fde76352e70 rdf:first sg:person.07776170271.83
78 rdf:rest Ne10755f144504fd29083e41b7d7241e9
79 N73fe4bbcdd11423494014bc52878bb94 schema:name dimensions_id
80 schema:value pub.1084895842
81 rdf:type schema:PropertyValue
82 N74f8ee319a1d4c188d1fa169ac5daf62 rdf:first N15111280c4254cd38ccf91b71d192257
83 rdf:rest Nfdcbb29968a54a79b8798fec6036c594
84 N9032e96a934b4dde90e4dd02c3fb2714 schema:name Springer Nature
85 rdf:type schema:Organisation
86 N97c77ab744d94efb83cf9e0776934bc2 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nc22a3e66cd3245039d964ebc57222264 rdf:first sg:person.012204235441.12
89 rdf:rest N264ccb08fd134c009a0f7fde76352e70
90 Ne10755f144504fd29083e41b7d7241e9 rdf:first sg:person.015120037757.44
91 rdf:rest rdf:nil
92 Nfc49e214166047f39a47a0c8bd5507bf schema:name doi
93 schema:value 10.1007/978-3-662-53644-5_19
94 rdf:type schema:PropertyValue
95 Nfdcbb29968a54a79b8798fec6036c594 rdf:first N16bf864352f8489b823e86a6fd8c5dbd
96 rdf:rest rdf:nil
97 anzsrc-for:21 schema:inDefinedTermSet anzsrc-for:
98 schema:name History and Archaeology
99 rdf:type schema:DefinedTerm
100 anzsrc-for:2103 schema:inDefinedTermSet anzsrc-for:
101 schema:name Historical Studies
102 rdf:type schema:DefinedTerm
103 sg:person.012204235441.12 schema:affiliation grid-institutes:grid.13992.30
104 schema:familyName Komargodski
105 schema:givenName Ilan
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12
107 rdf:type schema:Person
108 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
109 schema:familyName Yogev
110 schema:givenName Eylon
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
112 rdf:type schema:Person
113 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
114 schema:familyName Naor
115 schema:givenName Moni
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
117 rdf:type schema:Person
118 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
119 schema:name Weizmann Institute of Science, Rehovot, Israel
120 rdf:type schema:Organization
 




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


...