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", 
    "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 assumption", 
      "static adversaries", 
      "dishonest majority", 
      "scheduling techniques", 
      "hardness assumptions", 
      "trapdoor permutations", 
      "round efficiency", 
      "previous protocols", 
      "complexity", 
      "n players", 
      "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-08-04T17:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_191.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      22 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 Na952a48deec84894822bbf0ccd92f3db
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 N521c07c5049e4944962f58ccc4b4e042
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N333c7cb47f0544978b5644711dd6e842
11 schema:keywords Chor
12 Rabin
13 adversary
14 assumption
15 complexity
16 computation
17 cryptosystem
18 dishonest majority
19 efficiency
20 existence
21 functionality
22 hardness assumptions
23 majority
24 multi-party computation
25 n players
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 assumption
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 N3f668d039b8d432bad8724be51e840c3
43 Nd005ebfd9efd4c4ea43964fe41bc7be9
44 schema:publisher Nbeaee0753d874a2cb1bf86874b46e3bf
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-08-04T17:15
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N30684569e07a454097801808152b5b3b
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 N30684569e07a454097801808152b5b3b schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N333c7cb47f0544978b5644711dd6e842 schema:isbn 978-3-540-14039-9
57 978-3-540-39200-2
58 schema:name Advances in Cryptology — EUROCRYPT 2003
59 rdf:type schema:Book
60 N3f668d039b8d432bad8724be51e840c3 schema:name doi
61 schema:value 10.1007/3-540-39200-9_36
62 rdf:type schema:PropertyValue
63 N521c07c5049e4944962f58ccc4b4e042 rdf:first N808af292b9b9403ba2eec3ea4779b3fd
64 rdf:rest rdf:nil
65 N808af292b9b9403ba2eec3ea4779b3fd schema:familyName Biham
66 schema:givenName Eli
67 rdf:type schema:Person
68 Na952a48deec84894822bbf0ccd92f3db rdf:first sg:person.01354261156.67
69 rdf:rest Nb30f14608203403d86d80e7a3c42c785
70 Nb30f14608203403d86d80e7a3c42c785 rdf:first sg:person.015474716573.95
71 rdf:rest Ndc448bd672d64240ad5555d0e0d592ba
72 Nbeaee0753d874a2cb1bf86874b46e3bf schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nd005ebfd9efd4c4ea43964fe41bc7be9 schema:name dimensions_id
75 schema:value pub.1044875514
76 rdf:type schema:PropertyValue
77 Ndc448bd672d64240ad5555d0e0d592ba rdf:first sg:person.013307226666.21
78 rdf:rest rdf:nil
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)


...