Ontology type: schema:Chapter
2018-11-08
AUTHORSRio LaVigne , Chen-Da Liu-Zhang , Ueli Maurer , Tal Moran , Marta Mularczyk , Daniel Tschudi
ABSTRACTTopology-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... »
PAGES3-35
Theory of Cryptography
ISBN
978-3-030-03809-0
978-3-030-03810-6
http://scigraph.springernature.com/pub.10.1007/978-3-030-03810-6_1
DOIhttp://dx.doi.org/10.1007/978-3-030-03810-6_1
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1109772560
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
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 |