A Design Principle for Hash Functions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1990

AUTHORS

Ivan Bjerre Damgård

ABSTRACT

We show that if there exists a computationally collision free function f from m bits to t bits where m > t, then there exists a computationally collision free function h mapping messages of arbitrary polynomial lengths to t-bit strings.Let n be the length of the message. h can be constructed either such that it can be evaluated in time linear in n using 1 processor, or such that it takes time O(log(n)) using O(n) processors, counting evaluations of f as one step. Finally, for any constant k and large n, a speedup by a factor of k over the first construction is available using k processors.Apart from suggesting a generally sound design principle for hash functions, our results give a unified view of several apparently unrelated constructions of hash functions proposed earlier. It also suggests changes to other proposed constructions to make a proof of security potentially easier.We give three concrete examples of constructions, based on modular squaring, on Wolfram’s pseudoranddom bit generator [Wo], and on the knapsack problem. More... »

PAGES

416-427

Book

TITLE

Advances in Cryptology — CRYPTO’ 89 Proceedings

ISBN

978-0-387-97317-3
978-0-387-34805-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/0-387-34805-0_39

DOI

http://dx.doi.org/10.1007/0-387-34805-0_39

DIMENSIONS

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


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": [
      {
        "familyName": "Damg\u00e5rd", 
        "givenName": "Ivan Bjerre", 
        "id": "sg:person.016521211021.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016521211021.12"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1990", 
    "datePublishedReg": "1990-01-01", 
    "description": "We show that if there exists a computationally collision free function f from m bits to t bits where m > t, then there exists a computationally collision free function h mapping messages of arbitrary polynomial lengths to t-bit strings.Let n be the length of the message. h can be constructed either such that it can be evaluated in time linear in n using 1 processor, or such that it takes time O(log(n)) using O(n) processors, counting evaluations of f as one step. Finally, for any constant k and large n, a speedup by a factor of k over the first construction is available using k processors.Apart from suggesting a generally sound design principle for hash functions, our results give a unified view of several apparently unrelated constructions of hash functions proposed earlier. It also suggests changes to other proposed constructions to make a proof of security potentially easier.We give three concrete examples of constructions, based on modular squaring, on Wolfram\u2019s pseudoranddom bit generator [Wo], and on the knapsack problem.", 
    "editor": [
      {
        "familyName": "Brassard", 
        "givenName": "Gilles", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/0-387-34805-0_39", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-0-387-97317-3", 
        "978-0-387-34805-6"
      ], 
      "name": "Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings", 
      "type": "Book"
    }, 
    "keywords": [
      "hash function", 
      "proof of security", 
      "sound design principles", 
      "design principles", 
      "K processors", 
      "modular squaring", 
      "knapsack problem", 
      "t bits", 
      "processors", 
      "unified view", 
      "first construction", 
      "time linear", 
      "bit generator", 
      "polynomial length", 
      "mapping messages", 
      "messages", 
      "bits", 
      "concrete examples", 
      "speedup", 
      "security", 
      "construction", 
      "squaring", 
      "proof", 
      "string", 
      "principles", 
      "unrelated constructions", 
      "example", 
      "step", 
      "generator", 
      "view", 
      "evaluation", 
      "function", 
      "function f", 
      "time", 
      "results", 
      "linear", 
      "length", 
      "factors", 
      "changes", 
      "problem"
    ], 
    "name": "A Design Principle for Hash Functions", 
    "pagination": "416-427", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026402674"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/0-387-34805-0_39"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/0-387-34805-0_39", 
      "https://app.dimensions.ai/details/publication/pub.1026402674"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_106.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/0-387-34805-0_39"
  }
]
 

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/0-387-34805-0_39'

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/0-387-34805-0_39'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/0-387-34805-0_39'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/0-387-34805-0_39'


 

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

95 TRIPLES      22 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/0-387-34805-0_39 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd47a46244ebd47e48007edb2e35c8528
4 schema:datePublished 1990
5 schema:datePublishedReg 1990-01-01
6 schema:description We show that if there exists a computationally collision free function f from m bits to t bits where m > t, then there exists a computationally collision free function h mapping messages of arbitrary polynomial lengths to t-bit strings.Let n be the length of the message. h can be constructed either such that it can be evaluated in time linear in n using 1 processor, or such that it takes time O(log(n)) using O(n) processors, counting evaluations of f as one step. Finally, for any constant k and large n, a speedup by a factor of k over the first construction is available using k processors.Apart from suggesting a generally sound design principle for hash functions, our results give a unified view of several apparently unrelated constructions of hash functions proposed earlier. It also suggests changes to other proposed constructions to make a proof of security potentially easier.We give three concrete examples of constructions, based on modular squaring, on Wolfram’s pseudoranddom bit generator [Wo], and on the knapsack problem.
7 schema:editor N567475dd37ae48709f89900628f75b81
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nd1cdb18a8fcb4979833e6d290e00762b
11 schema:keywords K processors
12 bit generator
13 bits
14 changes
15 concrete examples
16 construction
17 design principles
18 evaluation
19 example
20 factors
21 first construction
22 function
23 function f
24 generator
25 hash function
26 knapsack problem
27 length
28 linear
29 mapping messages
30 messages
31 modular squaring
32 polynomial length
33 principles
34 problem
35 processors
36 proof
37 proof of security
38 results
39 security
40 sound design principles
41 speedup
42 squaring
43 step
44 string
45 t bits
46 time
47 time linear
48 unified view
49 unrelated constructions
50 view
51 schema:name A Design Principle for Hash Functions
52 schema:pagination 416-427
53 schema:productId N4ec717f72296405598a8cdf00b4768c5
54 Ndf625d851ea84ff8a636e71d3fab7338
55 schema:publisher N523817ee5a8043f99ea707c942dc034a
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026402674
57 https://doi.org/10.1007/0-387-34805-0_39
58 schema:sdDatePublished 2022-12-01T06:46
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher Naa3e44e659ce4830bd059d23c0cb77c5
61 schema:url https://doi.org/10.1007/0-387-34805-0_39
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N064a7247d2c84b2281c87bbc84977c37 schema:familyName Brassard
66 schema:givenName Gilles
67 rdf:type schema:Person
68 N4ec717f72296405598a8cdf00b4768c5 schema:name doi
69 schema:value 10.1007/0-387-34805-0_39
70 rdf:type schema:PropertyValue
71 N523817ee5a8043f99ea707c942dc034a schema:name Springer Nature
72 rdf:type schema:Organisation
73 N567475dd37ae48709f89900628f75b81 rdf:first N064a7247d2c84b2281c87bbc84977c37
74 rdf:rest rdf:nil
75 Naa3e44e659ce4830bd059d23c0cb77c5 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 Nd1cdb18a8fcb4979833e6d290e00762b schema:isbn 978-0-387-34805-6
78 978-0-387-97317-3
79 schema:name Advances in Cryptology — CRYPTO’ 89 Proceedings
80 rdf:type schema:Book
81 Nd47a46244ebd47e48007edb2e35c8528 rdf:first sg:person.016521211021.12
82 rdf:rest rdf:nil
83 Ndf625d851ea84ff8a636e71d3fab7338 schema:name dimensions_id
84 schema:value pub.1026402674
85 rdf:type schema:PropertyValue
86 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
87 schema:name Information and Computing Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
90 schema:name Computation Theory and Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.016521211021.12 schema:familyName Damgård
93 schema:givenName Ivan Bjerre
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016521211021.12
95 rdf:type schema:Person
 




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


...