Secure Distributed Key Generation for Discrete-Log Based Cryptosystems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-05-24

AUTHORS

Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin

ABSTRACT

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. More... »

PAGES

51-83

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00145-006-0347-3

DOI

http://dx.doi.org/10.1007/s00145-006-0347-3

DIMENSIONS

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


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": "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

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/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
 




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


...