Seven-Property-Preserving Iterated Hashing: ROX View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007-01-01

AUTHORS

Elena Andreeva , Gregory Neven , Bart Preneel , Thomas Shrimpton

ABSTRACT

Nearly all modern hash functions are constructed by iterating a compression function. At FSE’04, Rogaway and Shrimpton [28] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study points out that none of them preserves more than three notions from [28]. As a second contribution, we propose the new Random-Oracle XOR (ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times. More... »

PAGES

130-146

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-76900-2_8

DOI

http://dx.doi.org/10.1007/978-3-540-76900-2_8

DIMENSIONS

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


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": "SCD-COSIC, Dept.\u00a0of Electrical Engineering, Katholieke Universiteit Leuven", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "SCD-COSIC, Dept.\u00a0of Electrical Engineering, Katholieke Universiteit Leuven"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Andreeva", 
        "givenName": "Elena", 
        "id": "sg:person.010624232445.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010624232445.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "D\u00e9partement d\u2019Informatique, Ecole Normale Sup\u00e9rieure", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "SCD-COSIC, Dept.\u00a0of Electrical Engineering, Katholieke Universiteit Leuven", 
            "D\u00e9partement d\u2019Informatique, Ecole Normale Sup\u00e9rieure"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Neven", 
        "givenName": "Gregory", 
        "id": "sg:person.07516544401.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07516544401.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "SCD-COSIC, Dept.\u00a0of Electrical Engineering, Katholieke Universiteit Leuven", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "SCD-COSIC, Dept.\u00a0of Electrical Engineering, Katholieke Universiteit Leuven"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "id": "sg:person.011115044357.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Informatics, University of Lugano", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Dept.\u00a0of Computer Science, Portland State University", 
            "Faculty of Informatics, University of Lugano"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shrimpton", 
        "givenName": "Thomas", 
        "id": "sg:person.015267205523.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015267205523.60"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "Nearly all modern hash functions are constructed by iterating a compression function. At FSE\u201904, Rogaway and Shrimpton [28] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study points out that none of them preserves more than three notions from [28]. As a second contribution, we propose the new Random-Oracle XOR (ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170\u00a0bits) that is called only a logarithmic number of times.", 
    "editor": [
      {
        "familyName": "Kurosawa", 
        "givenName": "Kaoru", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-76900-2_8", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-76899-9", 
        "978-3-540-76900-2"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2007", 
      "type": "Book"
    }, 
    "keywords": [
      "random oracles", 
      "iteration", 
      "logarithmic number", 
      "main contribution", 
      "second contribution", 
      "hash function", 
      "oracle", 
      "counterexamples", 
      "function", 
      "notion", 
      "proof", 
      "collision resistance", 
      "compression function", 
      "security notions", 
      "contribution", 
      "number", 
      "Rogaway", 
      "second preimage resistance", 
      "time", 
      "variants", 
      "preimage resistance", 
      "Shrimpton", 
      "study", 
      "resistance", 
      "ROX", 
      "paper"
    ], 
    "name": "Seven-Property-Preserving Iterated Hashing: ROX", 
    "pagination": "130-146", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049072174"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-76900-2_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-76900-2_8", 
      "https://app.dimensions.ai/details/publication/pub.1049072174"
    ], 
    "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_104.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-76900-2_8"
  }
]
 

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-76900-2_8'

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-76900-2_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-76900-2_8'

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-76900-2_8'


 

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

113 TRIPLES      22 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-76900-2_8 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N6a95f3eceedb4ac7a2ad699cbea457c1
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description Nearly all modern hash functions are constructed by iterating a compression function. At FSE’04, Rogaway and Shrimpton [28] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study points out that none of them preserves more than three notions from [28]. As a second contribution, we propose the new Random-Oracle XOR (ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times.
7 schema:editor N85dc9c57b6ca475d800317717638fada
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N53f2f8a311b54db2b5c10f356df5a7f3
11 schema:keywords ROX
12 Rogaway
13 Shrimpton
14 collision resistance
15 compression function
16 contribution
17 counterexamples
18 function
19 hash function
20 iteration
21 logarithmic number
22 main contribution
23 notion
24 number
25 oracle
26 paper
27 preimage resistance
28 proof
29 random oracles
30 resistance
31 second contribution
32 second preimage resistance
33 security notions
34 study
35 time
36 variants
37 schema:name Seven-Property-Preserving Iterated Hashing: ROX
38 schema:pagination 130-146
39 schema:productId Nb1ab49ef97494ceb95b2d2b592f79196
40 Ne1c719d1f9594187ace68f5a8b27dabc
41 schema:publisher Ne3090904464f4bcc87a93a7da08ae16a
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049072174
43 https://doi.org/10.1007/978-3-540-76900-2_8
44 schema:sdDatePublished 2022-12-01T06:46
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher Nc82f0a11dfff4c75a1c89b7131eb26e3
47 schema:url https://doi.org/10.1007/978-3-540-76900-2_8
48 sgo:license sg:explorer/license/
49 sgo:sdDataset chapters
50 rdf:type schema:Chapter
51 N1544484746664b6fba82ad7d34a9aba1 rdf:first sg:person.011115044357.39
52 rdf:rest Nc14c6f62b13344a7860379fe26f3cf3f
53 N4b6543e1ae4f45788cf694c0613ff2fb schema:familyName Kurosawa
54 schema:givenName Kaoru
55 rdf:type schema:Person
56 N53f2f8a311b54db2b5c10f356df5a7f3 schema:isbn 978-3-540-76899-9
57 978-3-540-76900-2
58 schema:name Advances in Cryptology – ASIACRYPT 2007
59 rdf:type schema:Book
60 N6a95f3eceedb4ac7a2ad699cbea457c1 rdf:first sg:person.010624232445.91
61 rdf:rest Neb0ec747863a4672b8570cabb13a83fc
62 N85dc9c57b6ca475d800317717638fada rdf:first N4b6543e1ae4f45788cf694c0613ff2fb
63 rdf:rest rdf:nil
64 Nb1ab49ef97494ceb95b2d2b592f79196 schema:name doi
65 schema:value 10.1007/978-3-540-76900-2_8
66 rdf:type schema:PropertyValue
67 Nc14c6f62b13344a7860379fe26f3cf3f rdf:first sg:person.015267205523.60
68 rdf:rest rdf:nil
69 Nc82f0a11dfff4c75a1c89b7131eb26e3 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 Ne1c719d1f9594187ace68f5a8b27dabc schema:name dimensions_id
72 schema:value pub.1049072174
73 rdf:type schema:PropertyValue
74 Ne3090904464f4bcc87a93a7da08ae16a schema:name Springer Nature
75 rdf:type schema:Organisation
76 Neb0ec747863a4672b8570cabb13a83fc rdf:first sg:person.07516544401.59
77 rdf:rest N1544484746664b6fba82ad7d34a9aba1
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
82 schema:name Data Format
83 rdf:type schema:DefinedTerm
84 sg:person.010624232445.91 schema:affiliation grid-institutes:grid.5596.f
85 schema:familyName Andreeva
86 schema:givenName Elena
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010624232445.91
88 rdf:type schema:Person
89 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.5596.f
90 schema:familyName Preneel
91 schema:givenName Bart
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
93 rdf:type schema:Person
94 sg:person.015267205523.60 schema:affiliation grid-institutes:None
95 schema:familyName Shrimpton
96 schema:givenName Thomas
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015267205523.60
98 rdf:type schema:Person
99 sg:person.07516544401.59 schema:affiliation grid-institutes:None
100 schema:familyName Neven
101 schema:givenName Gregory
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07516544401.59
103 rdf:type schema:Person
104 grid-institutes:None schema:alternateName Département d’Informatique, Ecole Normale Supérieure
105 Faculty of Informatics, University of Lugano
106 schema:name Dept. of Computer Science, Portland State University
107 Département d’Informatique, Ecole Normale Supérieure
108 Faculty of Informatics, University of Lugano
109 SCD-COSIC, Dept. of Electrical Engineering, Katholieke Universiteit Leuven
110 rdf:type schema:Organization
111 grid-institutes:grid.5596.f schema:alternateName SCD-COSIC, Dept. of Electrical Engineering, Katholieke Universiteit Leuven
112 schema:name SCD-COSIC, Dept. of Electrical Engineering, Katholieke Universiteit Leuven
113 rdf:type schema:Organization
 




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


...