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 Na080d5d6ef31493e9ede1bea3567e9fa
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 N280f8b0d3699423c8ef10bc10442201a
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N298c95df8c3041b4b93c27dbc069c28a
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 N7064290cfff74558aadfc2d92cb76f8f
73 Nfad3280de3bf432b9fce88324401828c
74 schema:publisher N556ba5994f034e0a940a3a268c24939a
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 Nd48f0e23022642bcb06465ff10505ae8
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 N0ac6b5632d4447d4bff812933f28a2d7 rdf:first N34b12d0e8d7c483bb579b08e70083bef
85 rdf:rest rdf:nil
86 N280f8b0d3699423c8ef10bc10442201a rdf:first N9b127752e9ae4a518ebcb7b6780d8557
87 rdf:rest rdf:nil
88 N298c95df8c3041b4b93c27dbc069c28a schema:isbn 978-3-540-21000-9
89 978-3-540-24638-1
90 schema:name Theory of Cryptography
91 rdf:type schema:Book
92 N34b12d0e8d7c483bb579b08e70083bef schema:affiliation grid-institutes:grid.5801.c
93 schema:familyName Holenstein
94 schema:givenName Clemens
95 rdf:type schema:Person
96 N556ba5994f034e0a940a3a268c24939a schema:name Springer Nature
97 rdf:type schema:Organisation
98 N7064290cfff74558aadfc2d92cb76f8f schema:name dimensions_id
99 schema:value pub.1050815296
100 rdf:type schema:PropertyValue
101 N9b127752e9ae4a518ebcb7b6780d8557 schema:familyName Naor
102 schema:givenName Moni
103 rdf:type schema:Person
104 Na080d5d6ef31493e9ede1bea3567e9fa rdf:first sg:person.01316567627.91
105 rdf:rest Nd4a2ed06f7c44d41bccb73dc0d6426cd
106 Nd48f0e23022642bcb06465ff10505ae8 schema:name Springer Nature - SN SciGraph project
107 rdf:type schema:Organization
108 Nd4a2ed06f7c44d41bccb73dc0d6426cd rdf:first sg:person.01142624157.34
109 rdf:rest N0ac6b5632d4447d4bff812933f28a2d7
110 Nfad3280de3bf432b9fce88324401828c schema:name doi
111 schema:value 10.1007/978-3-540-24638-1_2
112 rdf:type schema:PropertyValue
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)


...