Network-Hiding Communication and Applications to Multi-party Protocols View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-07-21

AUTHORS

Martin Hirt , Ueli Maurer , Daniel Tschudi , Vassilis Zikas

ABSTRACT

As distributed networks are heavily used in modern applications, new security challenges emerge. In a multi-party computation (in short, MPC) protocol over an incomplete network, such a challenge is to hide, to the extent possible, the topology of the underlying communication network. Such a topology-hiding (aka network hiding) property is in fact very relevant in applications where anonymity is needed.To our knowledge, with the exception of two recent works by Chandran et al. [ITCS 2015] and by Moran et al. [TCC 2015], existing MPC protocols do not hide the topology of the underlying communication network. Moreover, the above two solutions are either not applicable to arbitrary networks (as is [ITCS 2015]) or, as in [TCC 2015], they make non-black-box and recursive use of cryptographic primitives resulting in an unrealistic communication and computation complexity even for simple, i.e., low degree and diameter, networks.Our work suggests the first topology-hiding communication protocol for incomplete networks which makes black-box use of the underlying cryptographic assumption—in particular, a public-key encryption scheme—and tolerates any adversary who passively corrupts arbitrarily many network nodes. Our solutions are based on a new, enhanced variant of threshold homomorphic encryption, in short, TH-PKE, that requires no a-priori setup and allows to circulate an encrypted message over any (unknown) incomplete network and then decrypt it without revealing any network information to intermediate nodes. We show how to realize this enhanced TH-PKE from the DDH assumption. The black-box nature of our scheme, along with some optimization tricks that we employ, makes our communication protocol more efficient than existing solutions.We then use our communication protocol to make any semi-honest secure MPC protocol topology-hiding with a reasonable—i.e., for simple networks, polynomial with small constants—communication and computation overhead. We further show how to construct anonymous broadcast without using expensive MPCs to setup the original pseudonyms. More... »

PAGES

335-365

Book

TITLE

Advances in Cryptology – CRYPTO 2016

ISBN

978-3-662-53007-8
978-3-662-53008-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53008-5_12

DOI

http://dx.doi.org/10.1007/978-3-662-53008-5_12

DIMENSIONS

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


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": "ETH Zurich, Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Zurich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hirt", 
        "givenName": "Martin", 
        "id": "sg:person.010611500757.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010611500757.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ETH Zurich, Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Zurich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maurer", 
        "givenName": "Ueli", 
        "id": "sg:person.01316567627.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ETH Zurich, Z\u00fcrich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Zurich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tschudi", 
        "givenName": "Daniel", 
        "id": "sg:person.011112577475.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011112577475.84"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "RPI, Troy, USA", 
          "id": "http://www.grid.ac/institutes/grid.33647.35", 
          "name": [
            "RPI, Troy, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zikas", 
        "givenName": "Vassilis", 
        "id": "sg:person.012007513121.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012007513121.08"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-07-21", 
    "datePublishedReg": "2016-07-21", 
    "description": "As distributed networks are heavily used in modern applications, new security challenges emerge. In a multi-party computation (in short, MPC) protocol over an incomplete network, such a challenge is to hide, to the extent possible, the topology of the underlying communication network. Such a topology-hiding (aka network hiding) property is in fact very relevant in applications where anonymity is needed.To our knowledge, with the exception of two recent works by Chandran et al. [ITCS\u00a02015] and by Moran et al. [TCC\u00a02015], existing MPC protocols do not hide the topology of the underlying communication network. Moreover, the above two solutions are either not applicable to arbitrary networks (as is [ITCS\u00a02015]) or, as in [TCC\u00a02015], they make non-black-box and recursive use of cryptographic primitives resulting in an unrealistic communication and computation complexity even for simple, i.e., low degree and diameter, networks.Our work suggests the first topology-hiding communication protocol for incomplete networks which makes black-box use of the underlying cryptographic assumption\u2014in particular, a public-key encryption scheme\u2014and tolerates any adversary who passively corrupts arbitrarily many network nodes. Our solutions are based on a new, enhanced variant of threshold homomorphic encryption, in short, TH-PKE, that requires no a-priori setup and allows to circulate an encrypted message over any (unknown) incomplete network and then decrypt it without revealing any network information to intermediate nodes. We show how to realize this enhanced TH-PKE from the DDH assumption. The black-box nature of our scheme, along with some optimization tricks that we employ, makes our communication protocol more efficient than existing solutions.We then use our communication protocol to make any semi-honest secure MPC protocol topology-hiding with a reasonable\u2014i.e., for simple networks, polynomial with small constants\u2014communication and computation overhead. We further show how to construct anonymous broadcast without using expensive MPCs to setup the original pseudonyms.", 
    "editor": [
      {
        "familyName": "Robshaw", 
        "givenName": "Matthew", 
        "type": "Person"
      }, 
      {
        "familyName": "Katz", 
        "givenName": "Jonathan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53008-5_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53007-8", 
        "978-3-662-53008-5"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "incomplete networks", 
      "MPC protocols", 
      "communication protocols", 
      "communication networks", 
      "public-key encryption scheme", 
      "threshold homomorphic encryption", 
      "multi-party computation", 
      "new security challenges", 
      "black-box use", 
      "secure MPC protocol", 
      "multi-party protocols", 
      "black-box nature", 
      "homomorphic encryption", 
      "encryption scheme", 
      "cryptographic primitives", 
      "network information", 
      "cryptographic assumptions", 
      "security challenges", 
      "computation complexity", 
      "intermediate nodes", 
      "network nodes", 
      "anonymous broadcast", 
      "DDH assumption", 
      "optimization tricks", 
      "modern applications", 
      "arbitrary networks", 
      "enhanced variant", 
      "network", 
      "simple network", 
      "recursive use", 
      "communication", 
      "computation", 
      "nodes", 
      "protocol", 
      "encryption", 
      "scheme", 
      "adversary", 
      "topology", 
      "primitives", 
      "applications", 
      "anonymity", 
      "pseudonyms", 
      "broadcast", 
      "challenges", 
      "messages", 
      "complexity", 
      "recent work", 
      "solution", 
      "Chandran", 
      "MPC", 
      "assumption", 
      "information", 
      "et al", 
      "work", 
      "tricks", 
      "setup", 
      "box", 
      "use", 
      "knowledge", 
      "al", 
      "properties", 
      "variants", 
      "fact", 
      "Moran et al", 
      "nature", 
      "degree", 
      "low degree", 
      "diameter", 
      "extent", 
      "exception"
    ], 
    "name": "Network-Hiding Communication and Applications to Multi-party Protocols", 
    "pagination": "335-365", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050792972"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53008-5_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53008-5_12", 
      "https://app.dimensions.ai/details/publication/pub.1050792972"
    ], 
    "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_349.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53008-5_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/978-3-662-53008-5_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/978-3-662-53008-5_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53008-5_12'

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-53008-5_12'


 

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

163 TRIPLES      23 PREDICATES      96 URIs      88 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53008-5_12 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author Ne5941a3430c44422be43847c41d73be0
5 schema:datePublished 2016-07-21
6 schema:datePublishedReg 2016-07-21
7 schema:description As distributed networks are heavily used in modern applications, new security challenges emerge. In a multi-party computation (in short, MPC) protocol over an incomplete network, such a challenge is to hide, to the extent possible, the topology of the underlying communication network. Such a topology-hiding (aka network hiding) property is in fact very relevant in applications where anonymity is needed.To our knowledge, with the exception of two recent works by Chandran et al. [ITCS 2015] and by Moran et al. [TCC 2015], existing MPC protocols do not hide the topology of the underlying communication network. Moreover, the above two solutions are either not applicable to arbitrary networks (as is [ITCS 2015]) or, as in [TCC 2015], they make non-black-box and recursive use of cryptographic primitives resulting in an unrealistic communication and computation complexity even for simple, i.e., low degree and diameter, networks.Our work suggests the first topology-hiding communication protocol for incomplete networks which makes black-box use of the underlying cryptographic assumption—in particular, a public-key encryption scheme—and tolerates any adversary who passively corrupts arbitrarily many network nodes. Our solutions are based on a new, enhanced variant of threshold homomorphic encryption, in short, TH-PKE, that requires no a-priori setup and allows to circulate an encrypted message over any (unknown) incomplete network and then decrypt it without revealing any network information to intermediate nodes. We show how to realize this enhanced TH-PKE from the DDH assumption. The black-box nature of our scheme, along with some optimization tricks that we employ, makes our communication protocol more efficient than existing solutions.We then use our communication protocol to make any semi-honest secure MPC protocol topology-hiding with a reasonable—i.e., for simple networks, polynomial with small constants—communication and computation overhead. We further show how to construct anonymous broadcast without using expensive MPCs to setup the original pseudonyms.
8 schema:editor Nfe8eadee7e0549668be16239c639bff5
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N80a1fbd17285486c83a0e7703c85fd11
13 schema:keywords Chandran
14 DDH assumption
15 MPC
16 MPC protocols
17 Moran et al
18 adversary
19 al
20 anonymity
21 anonymous broadcast
22 applications
23 arbitrary networks
24 assumption
25 black-box nature
26 black-box use
27 box
28 broadcast
29 challenges
30 communication
31 communication networks
32 communication protocols
33 complexity
34 computation
35 computation complexity
36 cryptographic assumptions
37 cryptographic primitives
38 degree
39 diameter
40 encryption
41 encryption scheme
42 enhanced variant
43 et al
44 exception
45 extent
46 fact
47 homomorphic encryption
48 incomplete networks
49 information
50 intermediate nodes
51 knowledge
52 low degree
53 messages
54 modern applications
55 multi-party computation
56 multi-party protocols
57 nature
58 network
59 network information
60 network nodes
61 new security challenges
62 nodes
63 optimization tricks
64 primitives
65 properties
66 protocol
67 pseudonyms
68 public-key encryption scheme
69 recent work
70 recursive use
71 scheme
72 secure MPC protocol
73 security challenges
74 setup
75 simple network
76 solution
77 threshold homomorphic encryption
78 topology
79 tricks
80 use
81 variants
82 work
83 schema:name Network-Hiding Communication and Applications to Multi-party Protocols
84 schema:pagination 335-365
85 schema:productId N3de375a67d774d389826989538b4a076
86 Nea01cd99cf77436f8639dd198474f244
87 schema:publisher N93b6984803f94cf88ab21843c1d5a370
88 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050792972
89 https://doi.org/10.1007/978-3-662-53008-5_12
90 schema:sdDatePublished 2022-05-20T07:46
91 schema:sdLicense https://scigraph.springernature.com/explorer/license/
92 schema:sdPublisher N36f8813e5b7244709458d0212d4dcd55
93 schema:url https://doi.org/10.1007/978-3-662-53008-5_12
94 sgo:license sg:explorer/license/
95 sgo:sdDataset chapters
96 rdf:type schema:Chapter
97 N0188ee6598054c65a53f7693abcaff91 rdf:first sg:person.011112577475.84
98 rdf:rest N8beebd984ec84b2e92de0b290b4194ea
99 N36f8813e5b7244709458d0212d4dcd55 schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 N3de375a67d774d389826989538b4a076 schema:name doi
102 schema:value 10.1007/978-3-662-53008-5_12
103 rdf:type schema:PropertyValue
104 N6711f09127344646815fcef61426d95f schema:familyName Katz
105 schema:givenName Jonathan
106 rdf:type schema:Person
107 N74206b644fdf41f3b72fc04b1d1c293a schema:familyName Robshaw
108 schema:givenName Matthew
109 rdf:type schema:Person
110 N80a1fbd17285486c83a0e7703c85fd11 schema:isbn 978-3-662-53007-8
111 978-3-662-53008-5
112 schema:name Advances in Cryptology – CRYPTO 2016
113 rdf:type schema:Book
114 N8beebd984ec84b2e92de0b290b4194ea rdf:first sg:person.012007513121.08
115 rdf:rest rdf:nil
116 N93b6984803f94cf88ab21843c1d5a370 schema:name Springer Nature
117 rdf:type schema:Organisation
118 Ne5941a3430c44422be43847c41d73be0 rdf:first sg:person.010611500757.30
119 rdf:rest Nfba04ddf785e4cfe8c6ae900664df9af
120 Nea01cd99cf77436f8639dd198474f244 schema:name dimensions_id
121 schema:value pub.1050792972
122 rdf:type schema:PropertyValue
123 Nef47e1adbe4946a0b899c18d3507e088 rdf:first N6711f09127344646815fcef61426d95f
124 rdf:rest rdf:nil
125 Nfba04ddf785e4cfe8c6ae900664df9af rdf:first sg:person.01316567627.91
126 rdf:rest N0188ee6598054c65a53f7693abcaff91
127 Nfe8eadee7e0549668be16239c639bff5 rdf:first N74206b644fdf41f3b72fc04b1d1c293a
128 rdf:rest Nef47e1adbe4946a0b899c18d3507e088
129 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
130 schema:name Information and Computing Sciences
131 rdf:type schema:DefinedTerm
132 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
133 schema:name Computation Theory and Mathematics
134 rdf:type schema:DefinedTerm
135 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
136 schema:name Data Format
137 rdf:type schema:DefinedTerm
138 sg:person.010611500757.30 schema:affiliation grid-institutes:grid.5801.c
139 schema:familyName Hirt
140 schema:givenName Martin
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010611500757.30
142 rdf:type schema:Person
143 sg:person.011112577475.84 schema:affiliation grid-institutes:grid.5801.c
144 schema:familyName Tschudi
145 schema:givenName Daniel
146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011112577475.84
147 rdf:type schema:Person
148 sg:person.012007513121.08 schema:affiliation grid-institutes:grid.33647.35
149 schema:familyName Zikas
150 schema:givenName Vassilis
151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012007513121.08
152 rdf:type schema:Person
153 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
154 schema:familyName Maurer
155 schema:givenName Ueli
156 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
157 rdf:type schema:Person
158 grid-institutes:grid.33647.35 schema:alternateName RPI, Troy, USA
159 schema:name RPI, Troy, USA
160 rdf:type schema:Organization
161 grid-institutes:grid.5801.c schema:alternateName ETH Zurich, Zürich, Switzerland
162 schema:name ETH Zurich, Zürich, Switzerland
163 rdf:type schema:Organization
 




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


...