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 Nf219b2616e504b319803a50c36599266
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 N917ce9c69e47461fba9623a6baa0b091
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N5ec2c7721ab54f6daaedbada447cfa94
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 Na8469ac3fb6e4aa4aa59e402b499aa74
40 Nd3577983c7414de087d3332db51d9bbf
41 schema:publisher Nff6caa9eb1244d02adcca0c076974473
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 Nc7e69b88be744bf2ac29a41edca6a34c
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 N35486e11224148e5a5f8109340e2abc9 schema:familyName Kurosawa
52 schema:givenName Kaoru
53 rdf:type schema:Person
54 N3cde284a64514e1997dbc843cabf76ad rdf:first sg:person.07516544401.59
55 rdf:rest Nf933e24ac0ae4c11aa215afb974b49ee
56 N5ec2c7721ab54f6daaedbada447cfa94 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 N917ce9c69e47461fba9623a6baa0b091 rdf:first N35486e11224148e5a5f8109340e2abc9
61 rdf:rest rdf:nil
62 Na8469ac3fb6e4aa4aa59e402b499aa74 schema:name dimensions_id
63 schema:value pub.1049072174
64 rdf:type schema:PropertyValue
65 Nc7e69b88be744bf2ac29a41edca6a34c schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nd3577983c7414de087d3332db51d9bbf schema:name doi
68 schema:value 10.1007/978-3-540-76900-2_8
69 rdf:type schema:PropertyValue
70 Ne9d83f7170dc47a89092e7893f97afca rdf:first sg:person.015267205523.60
71 rdf:rest rdf:nil
72 Nf219b2616e504b319803a50c36599266 rdf:first sg:person.010624232445.91
73 rdf:rest N3cde284a64514e1997dbc843cabf76ad
74 Nf933e24ac0ae4c11aa215afb974b49ee rdf:first sg:person.011115044357.39
75 rdf:rest Ne9d83f7170dc47a89092e7893f97afca
76 Nff6caa9eb1244d02adcca0c076974473 schema:name Springer Nature
77 rdf:type schema:Organisation
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)


...