Secure Hashed Diffie-Hellman over Non-DDH Groups View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Rosario Gennaro , Hugo Krawczyk , Tal Rabin

ABSTRACT

The Diffie-Hellman (DH) transform is a basic cryptographic primitive used in innumerable cryptographic applications, most prominently in discrete-log based encryption schemes and in the Diffie-Hellman key exchange. In many of these applications it has been recognized that the direct use of the DH output, even over groups that satisfy the strong Decisional Diffie-Hellman (DDH) assumption, may be insecure. This is the case when the application invoking the DH transform requires a value that is pseudo-randomly distributed over a set of strings of some length rather than over the DH group in use. A well-known and general solution is to hash (using a universal hash family) the DH output; we refer to this practice as the “hashed DH transform”.The question that we investigate in this paper is to what extent the DDH assumption is required when applying the hashed DH transform. We show that one can obtain a secure hashed DH transform over a non-DDH group G (i.e., a group in which the DDH assumption does not hold); indeed, we prove that for the hashed DH transform to be secure it suffices that G contain a sufficiently large DDH subgroup. As an application of this result, we show that the hashed DH transform is secure over Zp* for random prime p, provided that the DDH assumption holds over the large prime-order subgroups of Zp*. In particular, we obtain the same security working directly over Zp* as working over prime-order subgroups, without requiring any knowledge of the prime factorization of p-1 and without even having to find a generator of Zp*.Further contributions of the paper to the study of the DDH assumption include: the introduction of a DDH relaxation, via computational entropy, which we call the “t-DDH assumption” and which plays a central role in obtaining the above results; a characterization of DDH groups in terms of their DDH subgroups; and the analysis of of the DDH (and t-DDH) assumptions when using short exponents. More... »

PAGES

361-381

Book

TITLE

Advances in Cryptology - EUROCRYPT 2004

ISBN

978-3-540-21935-4
978-3-540-24676-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24676-3_22

DOI

http://dx.doi.org/10.1007/978-3-540-24676-3_22

DIMENSIONS

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


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/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, PO Box 704, 10598, Yorktown Heights, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J.Watson Research Center, PO Box 704, 10598, Yorktown Heights, NY, 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": "IBM T.J. Watson Research Center, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "Department of Electrical Engineering, Technion, 32000, Haifa, Israel", 
            "IBM T.J. Watson Research Center, New York, 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, PO Box 704, 10598, Yorktown Heights, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J.Watson Research Center, PO Box 704, 10598, Yorktown Heights, NY, 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": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "The Diffie-Hellman (DH) transform is a basic cryptographic primitive used in innumerable cryptographic applications, most prominently in discrete-log based encryption schemes and in the Diffie-Hellman key exchange. In many of these applications it has been recognized that the direct use of the DH output, even over groups that satisfy the strong Decisional Diffie-Hellman (DDH) assumption, may be insecure. This is the case when the application invoking the DH transform requires a value that is pseudo-randomly distributed over a set of strings of some length rather than over the DH group in use. A well-known and general solution is to hash (using a universal hash family) the DH output; we refer to this practice as the \u201chashed DH transform\u201d.The question that we investigate in this paper is to what extent the DDH assumption is required when applying the hashed DH transform. We show that one can obtain a secure hashed DH transform over a non-DDH group G (i.e., a group in which the DDH assumption does not hold); indeed, we prove that for the hashed DH transform to be secure it suffices that G contain a sufficiently large DDH subgroup. As an application of this result, we show that the hashed DH transform is secure over Zp* for random prime p, provided that the DDH assumption holds over the large prime-order subgroups of Zp*. In particular, we obtain the same security working directly over Zp* as working over prime-order subgroups, without requiring any knowledge of the prime factorization of p-1 and without even having to find a generator of Zp*.Further contributions of the paper to the study of the DDH assumption include: the introduction of a DDH relaxation, via computational entropy, which we call the \u201ct-DDH assumption\u201d and which plays a central role in obtaining the above results; a characterization of DDH groups in terms of their DDH subgroups; and the analysis of of the DDH (and t-DDH) assumptions when using short exponents.", 
    "editor": [
      {
        "familyName": "Cachin", 
        "givenName": "Christian", 
        "type": "Person"
      }, 
      {
        "familyName": "Camenisch", 
        "givenName": "Jan L.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24676-3_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21935-4", 
        "978-3-540-24676-3"
      ], 
      "name": "Advances in Cryptology - EUROCRYPT 2004", 
      "type": "Book"
    }, 
    "keywords": [
      "DDH assumption", 
      "prime order subgroup", 
      "Diffie-Hellman key exchange", 
      "decisional Diffie-Hellman assumption", 
      "Diffie-Hellman assumption", 
      "basic cryptographic primitives", 
      "large prime-order subgroup", 
      "encryption scheme", 
      "cryptographic primitives", 
      "set of strings", 
      "key exchange", 
      "Diffie-Hellman", 
      "cryptographic applications", 
      "same security", 
      "computational entropy", 
      "prime factorization", 
      "short exponents", 
      "hash", 
      "applications", 
      "primitives", 
      "transform", 
      "security", 
      "direct use", 
      "further contribution", 
      "scheme", 
      "factorization", 
      "set", 
      "output", 
      "general solution", 
      "strings", 
      "assumption", 
      "solution", 
      "DDH group", 
      "use", 
      "knowledge", 
      "generator", 
      "entropy", 
      "results", 
      "terms", 
      "exchange", 
      "contribution", 
      "introduction", 
      "practice", 
      "analysis", 
      "questions", 
      "cases", 
      "central role", 
      "values", 
      "relaxation", 
      "length", 
      "role", 
      "study", 
      "group", 
      "extent", 
      "exponent", 
      "above results", 
      "ZP", 
      "DH group", 
      "characterization", 
      "group G", 
      "subgroups", 
      "paper"
    ], 
    "name": "Secure Hashed Diffie-Hellman over Non-DDH Groups", 
    "pagination": "361-381", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047012120"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24676-3_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24676-3_22", 
      "https://app.dimensions.ai/details/publication/pub.1047012120"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_258.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24676-3_22"
  }
]
 

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-540-24676-3_22'

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-540-24676-3_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24676-3_22'

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-540-24676-3_22'


 

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

144 TRIPLES      23 PREDICATES      88 URIs      81 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24676-3_22 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nba37c452f0a4472a918c742c90ecea75
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description The Diffie-Hellman (DH) transform is a basic cryptographic primitive used in innumerable cryptographic applications, most prominently in discrete-log based encryption schemes and in the Diffie-Hellman key exchange. In many of these applications it has been recognized that the direct use of the DH output, even over groups that satisfy the strong Decisional Diffie-Hellman (DDH) assumption, may be insecure. This is the case when the application invoking the DH transform requires a value that is pseudo-randomly distributed over a set of strings of some length rather than over the DH group in use. A well-known and general solution is to hash (using a universal hash family) the DH output; we refer to this practice as the “hashed DH transform”.The question that we investigate in this paper is to what extent the DDH assumption is required when applying the hashed DH transform. We show that one can obtain a secure hashed DH transform over a non-DDH group G (i.e., a group in which the DDH assumption does not hold); indeed, we prove that for the hashed DH transform to be secure it suffices that G contain a sufficiently large DDH subgroup. As an application of this result, we show that the hashed DH transform is secure over Zp* for random prime p, provided that the DDH assumption holds over the large prime-order subgroups of Zp*. In particular, we obtain the same security working directly over Zp* as working over prime-order subgroups, without requiring any knowledge of the prime factorization of p-1 and without even having to find a generator of Zp*.Further contributions of the paper to the study of the DDH assumption include: the introduction of a DDH relaxation, via computational entropy, which we call the “t-DDH assumption” and which plays a central role in obtaining the above results; a characterization of DDH groups in terms of their DDH subgroups; and the analysis of of the DDH (and t-DDH) assumptions when using short exponents.
7 schema:editor Ncdf22cec3bad4f77a40d3535e3fca4b2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne58e21b9dba940b2bb19986497819146
12 schema:keywords DDH assumption
13 DDH group
14 DH group
15 Diffie-Hellman
16 Diffie-Hellman assumption
17 Diffie-Hellman key exchange
18 ZP
19 above results
20 analysis
21 applications
22 assumption
23 basic cryptographic primitives
24 cases
25 central role
26 characterization
27 computational entropy
28 contribution
29 cryptographic applications
30 cryptographic primitives
31 decisional Diffie-Hellman assumption
32 direct use
33 encryption scheme
34 entropy
35 exchange
36 exponent
37 extent
38 factorization
39 further contribution
40 general solution
41 generator
42 group
43 group G
44 hash
45 introduction
46 key exchange
47 knowledge
48 large prime-order subgroup
49 length
50 output
51 paper
52 practice
53 prime factorization
54 prime order subgroup
55 primitives
56 questions
57 relaxation
58 results
59 role
60 same security
61 scheme
62 security
63 set
64 set of strings
65 short exponents
66 solution
67 strings
68 study
69 subgroups
70 terms
71 transform
72 use
73 values
74 schema:name Secure Hashed Diffie-Hellman over Non-DDH Groups
75 schema:pagination 361-381
76 schema:productId Ne9ce3997d61643b58144e6e140f0fa39
77 Nf1e5028127cd4a778e94510ed7773728
78 schema:publisher N3fb527c62aaf4728972b45a08abef642
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047012120
80 https://doi.org/10.1007/978-3-540-24676-3_22
81 schema:sdDatePublished 2022-05-10T10:44
82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
83 schema:sdPublisher Ncd688665d4b147ef9bcab2e1db2f7e57
84 schema:url https://doi.org/10.1007/978-3-540-24676-3_22
85 sgo:license sg:explorer/license/
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N10484345cf434b38bde576bf2ea14e7e schema:familyName Camenisch
89 schema:givenName Jan L.
90 rdf:type schema:Person
91 N127c29b6b9064180a70b57c1f85c270c rdf:first N10484345cf434b38bde576bf2ea14e7e
92 rdf:rest rdf:nil
93 N3fb527c62aaf4728972b45a08abef642 schema:name Springer Nature
94 rdf:type schema:Organisation
95 N80952b34a55b44c886e30651c14ea4e5 rdf:first sg:person.013004021661.30
96 rdf:rest Nf2295a23ddec4cdaa1e67ee1c042e78a
97 Nba37c452f0a4472a918c742c90ecea75 rdf:first sg:person.013573255563.35
98 rdf:rest N80952b34a55b44c886e30651c14ea4e5
99 Ncaffd6a90b78444ebe80bc0ef16a109e schema:familyName Cachin
100 schema:givenName Christian
101 rdf:type schema:Person
102 Ncd688665d4b147ef9bcab2e1db2f7e57 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 Ncdf22cec3bad4f77a40d3535e3fca4b2 rdf:first Ncaffd6a90b78444ebe80bc0ef16a109e
105 rdf:rest N127c29b6b9064180a70b57c1f85c270c
106 Ne58e21b9dba940b2bb19986497819146 schema:isbn 978-3-540-21935-4
107 978-3-540-24676-3
108 schema:name Advances in Cryptology - EUROCRYPT 2004
109 rdf:type schema:Book
110 Ne9ce3997d61643b58144e6e140f0fa39 schema:name doi
111 schema:value 10.1007/978-3-540-24676-3_22
112 rdf:type schema:PropertyValue
113 Nf1e5028127cd4a778e94510ed7773728 schema:name dimensions_id
114 schema:value pub.1047012120
115 rdf:type schema:PropertyValue
116 Nf2295a23ddec4cdaa1e67ee1c042e78a rdf:first sg:person.015473523512.58
117 rdf:rest rdf:nil
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
122 schema:name Data Format
123 rdf:type schema:DefinedTerm
124 sg:person.013004021661.30 schema:affiliation grid-institutes:grid.481554.9
125 schema:familyName Krawczyk
126 schema:givenName Hugo
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013004021661.30
128 rdf:type schema:Person
129 sg:person.013573255563.35 schema:affiliation grid-institutes:grid.481554.9
130 schema:familyName Gennaro
131 schema:givenName Rosario
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013573255563.35
133 rdf:type schema:Person
134 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
135 schema:familyName Rabin
136 schema:givenName Tal
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
138 rdf:type schema:Person
139 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, New York, USA
140 IBM T.J.Watson Research Center, PO Box 704, 10598, Yorktown Heights, NY, USA
141 schema:name Department of Electrical Engineering, Technion, 32000, Haifa, Israel
142 IBM T.J. Watson Research Center, New York, USA
143 IBM T.J.Watson Research Center, PO Box 704, 10598, Yorktown Heights, NY, USA
144 rdf:type schema:Organization
 




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


...