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 N1dd76b77f5e744a6984205bad8783e95
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 Nb173a36dbd284dc781a593ebe3823629
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N8d0b0ca267ef48898104e7b4a6aa2d1e
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 N8abb1ab3b4754e3f9b852a05dbcc89ea
54 Nc9eb7480a039403c97406a2ad8d86a04
55 schema:publisher N1f40ead03a894e529f19c005294d19a6
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 N7429210e81d942958424b4a05e5ba52d
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 N1dd76b77f5e744a6984205bad8783e95 rdf:first sg:person.016521211021.12
66 rdf:rest rdf:nil
67 N1f40ead03a894e529f19c005294d19a6 schema:name Springer Nature
68 rdf:type schema:Organisation
69 N4775b7350e8d4ade87ae1a2814c50068 schema:familyName Brassard
70 schema:givenName Gilles
71 rdf:type schema:Person
72 N7429210e81d942958424b4a05e5ba52d schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N8abb1ab3b4754e3f9b852a05dbcc89ea schema:name doi
75 schema:value 10.1007/0-387-34805-0_39
76 rdf:type schema:PropertyValue
77 N8d0b0ca267ef48898104e7b4a6aa2d1e 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 Nb173a36dbd284dc781a593ebe3823629 rdf:first N4775b7350e8d4ade87ae1a2814c50068
82 rdf:rest rdf:nil
83 Nc9eb7480a039403c97406a2ad8d86a04 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)


...