Ontology type: schema:ScholarlyArticle
2006-05-24
AUTHORSRosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin
ABSTRACTA Distributed Key Generation (DKG) protocol is an essential component of threshold cryptosystems required to initialize the cryptosystem securely and generate its private and public keys. In the case of discrete-log-based (dlog-based) threshold signature schemes (ElGamal and its derivatives), the DKG protocol is further used in the distributed signature generation phase to generate one-time signature randomizers (r = gk). In this paper we show that a widely used dlog-based DKG protocol suggested by Pedersen does not guarantee a uniformly random distribution of generated keys: we describe an efficient active attacker controlling a small number of parties which successfully biases the values of the generated keys away from uniform. We then present a new DKG protocol for the setting of dlog-based cryptosystems which we prove to satisfy the security requirements from DKG protocols and, in particular, it ensures a uniform distribution of the generated keys. The new protocol can be used as a secure replacement for the many applications of Pedersen's protocol. Motivated by the fact that the new DKG protocol incurs additional communication cost relative to Pedersen's original protocol, we investigate whether the latter can be used in specific applications which require relaxed security properties from the DKG protocol. We answer this question affirmatively by showing that Pedersen's protocol suffices for the secure implementation of certain threshold cryptosystems whose security can be reduced to the hardness of the discrete logarithm problem. In particular, we show Pedersen's DKG to be sufficient for the construction of a threshold Schnorr signature scheme. Finally, we observe an interesting trade-off between security (reductions), computation, and communication that arises when comparing Pedersen's DKG protocol with ours. More... »
PAGES51-83
http://scigraph.springernature.com/pub.10.1007/s00145-006-0347-3
DOIhttp://dx.doi.org/10.1007/s00145-006-0347-3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1000307063
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": "IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA",
"id": "http://www.grid.ac/institutes/grid.481554.9",
"name": [
"IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, 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": "School of Information and Computer Science, University of California, Irvine, CA 92697-3425, USA",
"id": "http://www.grid.ac/institutes/grid.266093.8",
"name": [
"School of Information and Computer Science, University of California, Irvine, CA 92697-3425, USA"
],
"type": "Organization"
},
"familyName": "Jarecki",
"givenName": "Stanislaw",
"id": "sg:person.014344574541.81",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014344574541.81"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA",
"id": "http://www.grid.ac/institutes/grid.481554.9",
"name": [
"IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA"
],
"type": "Organization"
},
"familyName": "Krawczyk",
"givenName": "Hugo",
"id": "sg:person.013004021661.30",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013004021661.30"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA",
"id": "http://www.grid.ac/institutes/grid.481554.9",
"name": [
"IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, 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": "2006-05-24",
"datePublishedReg": "2006-05-24",
"description": "A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptosystems required to initialize the cryptosystem securely and generate its private and public keys. In the case of discrete-log-based (dlog-based) threshold signature schemes (ElGamal and its derivatives), the DKG protocol is further used in the distributed signature generation phase to generate one-time signature randomizers (r = gk). In this paper we show that a widely used dlog-based DKG protocol suggested by Pedersen does not guarantee a uniformly random distribution of generated keys: we describe an efficient active attacker controlling a small number of parties which successfully biases the values of the generated keys away from uniform. We then present a new DKG protocol for the setting of dlog-based cryptosystems which we prove to satisfy the security requirements from DKG protocols and, in particular, it ensures a uniform distribution of the generated keys. The new protocol can be used as a secure replacement for the many applications of Pedersen's protocol. Motivated by the fact that the new DKG protocol incurs additional communication cost relative to Pedersen's original protocol, we investigate whether the latter can be used in specific applications which require relaxed security properties from the DKG protocol. We answer this question affirmatively by showing that Pedersen's protocol suffices for the secure implementation of certain threshold cryptosystems whose security can be reduced to the hardness of the discrete logarithm problem. In particular, we show Pedersen's DKG to be sufficient for the construction of a threshold Schnorr signature scheme. Finally, we observe an interesting trade-off between security (reductions), computation, and communication that arises when comparing Pedersen's DKG protocol with ours.",
"genre": "article",
"id": "sg:pub.10.1007/s00145-006-0347-3",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1136278",
"issn": [
"0933-2790",
"1432-1378"
],
"name": "Journal of Cryptology",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "20"
}
],
"keywords": [
"DKG protocol",
"threshold cryptosystems",
"signature scheme",
"additional communication cost",
"signature generation phase",
"discrete logarithm problem",
"key generation protocol",
"threshold signature scheme",
"Schnorr signature scheme",
"security requirements",
"security properties",
"communication cost",
"active attacker",
"secure implementation",
"logarithm problem",
"public key",
"key generation",
"secure replacement",
"cryptosystem",
"original protocol",
"generation phase",
"generation protocol",
"new protocol",
"security",
"specific applications",
"key",
"protocol",
"scheme",
"attacker",
"applications",
"computation",
"implementation",
"communication",
"small number",
"requirements",
"randomizer",
"DKG",
"cost",
"essential component",
"parties",
"ours",
"construction",
"generation",
"number",
"components",
"fact",
"setting",
"uniform",
"questions",
"random distribution",
"distribution",
"cases",
"phase",
"values",
"Pedersen",
"properties",
"replacement",
"hardness",
"paper",
"problem"
],
"name": "Secure Distributed Key Generation for Discrete-Log Based Cryptosystems",
"pagination": "51-83",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1000307063"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00145-006-0347-3"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00145-006-0347-3",
"https://app.dimensions.ai/details/publication/pub.1000307063"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:23",
"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/article/article_417.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00145-006-0347-3"
}
]
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/s00145-006-0347-3'
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/s00145-006-0347-3'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-006-0347-3'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-006-0347-3'
This table displays all metadata directly associated to this object as RDF triples.
146 TRIPLES
21 PREDICATES
86 URIs
77 LITERALS
6 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/s00145-006-0347-3 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0802 |
3 | ″ | ″ | anzsrc-for:0804 |
4 | ″ | schema:author | N63ca054e78424c9a99584952274be4d0 |
5 | ″ | schema:datePublished | 2006-05-24 |
6 | ″ | schema:datePublishedReg | 2006-05-24 |
7 | ″ | schema:description | A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptosystems required to initialize the cryptosystem securely and generate its private and public keys. In the case of discrete-log-based (dlog-based) threshold signature schemes (ElGamal and its derivatives), the DKG protocol is further used in the distributed signature generation phase to generate one-time signature randomizers (r = gk). In this paper we show that a widely used dlog-based DKG protocol suggested by Pedersen does not guarantee a uniformly random distribution of generated keys: we describe an efficient active attacker controlling a small number of parties which successfully biases the values of the generated keys away from uniform. We then present a new DKG protocol for the setting of dlog-based cryptosystems which we prove to satisfy the security requirements from DKG protocols and, in particular, it ensures a uniform distribution of the generated keys. The new protocol can be used as a secure replacement for the many applications of Pedersen's protocol. Motivated by the fact that the new DKG protocol incurs additional communication cost relative to Pedersen's original protocol, we investigate whether the latter can be used in specific applications which require relaxed security properties from the DKG protocol. We answer this question affirmatively by showing that Pedersen's protocol suffices for the secure implementation of certain threshold cryptosystems whose security can be reduced to the hardness of the discrete logarithm problem. In particular, we show Pedersen's DKG to be sufficient for the construction of a threshold Schnorr signature scheme. Finally, we observe an interesting trade-off between security (reductions), computation, and communication that arises when comparing Pedersen's DKG protocol with ours. |
8 | ″ | schema:genre | article |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | false |
11 | ″ | schema:isPartOf | Nb935051a69ad40a09b4e7daffa959b62 |
12 | ″ | ″ | Ne40facd1ca0d40dda189e576bcaa14f1 |
13 | ″ | ″ | sg:journal.1136278 |
14 | ″ | schema:keywords | DKG |
15 | ″ | ″ | DKG protocol |
16 | ″ | ″ | Pedersen |
17 | ″ | ″ | Schnorr signature scheme |
18 | ″ | ″ | active attacker |
19 | ″ | ″ | additional communication cost |
20 | ″ | ″ | applications |
21 | ″ | ″ | attacker |
22 | ″ | ″ | cases |
23 | ″ | ″ | communication |
24 | ″ | ″ | communication cost |
25 | ″ | ″ | components |
26 | ″ | ″ | computation |
27 | ″ | ″ | construction |
28 | ″ | ″ | cost |
29 | ″ | ″ | cryptosystem |
30 | ″ | ″ | discrete logarithm problem |
31 | ″ | ″ | distribution |
32 | ″ | ″ | essential component |
33 | ″ | ″ | fact |
34 | ″ | ″ | generation |
35 | ″ | ″ | generation phase |
36 | ″ | ″ | generation protocol |
37 | ″ | ″ | hardness |
38 | ″ | ″ | implementation |
39 | ″ | ″ | key |
40 | ″ | ″ | key generation |
41 | ″ | ″ | key generation protocol |
42 | ″ | ″ | logarithm problem |
43 | ″ | ″ | new protocol |
44 | ″ | ″ | number |
45 | ″ | ″ | original protocol |
46 | ″ | ″ | ours |
47 | ″ | ″ | paper |
48 | ″ | ″ | parties |
49 | ″ | ″ | phase |
50 | ″ | ″ | problem |
51 | ″ | ″ | properties |
52 | ″ | ″ | protocol |
53 | ″ | ″ | public key |
54 | ″ | ″ | questions |
55 | ″ | ″ | random distribution |
56 | ″ | ″ | randomizer |
57 | ″ | ″ | replacement |
58 | ″ | ″ | requirements |
59 | ″ | ″ | scheme |
60 | ″ | ″ | secure implementation |
61 | ″ | ″ | secure replacement |
62 | ″ | ″ | security |
63 | ″ | ″ | security properties |
64 | ″ | ″ | security requirements |
65 | ″ | ″ | setting |
66 | ″ | ″ | signature generation phase |
67 | ″ | ″ | signature scheme |
68 | ″ | ″ | small number |
69 | ″ | ″ | specific applications |
70 | ″ | ″ | threshold cryptosystems |
71 | ″ | ″ | threshold signature scheme |
72 | ″ | ″ | uniform |
73 | ″ | ″ | values |
74 | ″ | schema:name | Secure Distributed Key Generation for Discrete-Log Based Cryptosystems |
75 | ″ | schema:pagination | 51-83 |
76 | ″ | schema:productId | N81d9ebea787141e3ba162afc74ce6018 |
77 | ″ | ″ | Ne7854df625304e038da8e9fba6a536f7 |
78 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1000307063 |
79 | ″ | ″ | https://doi.org/10.1007/s00145-006-0347-3 |
80 | ″ | schema:sdDatePublished | 2022-05-20T07:23 |
81 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
82 | ″ | schema:sdPublisher | N49265ff20e2d4a87a0a0eb1657c219ce |
83 | ″ | schema:url | https://doi.org/10.1007/s00145-006-0347-3 |
84 | ″ | sgo:license | sg:explorer/license/ |
85 | ″ | sgo:sdDataset | articles |
86 | ″ | rdf:type | schema:ScholarlyArticle |
87 | N1768e494dbf444709ed020a0780b4414 | rdf:first | sg:person.014344574541.81 |
88 | ″ | rdf:rest | N377a41d1d3a64c5996eb551d5e688f83 |
89 | N377a41d1d3a64c5996eb551d5e688f83 | rdf:first | sg:person.013004021661.30 |
90 | ″ | rdf:rest | Nc92a5dfff36f4015b584f824f13398ea |
91 | N49265ff20e2d4a87a0a0eb1657c219ce | schema:name | Springer Nature - SN SciGraph project |
92 | ″ | rdf:type | schema:Organization |
93 | N63ca054e78424c9a99584952274be4d0 | rdf:first | sg:person.013573255563.35 |
94 | ″ | rdf:rest | N1768e494dbf444709ed020a0780b4414 |
95 | N81d9ebea787141e3ba162afc74ce6018 | schema:name | dimensions_id |
96 | ″ | schema:value | pub.1000307063 |
97 | ″ | rdf:type | schema:PropertyValue |
98 | Nb935051a69ad40a09b4e7daffa959b62 | schema:issueNumber | 1 |
99 | ″ | rdf:type | schema:PublicationIssue |
100 | Nc92a5dfff36f4015b584f824f13398ea | rdf:first | sg:person.015473523512.58 |
101 | ″ | rdf:rest | rdf:nil |
102 | Ne40facd1ca0d40dda189e576bcaa14f1 | schema:volumeNumber | 20 |
103 | ″ | rdf:type | schema:PublicationVolume |
104 | Ne7854df625304e038da8e9fba6a536f7 | schema:name | doi |
105 | ″ | schema:value | 10.1007/s00145-006-0347-3 |
106 | ″ | rdf:type | schema:PropertyValue |
107 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
108 | ″ | schema:name | Information and Computing Sciences |
109 | ″ | rdf:type | schema:DefinedTerm |
110 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |
111 | ″ | schema:name | Computation Theory and Mathematics |
112 | ″ | rdf:type | schema:DefinedTerm |
113 | anzsrc-for:0804 | schema:inDefinedTermSet | anzsrc-for: |
114 | ″ | schema:name | Data Format |
115 | ″ | rdf:type | schema:DefinedTerm |
116 | sg:journal.1136278 | schema:issn | 0933-2790 |
117 | ″ | ″ | 1432-1378 |
118 | ″ | schema:name | Journal of Cryptology |
119 | ″ | schema:publisher | Springer Nature |
120 | ″ | rdf:type | schema:Periodical |
121 | sg:person.013004021661.30 | schema:affiliation | grid-institutes:grid.481554.9 |
122 | ″ | schema:familyName | Krawczyk |
123 | ″ | schema:givenName | Hugo |
124 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013004021661.30 |
125 | ″ | rdf:type | schema:Person |
126 | sg:person.013573255563.35 | schema:affiliation | grid-institutes:grid.481554.9 |
127 | ″ | schema:familyName | Gennaro |
128 | ″ | schema:givenName | Rosario |
129 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013573255563.35 |
130 | ″ | rdf:type | schema:Person |
131 | sg:person.014344574541.81 | schema:affiliation | grid-institutes:grid.266093.8 |
132 | ″ | schema:familyName | Jarecki |
133 | ″ | schema:givenName | Stanislaw |
134 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014344574541.81 |
135 | ″ | rdf:type | schema:Person |
136 | sg:person.015473523512.58 | schema:affiliation | grid-institutes:grid.481554.9 |
137 | ″ | schema:familyName | Rabin |
138 | ″ | schema:givenName | Tal |
139 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58 |
140 | ″ | rdf:type | schema:Person |
141 | grid-institutes:grid.266093.8 | schema:alternateName | School of Information and Computer Science, University of California, Irvine, CA 92697-3425, USA |
142 | ″ | schema:name | School of Information and Computer Science, University of California, Irvine, CA 92697-3425, USA |
143 | ″ | rdf:type | schema:Organization |
144 | grid-institutes:grid.481554.9 | schema:alternateName | IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA |
145 | ″ | schema:name | IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA |
146 | ″ | rdf:type | schema:Organization |