Round Efficiency of Multi-party Computation with a Dishonest Majority View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003-05-13

AUTHORS

Jonathan Katz , Rafail Ostrovsky , Adam Smith

ABSTRACT

We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality and up to n − 1 of these players may be arbitrarily malicious. Previous protocols for this setting (when a broadcast channel is available) require O(n) rounds. We present two protocols with improved round complexity: The first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity O(log n) based on a proof scheduling technique of Chor and Rabin [[13]]; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak [[2]]) and achieves O(1) round complexity. More... »

PAGES

578-595

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-39200-9_36

DOI

http://dx.doi.org/10.1007/3-540-39200-9_36

DIMENSIONS

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


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, University of Maryland, College Park, MD", 
          "id": "http://www.grid.ac/institutes/grid.410443.6", 
          "name": [
            "Dept. of Computer Science, University of Maryland, College Park, MD"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Katz", 
        "givenName": "Jonathan", 
        "id": "sg:person.01354261156.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354261156.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Telcordia Technologies, Morristown, NJ", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Telcordia Technologies, Morristown, NJ"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ostrovsky", 
        "givenName": "Rafail", 
        "id": "sg:person.015474716573.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015474716573.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Lab. for Computer Science, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Lab. for Computer Science, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Smith", 
        "givenName": "Adam", 
        "id": "sg:person.013307226666.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-05-13", 
    "datePublishedReg": "2003-05-13", 
    "description": "We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality and up to n \u2212 1 of these players may be arbitrarily malicious. Previous protocols for this setting (when a broadcast channel is available) require O(n) rounds. We present two protocols with improved round complexity: The first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity O(log n) based on a proof scheduling technique of Chor and Rabin [[13]]; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak [[2]]) and achieves O(1) round complexity.", 
    "editor": [
      {
        "familyName": "Biham", 
        "givenName": "Eli", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-39200-9_36", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-14039-9", 
        "978-3-540-39200-2"
      ], 
      "name": "Advances in Cryptology \u2014 EUROCRYPT 2003", 
      "type": "Book"
    }, 
    "keywords": [
      "multi-party computation", 
      "round complexity", 
      "stronger hardness assumptions", 
      "static adversaries", 
      "dishonest majority", 
      "scheduling techniques", 
      "hardness assumption", 
      "trapdoor permutations", 
      "round efficiency", 
      "previous protocols", 
      "complexity", 
      "computation", 
      "cryptosystem", 
      "adversary", 
      "protocol", 
      "Chor", 
      "functionality", 
      "players", 
      "Rabin", 
      "permutations", 
      "technique", 
      "efficiency", 
      "parties", 
      "assumption", 
      "setting", 
      "majority", 
      "existence", 
      "presence"
    ], 
    "name": "Round Efficiency of Multi-party Computation with a Dishonest Majority", 
    "pagination": "578-595", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044875514"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-39200-9_36"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-39200-9_36", 
      "https://app.dimensions.ai/details/publication/pub.1044875514"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:29", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_213.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-39200-9_36"
  }
]
 

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/3-540-39200-9_36'

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/3-540-39200-9_36'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-39200-9_36'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-39200-9_36'


 

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

108 TRIPLES      23 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-39200-9_36 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N63d17677d2534437b41bcec4aedc7e4b
4 schema:datePublished 2003-05-13
5 schema:datePublishedReg 2003-05-13
6 schema:description We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality and up to n − 1 of these players may be arbitrarily malicious. Previous protocols for this setting (when a broadcast channel is available) require O(n) rounds. We present two protocols with improved round complexity: The first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity O(log n) based on a proof scheduling technique of Chor and Rabin [[13]]; the second requires a stronger hardness assumption (along with the non-black-box techniques of Barak [[2]]) and achieves O(1) round complexity.
7 schema:editor N6fd9819235df4b0a805067f19a0f1d75
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na4c64d84a8e945f7b42da614f24955ae
12 schema:keywords Chor
13 Rabin
14 adversary
15 assumption
16 complexity
17 computation
18 cryptosystem
19 dishonest majority
20 efficiency
21 existence
22 functionality
23 hardness assumption
24 majority
25 multi-party computation
26 parties
27 permutations
28 players
29 presence
30 previous protocols
31 protocol
32 round complexity
33 round efficiency
34 scheduling techniques
35 setting
36 static adversaries
37 stronger hardness assumptions
38 technique
39 trapdoor permutations
40 schema:name Round Efficiency of Multi-party Computation with a Dishonest Majority
41 schema:pagination 578-595
42 schema:productId N917bcd73272c499eb840ab1c016e1bd8
43 Nf63457f27c364687b90f8b93db964367
44 schema:publisher N61f1ad505ded4815932dc9ce2b69941f
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044875514
46 https://doi.org/10.1007/3-540-39200-9_36
47 schema:sdDatePublished 2022-06-01T22:29
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher Nf97a07efae8d444381b2609eb14b05c1
50 schema:url https://doi.org/10.1007/3-540-39200-9_36
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N0cdd2f0dd1734246a3c7a819c1451a06 schema:familyName Biham
55 schema:givenName Eli
56 rdf:type schema:Person
57 N61f1ad505ded4815932dc9ce2b69941f schema:name Springer Nature
58 rdf:type schema:Organisation
59 N63d17677d2534437b41bcec4aedc7e4b rdf:first sg:person.01354261156.67
60 rdf:rest Ncf3431ce1bc94aba9e43c08e4b098911
61 N6fd9819235df4b0a805067f19a0f1d75 rdf:first N0cdd2f0dd1734246a3c7a819c1451a06
62 rdf:rest rdf:nil
63 N917bcd73272c499eb840ab1c016e1bd8 schema:name dimensions_id
64 schema:value pub.1044875514
65 rdf:type schema:PropertyValue
66 Na4c64d84a8e945f7b42da614f24955ae schema:isbn 978-3-540-14039-9
67 978-3-540-39200-2
68 schema:name Advances in Cryptology — EUROCRYPT 2003
69 rdf:type schema:Book
70 Nb831793fe9654f57b551bf2920d4c374 rdf:first sg:person.013307226666.21
71 rdf:rest rdf:nil
72 Ncf3431ce1bc94aba9e43c08e4b098911 rdf:first sg:person.015474716573.95
73 rdf:rest Nb831793fe9654f57b551bf2920d4c374
74 Nf63457f27c364687b90f8b93db964367 schema:name doi
75 schema:value 10.1007/3-540-39200-9_36
76 rdf:type schema:PropertyValue
77 Nf97a07efae8d444381b2609eb14b05c1 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
83 schema:name Computation Theory and Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.116068.8
86 schema:familyName Smith
87 schema:givenName Adam
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
89 rdf:type schema:Person
90 sg:person.01354261156.67 schema:affiliation grid-institutes:grid.410443.6
91 schema:familyName Katz
92 schema:givenName Jonathan
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354261156.67
94 rdf:type schema:Person
95 sg:person.015474716573.95 schema:affiliation grid-institutes:grid.432790.b
96 schema:familyName Ostrovsky
97 schema:givenName Rafail
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015474716573.95
99 rdf:type schema:Person
100 grid-institutes:grid.116068.8 schema:alternateName MIT Lab. for Computer Science, Cambridge, MA
101 schema:name MIT Lab. for Computer Science, Cambridge, MA
102 rdf:type schema:Organization
103 grid-institutes:grid.410443.6 schema:alternateName Dept. of Computer Science, University of Maryland, College Park, MD
104 schema:name Dept. of Computer Science, University of Maryland, College Park, MD
105 rdf:type schema:Organization
106 grid-institutes:grid.432790.b schema:alternateName Telcordia Technologies, Morristown, NJ
107 schema:name Telcordia Technologies, Morristown, NJ
108 rdf:type schema:Organization
 




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


...