Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Ueli Maurer , Renato Renner , Clemens Holenstein

ABSTRACT

The goals of this paper are two-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. In contrast to the conventional notion of indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions.Second, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich, and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem. More... »

PAGES

21-39

Book

TITLE

Theory of Cryptography

ISBN

978-3-540-21000-9
978-3-540-24638-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24638-1_2

DOI

http://dx.doi.org/10.1007/978-3-540-24638-1_2

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maurer", 
        "givenName": "Ueli", 
        "id": "sg:person.01316567627.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Renner", 
        "givenName": "Renato", 
        "id": "sg:person.01142624157.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01142624157.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Holenstein", 
        "givenName": "Clemens", 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "The goals of this paper are two-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. In contrast to the conventional notion of indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions.Second, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich, and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.", 
    "editor": [
      {
        "familyName": "Naor", 
        "givenName": "Moni", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24638-1_2", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21000-9", 
        "978-3-540-24638-1"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "random oracle methodology", 
      "main theorem", 
      "irreducibility results", 
      "verifiable criteria", 
      "random oracles", 
      "random strings", 
      "asynchronous beacons", 
      "system U", 
      "related notions", 
      "generalization", 
      "involved systems", 
      "fundamental concepts", 
      "random oracle model", 
      "internal states", 
      "theorem", 
      "oracle model", 
      "indistinguishability", 
      "oracle", 
      "cryptosystem", 
      "system V", 
      "Goldreich", 
      "system", 
      "hash function", 
      "string", 
      "applications", 
      "notion", 
      "parameters", 
      "public parameters", 
      "model", 
      "additional information", 
      "conventional notions", 
      "methodology", 
      "function", 
      "instances", 
      "primitives", 
      "weaker primitives", 
      "state", 
      "two-fold", 
      "possible adversaries", 
      "implementation", 
      "impossibility", 
      "indifferentiability", 
      "adversary", 
      "beacons", 
      "concept", 
      "criteria", 
      "results", 
      "reducibility", 
      "information", 
      "Halevi", 
      "Canetti", 
      "goal", 
      "family", 
      "setting", 
      "reduction", 
      "contrast", 
      "access", 
      "members", 
      "paper"
    ], 
    "name": "Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology", 
    "pagination": "21-39", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050815296"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24638-1_2"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24638-1_2", 
      "https://app.dimensions.ai/details/publication/pub.1050815296"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_163.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24638-1_2"
  }
]
 

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-24638-1_2'

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-24638-1_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24638-1_2'

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-24638-1_2'


 

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

131 TRIPLES      22 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24638-1_2 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N93943208f22b4f7f96ed0a0432af2519
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description The goals of this paper are two-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. In contrast to the conventional notion of indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions.Second, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich, and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.
7 schema:editor Nbedf355737d040c3b21c25c49bfdce71
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nebbea63911234bf8a45a0ca0a6628ea6
11 schema:keywords Canetti
12 Goldreich
13 Halevi
14 access
15 additional information
16 adversary
17 applications
18 asynchronous beacons
19 beacons
20 concept
21 contrast
22 conventional notions
23 criteria
24 cryptosystem
25 family
26 function
27 fundamental concepts
28 generalization
29 goal
30 hash function
31 implementation
32 impossibility
33 indifferentiability
34 indistinguishability
35 information
36 instances
37 internal states
38 involved systems
39 irreducibility results
40 main theorem
41 members
42 methodology
43 model
44 notion
45 oracle
46 oracle model
47 paper
48 parameters
49 possible adversaries
50 primitives
51 public parameters
52 random oracle methodology
53 random oracle model
54 random oracles
55 random strings
56 reducibility
57 reduction
58 related notions
59 results
60 setting
61 state
62 string
63 system
64 system U
65 system V
66 theorem
67 two-fold
68 verifiable criteria
69 weaker primitives
70 schema:name Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
71 schema:pagination 21-39
72 schema:productId N2f1f67465f064c0cb5ff3a2fa2f3180e
73 Nbb38a0db157749d1b6f2f013d56eabe7
74 schema:publisher N770d6d876e36478bb8d478a4feb2383a
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050815296
76 https://doi.org/10.1007/978-3-540-24638-1_2
77 schema:sdDatePublished 2022-11-24T21:12
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher Ndcffe416816449dd8f9dfbe86d55e572
80 schema:url https://doi.org/10.1007/978-3-540-24638-1_2
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N1ff5ee7797d14736a23e581bf9c778a8 rdf:first Nbbd8f4b715dc4b479147589263673f74
85 rdf:rest rdf:nil
86 N2f1f67465f064c0cb5ff3a2fa2f3180e schema:name doi
87 schema:value 10.1007/978-3-540-24638-1_2
88 rdf:type schema:PropertyValue
89 N770d6d876e36478bb8d478a4feb2383a schema:name Springer Nature
90 rdf:type schema:Organisation
91 N93943208f22b4f7f96ed0a0432af2519 rdf:first sg:person.01316567627.91
92 rdf:rest Ne5759fa984fa4ff0a46221788e74bcfd
93 Nbb38a0db157749d1b6f2f013d56eabe7 schema:name dimensions_id
94 schema:value pub.1050815296
95 rdf:type schema:PropertyValue
96 Nbbd8f4b715dc4b479147589263673f74 schema:affiliation grid-institutes:grid.5801.c
97 schema:familyName Holenstein
98 schema:givenName Clemens
99 rdf:type schema:Person
100 Nbedf355737d040c3b21c25c49bfdce71 rdf:first Nfb33be46f2c34be0b147986f173f3375
101 rdf:rest rdf:nil
102 Ndcffe416816449dd8f9dfbe86d55e572 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 Ne5759fa984fa4ff0a46221788e74bcfd rdf:first sg:person.01142624157.34
105 rdf:rest N1ff5ee7797d14736a23e581bf9c778a8
106 Nebbea63911234bf8a45a0ca0a6628ea6 schema:isbn 978-3-540-21000-9
107 978-3-540-24638-1
108 schema:name Theory of Cryptography
109 rdf:type schema:Book
110 Nfb33be46f2c34be0b147986f173f3375 schema:familyName Naor
111 schema:givenName Moni
112 rdf:type schema:Person
113 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
114 schema:name Mathematical Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
117 schema:name Statistics
118 rdf:type schema:DefinedTerm
119 sg:person.01142624157.34 schema:affiliation grid-institutes:grid.5801.c
120 schema:familyName Renner
121 schema:givenName Renato
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01142624157.34
123 rdf:type schema:Person
124 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
125 schema:familyName Maurer
126 schema:givenName Ueli
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
128 rdf:type schema:Person
129 grid-institutes:grid.5801.c schema:alternateName Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland
130 schema:name Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland
131 rdf:type schema:Organization
 




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


...