On 2-Round Secure Multiparty Computation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-09-13

AUTHORS

Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin

ABSTRACT

Substantial efforts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the presence of an active (Byzantine) adversary, assuming the availability of secure point-to-point channels and a broadcast primitive. It was recently shown that in this setting three rounds are sufficient for arbitrary secure computation tasks, with a linear security threshold, and two rounds are sufficient for certain nontrivial tasks. This leaves open the question whether every function can be securely computed in two rounds. We show that the answer to this question is “no”: even some very simple functions do not admit secure 2-round protocols (independently of their communication and time complexity) and thus 3 is the exact round complexity of general secure multiparty computation. Yet, we also present some positive results by identifying a useful class of functions which can be securely computed in two rounds. Our results apply both to the information-theoretic and to the computational notions of security. More... »

PAGES

178-193

Book

TITLE

Advances in Cryptology — CRYPTO 2002

ISBN

978-3-540-44050-5
978-3-540-45708-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45708-9_12

DOI

http://dx.doi.org/10.1007/3-540-45708-9_12

DIMENSIONS

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


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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "T.J. Watson Research Center, IBM, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "T.J. Watson Research Center, IBM, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gennaro", 
        "givenName": "Rosario", 
        "id": "sg:person.013573255563.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013573255563.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Princeton University, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Princeton University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ishai", 
        "givenName": "Yuval", 
        "id": "sg:person.010434442160.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010434442160.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technion, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Technion, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kushilevitz", 
        "givenName": "Eyal", 
        "id": "sg:person.013624731540.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624731540.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "T.J. Watson Research Center, IBM, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "T.J. Watson Research Center, IBM, 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"
      }
    ], 
    "datePublished": "2002-09-13", 
    "datePublishedReg": "2002-09-13", 
    "description": "Substantial efforts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the presence of an active (Byzantine) adversary, assuming the availability of secure point-to-point channels and a broadcast primitive. It was recently shown that in this setting three rounds are sufficient for arbitrary secure computation tasks, with a linear security threshold, and two rounds are sufficient for certain nontrivial tasks. This leaves open the question whether every function can be securely computed in two rounds. We show that the answer to this question is \u201cno\u201d: even some very simple functions do not admit secure 2-round protocols (independently of their communication and time complexity) and thus 3 is the exact round complexity of general secure multiparty computation. Yet, we also present some positive results by identifying a useful class of functions which can be securely computed in two rounds. Our results apply both to the information-theoretic and to the computational notions of security.", 
    "editor": [
      {
        "familyName": "Yung", 
        "givenName": "Moti", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45708-9_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-44050-5", 
        "978-3-540-45708-4"
      ], 
      "name": "Advances in Cryptology \u2014 CRYPTO 2002", 
      "type": "Book"
    }, 
    "keywords": [
      "secure multiparty computation", 
      "multiparty computation", 
      "round complexity", 
      "general secure multiparty computation", 
      "exact round complexity", 
      "computation tasks", 
      "active adversary", 
      "cryptographic tasks", 
      "computational notion", 
      "secure point", 
      "broadcast primitive", 
      "security threshold", 
      "nontrivial task", 
      "point channels", 
      "computation", 
      "task", 
      "complexity", 
      "useful class", 
      "adversary", 
      "primitives", 
      "substantial effort", 
      "security", 
      "simple function", 
      "protocol", 
      "rounds", 
      "answers", 
      "work", 
      "availability", 
      "efforts", 
      "results", 
      "notion", 
      "channels", 
      "class", 
      "function", 
      "point", 
      "questions", 
      "threshold", 
      "positive results", 
      "presence"
    ], 
    "name": "On 2-Round Secure Multiparty Computation", 
    "pagination": "178-193", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010608654"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45708-9_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45708-9_12", 
      "https://app.dimensions.ai/details/publication/pub.1010608654"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:39", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_168.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45708-9_12"
  }
]
 

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-45708-9_12'

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-45708-9_12'

Turtle is a human-readable linked data format.

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

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-45708-9_12'


 

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

130 TRIPLES      23 PREDICATES      65 URIs      57 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45708-9_12 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author N83ca2d9b30984a5a85e712777ab509a3
5 schema:datePublished 2002-09-13
6 schema:datePublishedReg 2002-09-13
7 schema:description Substantial efforts have been spent on characterizing the round complexity of various cryptographic tasks. In this work we study the round complexity of secure multiparty computation in the presence of an active (Byzantine) adversary, assuming the availability of secure point-to-point channels and a broadcast primitive. It was recently shown that in this setting three rounds are sufficient for arbitrary secure computation tasks, with a linear security threshold, and two rounds are sufficient for certain nontrivial tasks. This leaves open the question whether every function can be securely computed in two rounds. We show that the answer to this question is “no”: even some very simple functions do not admit secure 2-round protocols (independently of their communication and time complexity) and thus 3 is the exact round complexity of general secure multiparty computation. Yet, we also present some positive results by identifying a useful class of functions which can be securely computed in two rounds. Our results apply both to the information-theoretic and to the computational notions of security.
8 schema:editor Na419f66b8ab945bc835b8e50682bb58d
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf N14064176acd14413a848f7767c295dc6
13 schema:keywords active adversary
14 adversary
15 answers
16 availability
17 broadcast primitive
18 channels
19 class
20 complexity
21 computation
22 computation tasks
23 computational notion
24 cryptographic tasks
25 efforts
26 exact round complexity
27 function
28 general secure multiparty computation
29 multiparty computation
30 nontrivial task
31 notion
32 point
33 point channels
34 positive results
35 presence
36 primitives
37 protocol
38 questions
39 results
40 round complexity
41 rounds
42 secure multiparty computation
43 secure point
44 security
45 security threshold
46 simple function
47 substantial effort
48 task
49 threshold
50 useful class
51 work
52 schema:name On 2-Round Secure Multiparty Computation
53 schema:pagination 178-193
54 schema:productId N73dbff23c6754f1bb7503a84ae920b9e
55 Nab0fa368a5454539a7697a53d55f104e
56 schema:publisher N103925b88d02400cb697538b26d2d95b
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010608654
58 https://doi.org/10.1007/3-540-45708-9_12
59 schema:sdDatePublished 2022-05-10T10:39
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher Nce18c9aa57bc46c7974405aeec7ad789
62 schema:url https://doi.org/10.1007/3-540-45708-9_12
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N02f20b35679745b3b0084020b1e03dfc rdf:first sg:person.015473523512.58
67 rdf:rest rdf:nil
68 N103925b88d02400cb697538b26d2d95b schema:name Springer Nature
69 rdf:type schema:Organisation
70 N14064176acd14413a848f7767c295dc6 schema:isbn 978-3-540-44050-5
71 978-3-540-45708-4
72 schema:name Advances in Cryptology — CRYPTO 2002
73 rdf:type schema:Book
74 N5efa6911376e48fb98e969b8a96b7649 schema:familyName Yung
75 schema:givenName Moti
76 rdf:type schema:Person
77 N73dbff23c6754f1bb7503a84ae920b9e schema:name doi
78 schema:value 10.1007/3-540-45708-9_12
79 rdf:type schema:PropertyValue
80 N7eab7994978e42f693d2acd251d1867a rdf:first sg:person.010434442160.49
81 rdf:rest Ne03c2ffc5b7a4454afff3636af48dea7
82 N83ca2d9b30984a5a85e712777ab509a3 rdf:first sg:person.013573255563.35
83 rdf:rest N7eab7994978e42f693d2acd251d1867a
84 Na419f66b8ab945bc835b8e50682bb58d rdf:first N5efa6911376e48fb98e969b8a96b7649
85 rdf:rest rdf:nil
86 Nab0fa368a5454539a7697a53d55f104e schema:name dimensions_id
87 schema:value pub.1010608654
88 rdf:type schema:PropertyValue
89 Nce18c9aa57bc46c7974405aeec7ad789 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Ne03c2ffc5b7a4454afff3636af48dea7 rdf:first sg:person.013624731540.48
92 rdf:rest N02f20b35679745b3b0084020b1e03dfc
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
97 schema:name Computation Theory and Mathematics
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
100 schema:name Data Format
101 rdf:type schema:DefinedTerm
102 sg:person.010434442160.49 schema:affiliation grid-institutes:grid.16750.35
103 schema:familyName Ishai
104 schema:givenName Yuval
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010434442160.49
106 rdf:type schema:Person
107 sg:person.013573255563.35 schema:affiliation grid-institutes:grid.481554.9
108 schema:familyName Gennaro
109 schema:givenName Rosario
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013573255563.35
111 rdf:type schema:Person
112 sg:person.013624731540.48 schema:affiliation grid-institutes:grid.6451.6
113 schema:familyName Kushilevitz
114 schema:givenName Eyal
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624731540.48
116 rdf:type schema:Person
117 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
118 schema:familyName Rabin
119 schema:givenName Tal
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
121 rdf:type schema:Person
122 grid-institutes:grid.16750.35 schema:alternateName Princeton University, USA
123 schema:name Princeton University, USA
124 rdf:type schema:Organization
125 grid-institutes:grid.481554.9 schema:alternateName T.J. Watson Research Center, IBM, USA
126 schema:name T.J. Watson Research Center, IBM, USA
127 rdf:type schema:Organization
128 grid-institutes:grid.6451.6 schema:alternateName Technion, Israel
129 schema:name Technion, Israel
130 rdf:type schema:Organization
 




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


...