Topology-Hiding Computation Beyond Semi-Honest Adversaries View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-11-08

AUTHORS

Rio LaVigne , Chen-Da Liu-Zhang , Ueli Maurer , Tal Moran , Marta Mularczyk , Daniel Tschudi

ABSTRACT

Topology-hiding communication protocols allow a set of parties, connected by an incomplete network with unknown communication graph, where each party only knows its neighbors, to construct a complete communication network such that the network topology remains hidden even from a powerful adversary who can corrupt parties. This communication network can then be used to perform arbitrary tasks, for example secure multi-party computation, in a topology-hiding manner. Previously proposed protocols could only tolerate passive corruption. This paper proposes protocols that can also tolerate fail-corruption (i.e., the adversary can crash any party at any point in time) and so-called semi-malicious corruption (i.e., the adversary can control a corrupted party’s randomness), without leaking more than an arbitrarily small fraction of a bit of information about the topology. A small-leakage protocol was recently proposed by Ball et al. [Eurocrypt’18], but only under the unrealistic set-up assumption that each party has a trusted hardware module containing secret correlated pre-set keys, and with the further two restrictions that only passively corrupted parties can be crashed by the adversary, and semi-malicious corruption is not tolerated. Since leaking a small amount of information is unavoidable, as is the need to abort the protocol in case of failures, our protocols seem to achieve the best possible goal in a model with fail-corruption.Further contributions of the paper are applications of the protocol to obtain secure MPC protocols, which requires a way to bound the aggregated leakage when multiple small-leakage protocols are executed in parallel or sequentially. Moreover, while previous protocols are based on the DDH assumption, a new so-called PKCR public-key encryption scheme based on the LWE assumption is proposed, allowing to base topology-hiding computation on LWE. Furthermore, a protocol using fully-homomorphic encryption achieving very low round complexity is proposed. More... »

PAGES

3-35

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-03810-6_1

DOI

http://dx.doi.org/10.1007/978-3-030-03810-6_1

DIMENSIONS

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


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": "MIT, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "LaVigne", 
        "givenName": "Rio", 
        "id": "sg:person.013513047001.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013513047001.56"
        ], 
        "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": "Liu-Zhang", 
        "givenName": "Chen-Da", 
        "id": "sg:person.011544110647.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011544110647.05"
        ], 
        "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": "IDC Herzliya, Herzliya, Israel", 
          "id": "http://www.grid.ac/institutes/grid.21166.32", 
          "name": [
            "IDC Herzliya, Herzliya, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Moran", 
        "givenName": "Tal", 
        "id": "sg:person.012022173111.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012022173111.00"
        ], 
        "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": "Mularczyk", 
        "givenName": "Marta", 
        "id": "sg:person.013734432247.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013734432247.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Aarhus University, Aarhus, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.7048.b", 
          "name": [
            "Aarhus University, Aarhus, Denmark"
          ], 
          "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"
      }
    ], 
    "datePublished": "2018-11-08", 
    "datePublishedReg": "2018-11-08", 
    "description": "Topology-hiding communication protocols allow a set of parties, connected by an incomplete network with unknown communication graph, where each party only knows its neighbors, to construct a complete communication network such that the network topology remains hidden even from a powerful adversary who can corrupt parties. This communication network can then be used to perform arbitrary tasks, for example secure multi-party computation, in a topology-hiding manner. Previously proposed protocols could only tolerate passive corruption. This paper proposes protocols that can also tolerate fail-corruption (i.e., the adversary can crash any party at any point in time) and so-called semi-malicious corruption (i.e., the adversary can control a corrupted party\u2019s randomness), without leaking more than an arbitrarily small fraction of a bit of information about the topology. A small-leakage protocol was recently proposed by Ball et al. [Eurocrypt\u201918], but only under the unrealistic set-up assumption that each party has a trusted hardware module containing secret correlated pre-set keys, and with the further two restrictions that only passively corrupted parties can be crashed by the adversary, and semi-malicious corruption is not tolerated. Since leaking a small amount of information is unavoidable, as is the need to abort the protocol in case of failures, our protocols seem to achieve the best possible goal in a model with fail-corruption.Further contributions of the paper are applications of the protocol to obtain secure MPC protocols, which requires a way to bound the aggregated leakage when multiple small-leakage protocols are executed in parallel or sequentially. Moreover, while previous protocols are based on the DDH assumption, a new so-called PKCR public-key encryption scheme based on the LWE assumption is proposed, allowing to base topology-hiding computation on LWE. Furthermore, a protocol using fully-homomorphic encryption achieving very low round complexity is proposed.", 
    "editor": [
      {
        "familyName": "Beimel", 
        "givenName": "Amos", 
        "type": "Person"
      }, 
      {
        "familyName": "Dziembowski", 
        "givenName": "Stefan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-03810-6_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-03809-0", 
        "978-3-030-03810-6"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "Topology-Hiding Computation", 
      "communication networks", 
      "secure multi-party computation", 
      "public-key encryption scheme", 
      "lower round complexity", 
      "multi-party computation", 
      "secure MPC protocol", 
      "semi-honest adversaries", 
      "set of parties", 
      "complete communication network", 
      "homomorphic encryption", 
      "encryption scheme", 
      "hardware modules", 
      "MPC protocols", 
      "communication protocols", 
      "arbitrary tasks", 
      "powerful adversary", 
      "communication graph", 
      "DDH assumption", 
      "round complexity", 
      "network topology", 
      "LWE assumption", 
      "corrupt parties", 
      "incomplete networks", 
      "adversary", 
      "bits of information", 
      "previous protocols", 
      "network", 
      "passive corruptions", 
      "case of failure", 
      "computation", 
      "protocol", 
      "encryption", 
      "possible goals", 
      "topology", 
      "information", 
      "set", 
      "LWE", 
      "graph", 
      "further contribution", 
      "task", 
      "neighbors", 
      "parties", 
      "complexity", 
      "bits", 
      "module", 
      "scheme", 
      "key", 
      "applications", 
      "corruption", 
      "unrealistic set", 
      "goal", 
      "assumption", 
      "way", 
      "need", 
      "parallel", 
      "model", 
      "small fraction", 
      "manner", 
      "et al", 
      "Ball et al", 
      "amount", 
      "restriction", 
      "contribution", 
      "leakage", 
      "small amount", 
      "cases", 
      "failure", 
      "al", 
      "fraction", 
      "paper"
    ], 
    "name": "Topology-Hiding Computation Beyond Semi-Honest Adversaries", 
    "pagination": "3-35", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1109772560"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-03810-6_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-03810-6_1", 
      "https://app.dimensions.ai/details/publication/pub.1109772560"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:44", 
    "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_26.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-03810-6_1"
  }
]
 

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-030-03810-6_1'

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-030-03810-6_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03810-6_1'

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-030-03810-6_1'


 

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

180 TRIPLES      23 PREDICATES      96 URIs      89 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-03810-6_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N526ade962b6f444490e64ba378f2db89
4 schema:datePublished 2018-11-08
5 schema:datePublishedReg 2018-11-08
6 schema:description Topology-hiding communication protocols allow a set of parties, connected by an incomplete network with unknown communication graph, where each party only knows its neighbors, to construct a complete communication network such that the network topology remains hidden even from a powerful adversary who can corrupt parties. This communication network can then be used to perform arbitrary tasks, for example secure multi-party computation, in a topology-hiding manner. Previously proposed protocols could only tolerate passive corruption. This paper proposes protocols that can also tolerate fail-corruption (i.e., the adversary can crash any party at any point in time) and so-called semi-malicious corruption (i.e., the adversary can control a corrupted party’s randomness), without leaking more than an arbitrarily small fraction of a bit of information about the topology. A small-leakage protocol was recently proposed by Ball et al. [Eurocrypt’18], but only under the unrealistic set-up assumption that each party has a trusted hardware module containing secret correlated pre-set keys, and with the further two restrictions that only passively corrupted parties can be crashed by the adversary, and semi-malicious corruption is not tolerated. Since leaking a small amount of information is unavoidable, as is the need to abort the protocol in case of failures, our protocols seem to achieve the best possible goal in a model with fail-corruption.Further contributions of the paper are applications of the protocol to obtain secure MPC protocols, which requires a way to bound the aggregated leakage when multiple small-leakage protocols are executed in parallel or sequentially. Moreover, while previous protocols are based on the DDH assumption, a new so-called PKCR public-key encryption scheme based on the LWE assumption is proposed, allowing to base topology-hiding computation on LWE. Furthermore, a protocol using fully-homomorphic encryption achieving very low round complexity is proposed.
7 schema:editor N5e74422f8dee489e88d5a151f330bf25
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N24c201b3e50441d8b7898864ac5a4e7b
12 schema:keywords Ball et al
13 DDH assumption
14 LWE
15 LWE assumption
16 MPC protocols
17 Topology-Hiding Computation
18 adversary
19 al
20 amount
21 applications
22 arbitrary tasks
23 assumption
24 bits
25 bits of information
26 case of failure
27 cases
28 communication graph
29 communication networks
30 communication protocols
31 complete communication network
32 complexity
33 computation
34 contribution
35 corrupt parties
36 corruption
37 encryption
38 encryption scheme
39 et al
40 failure
41 fraction
42 further contribution
43 goal
44 graph
45 hardware modules
46 homomorphic encryption
47 incomplete networks
48 information
49 key
50 leakage
51 lower round complexity
52 manner
53 model
54 module
55 multi-party computation
56 need
57 neighbors
58 network
59 network topology
60 paper
61 parallel
62 parties
63 passive corruptions
64 possible goals
65 powerful adversary
66 previous protocols
67 protocol
68 public-key encryption scheme
69 restriction
70 round complexity
71 scheme
72 secure MPC protocol
73 secure multi-party computation
74 semi-honest adversaries
75 set
76 set of parties
77 small amount
78 small fraction
79 task
80 topology
81 unrealistic set
82 way
83 schema:name Topology-Hiding Computation Beyond Semi-Honest Adversaries
84 schema:pagination 3-35
85 schema:productId N2e1f44341a1e43cbb7108e1266ddc6c5
86 Nc528f8945c0147319c9c8a9333e05b7d
87 schema:publisher Nda549f461d57474494f4649ba0273adb
88 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109772560
89 https://doi.org/10.1007/978-3-030-03810-6_1
90 schema:sdDatePublished 2022-05-20T07:44
91 schema:sdLicense https://scigraph.springernature.com/explorer/license/
92 schema:sdPublisher Ndec24909ebeb43e8a29af1b4012e64e6
93 schema:url https://doi.org/10.1007/978-3-030-03810-6_1
94 sgo:license sg:explorer/license/
95 sgo:sdDataset chapters
96 rdf:type schema:Chapter
97 N24c201b3e50441d8b7898864ac5a4e7b schema:isbn 978-3-030-03809-0
98 978-3-030-03810-6
99 schema:name Theory of Cryptography
100 rdf:type schema:Book
101 N251b0ce8104e4b438bff0331ceb2d258 rdf:first sg:person.013734432247.31
102 rdf:rest Na11edffbed624f51929396c85db1a900
103 N2e1f44341a1e43cbb7108e1266ddc6c5 schema:name doi
104 schema:value 10.1007/978-3-030-03810-6_1
105 rdf:type schema:PropertyValue
106 N3f888bbf408846aa971987b5a37a9810 schema:familyName Beimel
107 schema:givenName Amos
108 rdf:type schema:Person
109 N44a2646ea51a45208fbfc2cff9bf3b1f rdf:first sg:person.012022173111.00
110 rdf:rest N251b0ce8104e4b438bff0331ceb2d258
111 N526ade962b6f444490e64ba378f2db89 rdf:first sg:person.013513047001.56
112 rdf:rest N88f8fefab17741d3807910eda28135c1
113 N5e74422f8dee489e88d5a151f330bf25 rdf:first N3f888bbf408846aa971987b5a37a9810
114 rdf:rest Ned85d99799ee47709c694b74507dba9b
115 N88f8fefab17741d3807910eda28135c1 rdf:first sg:person.011544110647.05
116 rdf:rest Nc9c70c6673fc443ba916bfb98f10dbe2
117 Na11edffbed624f51929396c85db1a900 rdf:first sg:person.011112577475.84
118 rdf:rest rdf:nil
119 Na26c3d0c496b422784dd31f5c976a370 schema:familyName Dziembowski
120 schema:givenName Stefan
121 rdf:type schema:Person
122 Nc528f8945c0147319c9c8a9333e05b7d schema:name dimensions_id
123 schema:value pub.1109772560
124 rdf:type schema:PropertyValue
125 Nc9c70c6673fc443ba916bfb98f10dbe2 rdf:first sg:person.01316567627.91
126 rdf:rest N44a2646ea51a45208fbfc2cff9bf3b1f
127 Nda549f461d57474494f4649ba0273adb schema:name Springer Nature
128 rdf:type schema:Organisation
129 Ndec24909ebeb43e8a29af1b4012e64e6 schema:name Springer Nature - SN SciGraph project
130 rdf:type schema:Organization
131 Ned85d99799ee47709c694b74507dba9b rdf:first Na26c3d0c496b422784dd31f5c976a370
132 rdf:rest rdf:nil
133 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
134 schema:name Information and Computing Sciences
135 rdf:type schema:DefinedTerm
136 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
137 schema:name Computation Theory and Mathematics
138 rdf:type schema:DefinedTerm
139 sg:person.011112577475.84 schema:affiliation grid-institutes:grid.7048.b
140 schema:familyName Tschudi
141 schema:givenName Daniel
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011112577475.84
143 rdf:type schema:Person
144 sg:person.011544110647.05 schema:affiliation grid-institutes:grid.5801.c
145 schema:familyName Liu-Zhang
146 schema:givenName Chen-Da
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011544110647.05
148 rdf:type schema:Person
149 sg:person.012022173111.00 schema:affiliation grid-institutes:grid.21166.32
150 schema:familyName Moran
151 schema:givenName Tal
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012022173111.00
153 rdf:type schema:Person
154 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
155 schema:familyName Maurer
156 schema:givenName Ueli
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
158 rdf:type schema:Person
159 sg:person.013513047001.56 schema:affiliation grid-institutes:grid.116068.8
160 schema:familyName LaVigne
161 schema:givenName Rio
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013513047001.56
163 rdf:type schema:Person
164 sg:person.013734432247.31 schema:affiliation grid-institutes:grid.5801.c
165 schema:familyName Mularczyk
166 schema:givenName Marta
167 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013734432247.31
168 rdf:type schema:Person
169 grid-institutes:grid.116068.8 schema:alternateName MIT, Cambridge, USA
170 schema:name MIT, Cambridge, USA
171 rdf:type schema:Organization
172 grid-institutes:grid.21166.32 schema:alternateName IDC Herzliya, Herzliya, Israel
173 schema:name IDC Herzliya, Herzliya, Israel
174 rdf:type schema:Organization
175 grid-institutes:grid.5801.c schema:alternateName ETH Zurich, Zürich, Switzerland
176 schema:name ETH Zurich, Zürich, Switzerland
177 rdf:type schema:Organization
178 grid-institutes:grid.7048.b schema:alternateName Aarhus University, Aarhus, Denmark
179 schema:name Aarhus University, Aarhus, Denmark
180 rdf:type schema:Organization
 




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


...