The Round Complexity of Verifiable Secret Sharing Revisited View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Arpita Patra , Ashish Choudhary , Tal Rabin , C. Pandu Rangan

ABSTRACT

The round complexity of interactive protocols is one of their most important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of three rounds for VSS, with n = 3t + 1, where the reconstruction of the secrets always succeeds, i.e. with probability 1. In contrast we show that with a negligible probability of error in the reconstruction phase:There exists an efficient 2-round VSS protocol for n = 3t + 1. If we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase.There exists an efficient 1-round VSS for t = 1 and n > 3.We prove that our results are optimal both in resilience and number of sharing rounds by showing:There does not exist a 2-round WSS (and hence VSS) for n ≤ 3t.There does not exist a 1-round VSS protocol for t ≥ 2 and n ≥ 4. More... »

PAGES

487-504

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03356-8_29

DOI

http://dx.doi.org/10.1007/978-3-642-03356-8_29

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India", 
          "id": "http://www.grid.ac/institutes/grid.417969.4", 
          "name": [
            "Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patra", 
        "givenName": "Arpita", 
        "id": "sg:person.016570701367.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016570701367.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India", 
          "id": "http://www.grid.ac/institutes/grid.417969.4", 
          "name": [
            "Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Choudhary", 
        "givenName": "Ashish", 
        "id": "sg:person.014341113651.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014341113651.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "id": "sg:person.015473523512.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India", 
          "id": "http://www.grid.ac/institutes/grid.417969.4", 
          "name": [
            "Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rangan", 
        "givenName": "C. Pandu", 
        "id": "sg:person.016366027737.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "The round complexity of interactive protocols is one of their most important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of three rounds for VSS, with n\u2009=\u20093t\u2009+\u20091, where the reconstruction of the secrets always succeeds, i.e. with probability 1. In contrast we show that with a negligible probability of error in the reconstruction phase:There exists an efficient 2-round VSS protocol for n\u2009=\u20093t\u2009+\u20091. If we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase.There exists an efficient 1-round VSS for t\u2009=\u20091 and n\u2009>\u20093.We prove that our results are optimal both in resilience and number of sharing rounds by showing:There does not exist a 2-round WSS (and hence VSS) for n\u2009\u2264\u20093t.There does not exist a 1-round VSS protocol for t\u2009\u2265\u20092 and n\u2009\u2265\u20094.", 
    "editor": [
      {
        "familyName": "Halevi", 
        "givenName": "Shai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-03356-8_29", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-03355-1", 
        "978-3-642-03356-8"
      ], 
      "name": "Advances in Cryptology - CRYPTO 2009", 
      "type": "Book"
    }, 
    "keywords": [
      "round complexity", 
      "VSS protocol", 
      "reconstruction phase", 
      "verifiable secret sharing", 
      "negligible probability", 
      "interactive protocol", 
      "secret sharing", 
      "complexity measures", 
      "important complexity measures", 
      "complexity", 
      "lower bounds", 
      "protocol", 
      "upper bounds", 
      "adversary", 
      "sharing", 
      "probability 1", 
      "bounds", 
      "error", 
      "secrets", 
      "probability", 
      "rounds", 
      "reconstruction", 
      "work", 
      "results", 
      "resilience", 
      "number", 
      "VSS", 
      "previous results", 
      "WSS", 
      "measures", 
      "phase", 
      "contrast", 
      "Vs"
    ], 
    "name": "The Round Complexity of Verifiable Secret Sharing Revisited", 
    "pagination": "487-504", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002582525"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-03356-8_29"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-03356-8_29", 
      "https://app.dimensions.ai/details/publication/pub.1002582525"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "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_352.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-03356-8_29"
  }
]
 

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-642-03356-8_29'

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-642-03356-8_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03356-8_29'

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-642-03356-8_29'


 

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

117 TRIPLES      23 PREDICATES      59 URIs      52 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-03356-8_29 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N54aae6b4d6ea45dab5a3143977a3b1e8
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description The round complexity of interactive protocols is one of their most important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of three rounds for VSS, with n = 3t + 1, where the reconstruction of the secrets always succeeds, i.e. with probability 1. In contrast we show that with a negligible probability of error in the reconstruction phase:There exists an efficient 2-round VSS protocol for n = 3t + 1. If we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase.There exists an efficient 1-round VSS for t = 1 and n > 3.We prove that our results are optimal both in resilience and number of sharing rounds by showing:There does not exist a 2-round WSS (and hence VSS) for n ≤ 3t.There does not exist a 1-round VSS protocol for t ≥ 2 and n ≥ 4.
7 schema:editor N9b5dc0f7ea2a46a3a741b915c78e4b56
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N8d945a7358ea411586b21343975d2eb8
12 schema:keywords VSS
13 VSS protocol
14 Vs
15 WSS
16 adversary
17 bounds
18 complexity
19 complexity measures
20 contrast
21 error
22 important complexity measures
23 interactive protocol
24 lower bounds
25 measures
26 negligible probability
27 number
28 phase
29 previous results
30 probability
31 probability 1
32 protocol
33 reconstruction
34 reconstruction phase
35 resilience
36 results
37 round complexity
38 rounds
39 secret sharing
40 secrets
41 sharing
42 upper bounds
43 verifiable secret sharing
44 work
45 schema:name The Round Complexity of Verifiable Secret Sharing Revisited
46 schema:pagination 487-504
47 schema:productId N7ea124b809d64f21bf497bb862d25853
48 Nbdaea12250db4abebe930a6c1550bdfa
49 schema:publisher N415283b4d32d45399a020da27c7ed27b
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002582525
51 https://doi.org/10.1007/978-3-642-03356-8_29
52 schema:sdDatePublished 2022-05-20T07:46
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N7774eb68ec814b21a2735a2253507716
55 schema:url https://doi.org/10.1007/978-3-642-03356-8_29
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N354f8c7617d2484e886e890c07bf9496 rdf:first sg:person.015473523512.58
60 rdf:rest N9ca100ac516b483e8aad0475be5f0a10
61 N415283b4d32d45399a020da27c7ed27b schema:name Springer Nature
62 rdf:type schema:Organisation
63 N54aae6b4d6ea45dab5a3143977a3b1e8 rdf:first sg:person.016570701367.19
64 rdf:rest N73fa1e3b971f41b39ee2e334f4fd0f2e
65 N73fa1e3b971f41b39ee2e334f4fd0f2e rdf:first sg:person.014341113651.28
66 rdf:rest N354f8c7617d2484e886e890c07bf9496
67 N7774eb68ec814b21a2735a2253507716 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N7ea124b809d64f21bf497bb862d25853 schema:name dimensions_id
70 schema:value pub.1002582525
71 rdf:type schema:PropertyValue
72 N8d945a7358ea411586b21343975d2eb8 schema:isbn 978-3-642-03355-1
73 978-3-642-03356-8
74 schema:name Advances in Cryptology - CRYPTO 2009
75 rdf:type schema:Book
76 N9b5dc0f7ea2a46a3a741b915c78e4b56 rdf:first Nc298ff3b6cef471582f886c7a4e1d0b2
77 rdf:rest rdf:nil
78 N9ca100ac516b483e8aad0475be5f0a10 rdf:first sg:person.016366027737.61
79 rdf:rest rdf:nil
80 Nbdaea12250db4abebe930a6c1550bdfa schema:name doi
81 schema:value 10.1007/978-3-642-03356-8_29
82 rdf:type schema:PropertyValue
83 Nc298ff3b6cef471582f886c7a4e1d0b2 schema:familyName Halevi
84 schema:givenName Shai
85 rdf:type schema:Person
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.014341113651.28 schema:affiliation grid-institutes:grid.417969.4
93 schema:familyName Choudhary
94 schema:givenName Ashish
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014341113651.28
96 rdf:type schema:Person
97 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
98 schema:familyName Rabin
99 schema:givenName Tal
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
101 rdf:type schema:Person
102 sg:person.016366027737.61 schema:affiliation grid-institutes:grid.417969.4
103 schema:familyName Rangan
104 schema:givenName C. Pandu
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016366027737.61
106 rdf:type schema:Person
107 sg:person.016570701367.19 schema:affiliation grid-institutes:grid.417969.4
108 schema:familyName Patra
109 schema:givenName Arpita
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016570701367.19
111 rdf:type schema:Person
112 grid-institutes:grid.417969.4 schema:alternateName Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India
113 schema:name Dept of Computer Science and Engineering, IIT Madras, 600036, Chennai, India
114 rdf:type schema:Organization
115 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, USA
116 schema:name IBM T.J. Watson Research Center, USA
117 rdf:type schema:Organization
 




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


...