The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Nir Bitansky , Ran Canetti , Henry Cohn , Shafi Goldwasser , Yael Tauman Kalai , Omer Paneth , Alon Rosen

ABSTRACT

In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies:The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated.The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy.These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005). More... »

PAGES

71-89

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-44381-1_5

DOI

http://dx.doi.org/10.1007/978-3-662-44381-1_5

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tel Aviv University, Tel Aviv, Israel", 
          "id": "http://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Tel Aviv University, Tel Aviv, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bitansky", 
        "givenName": "Nir", 
        "id": "sg:person.016302552357.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Boston University, Boston, USA", 
          "id": "http://www.grid.ac/institutes/grid.189504.1", 
          "name": [
            "Tel Aviv University, Tel Aviv, Israel", 
            "Boston University, Boston, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Canetti", 
        "givenName": "Ran", 
        "id": "sg:person.012320111457.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research New England, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cohn", 
        "givenName": "Henry", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Massachusetts Institute of Technology, Cambridge, USA", 
            "Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goldwasser", 
        "givenName": "Shafi", 
        "id": "sg:person.010651111361.51", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010651111361.51"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research New England, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kalai", 
        "givenName": "Yael Tauman", 
        "id": "sg:person.015074540743.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074540743.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Boston University, Boston, USA", 
          "id": "http://www.grid.ac/institutes/grid.189504.1", 
          "name": [
            "Boston University, Boston, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paneth", 
        "givenName": "Omer", 
        "id": "sg:person.014073524511.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IDC Herzliya, Herzliya, Israel", 
          "id": "http://www.grid.ac/institutes/grid.21166.32", 
          "name": [
            "IDC Herzliya, Herzliya, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rosen", 
        "givenName": "Alon", 
        "id": "sg:person.016463202715.80", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016463202715.80"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies:The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated.The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy.These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005).", 
    "editor": [
      {
        "familyName": "Garay", 
        "givenName": "Juan A.", 
        "type": "Person"
      }, 
      {
        "familyName": "Gennaro", 
        "givenName": "Rosario", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-44381-1_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-44380-4", 
        "978-3-662-44381-1"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2014", 
      "type": "Book"
    }, 
    "keywords": [
      "virtual black box obfuscation", 
      "universal simulator", 
      "auxiliary input", 
      "impossibility results", 
      "strong impossibility results", 
      "indistinguishability obfuscation", 
      "obfuscation", 
      "simulator", 
      "Goldwasser", 
      "general circuits", 
      "input", 
      "circuit family", 
      "Kalai", 
      "bounds", 
      "impossibility", 
      "results", 
      "circuit", 
      "family", 
      "paper"
    ], 
    "name": "The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator", 
    "pagination": "71-89", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040657539"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-44381-1_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-44381-1_5", 
      "https://app.dimensions.ai/details/publication/pub.1040657539"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:36", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_460.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-44381-1_5"
  }
]
 

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-662-44381-1_5'

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-662-44381-1_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-44381-1_5'

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-662-44381-1_5'


 

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

139 TRIPLES      23 PREDICATES      45 URIs      38 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-44381-1_5 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N25da0a975efe4254a5951fa2ab534bd2
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description In this paper we show that indistinguishability obfuscation for general circuits implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, it implies:The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy (for example, many cryptographic primitives). Impossibility holds even when the auxiliary input depends only on the public circuit family, and not which circuit in the family is being obfuscated.The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy.These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (FOCS 2005).
7 schema:editor Na3354b398069432897bd99ae0b9fe238
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N5747e9cf673a496ab6c9b726145c9fc2
12 schema:keywords Goldwasser
13 Kalai
14 auxiliary input
15 bounds
16 circuit
17 circuit family
18 family
19 general circuits
20 impossibility
21 impossibility results
22 indistinguishability obfuscation
23 input
24 obfuscation
25 paper
26 results
27 simulator
28 strong impossibility results
29 universal simulator
30 virtual black box obfuscation
31 schema:name The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator
32 schema:pagination 71-89
33 schema:productId N0cfdb1ee8e52423f88e3a39029180e5f
34 N763d7d81091545bf9cd4e4388503268c
35 schema:publisher N5dd7922142a2427280056d3c8efd2fa3
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040657539
37 https://doi.org/10.1007/978-3-662-44381-1_5
38 schema:sdDatePublished 2022-06-01T22:36
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher N92f3dc9877354011a7424071443e772d
41 schema:url https://doi.org/10.1007/978-3-662-44381-1_5
42 sgo:license sg:explorer/license/
43 sgo:sdDataset chapters
44 rdf:type schema:Chapter
45 N0cfdb1ee8e52423f88e3a39029180e5f schema:name doi
46 schema:value 10.1007/978-3-662-44381-1_5
47 rdf:type schema:PropertyValue
48 N25da0a975efe4254a5951fa2ab534bd2 rdf:first sg:person.016302552357.74
49 rdf:rest N45e191bde0a74816962278d77c812c75
50 N2b9e12f2c68b4c7aa07b67cd67ea7019 rdf:first sg:person.016463202715.80
51 rdf:rest rdf:nil
52 N45e191bde0a74816962278d77c812c75 rdf:first sg:person.012320111457.74
53 rdf:rest Nbe034b5cb06a4c72a4e8d19030a435cb
54 N4bfde1f34b0d4b788f20a76ff3b53a29 rdf:first sg:person.010651111361.51
55 rdf:rest N7d311860439e4cb098552994e2b80d9c
56 N4e574b66bedb41d0bcb927d705d1b413 schema:familyName Garay
57 schema:givenName Juan A.
58 rdf:type schema:Person
59 N562dfc9d7fdf4558ac49da07fcc66662 rdf:first sg:person.014073524511.68
60 rdf:rest N2b9e12f2c68b4c7aa07b67cd67ea7019
61 N5747e9cf673a496ab6c9b726145c9fc2 schema:isbn 978-3-662-44380-4
62 978-3-662-44381-1
63 schema:name Advances in Cryptology – CRYPTO 2014
64 rdf:type schema:Book
65 N5dd7922142a2427280056d3c8efd2fa3 schema:name Springer Nature
66 rdf:type schema:Organisation
67 N763d7d81091545bf9cd4e4388503268c schema:name dimensions_id
68 schema:value pub.1040657539
69 rdf:type schema:PropertyValue
70 N7d311860439e4cb098552994e2b80d9c rdf:first sg:person.015074540743.62
71 rdf:rest N562dfc9d7fdf4558ac49da07fcc66662
72 N92f3dc9877354011a7424071443e772d schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Na3354b398069432897bd99ae0b9fe238 rdf:first N4e574b66bedb41d0bcb927d705d1b413
75 rdf:rest Ncca8a42505d74d2783c0fe3cdf896904
76 Nbe034b5cb06a4c72a4e8d19030a435cb rdf:first Ne6f4b63e90df45dcaf6e8fc1553ac1fa
77 rdf:rest N4bfde1f34b0d4b788f20a76ff3b53a29
78 Ncca8a42505d74d2783c0fe3cdf896904 rdf:first Ncddc1c868c6e4c38b2e72d3206f834db
79 rdf:rest rdf:nil
80 Ncddc1c868c6e4c38b2e72d3206f834db schema:familyName Gennaro
81 schema:givenName Rosario
82 rdf:type schema:Person
83 Ne6f4b63e90df45dcaf6e8fc1553ac1fa schema:affiliation grid-institutes:grid.419815.0
84 schema:familyName Cohn
85 schema:givenName Henry
86 rdf:type schema:Person
87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
88 schema:name Information and Computing Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
91 schema:name Artificial Intelligence and Image Processing
92 rdf:type schema:DefinedTerm
93 sg:person.010651111361.51 schema:affiliation grid-institutes:grid.13992.30
94 schema:familyName Goldwasser
95 schema:givenName Shafi
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010651111361.51
97 rdf:type schema:Person
98 sg:person.012320111457.74 schema:affiliation grid-institutes:grid.189504.1
99 schema:familyName Canetti
100 schema:givenName Ran
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74
102 rdf:type schema:Person
103 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.189504.1
104 schema:familyName Paneth
105 schema:givenName Omer
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
107 rdf:type schema:Person
108 sg:person.015074540743.62 schema:affiliation grid-institutes:grid.419815.0
109 schema:familyName Kalai
110 schema:givenName Yael Tauman
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074540743.62
112 rdf:type schema:Person
113 sg:person.016302552357.74 schema:affiliation grid-institutes:grid.12136.37
114 schema:familyName Bitansky
115 schema:givenName Nir
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74
117 rdf:type schema:Person
118 sg:person.016463202715.80 schema:affiliation grid-institutes:grid.21166.32
119 schema:familyName Rosen
120 schema:givenName Alon
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016463202715.80
122 rdf:type schema:Person
123 grid-institutes:grid.12136.37 schema:alternateName Tel Aviv University, Tel Aviv, Israel
124 schema:name Tel Aviv University, Tel Aviv, Israel
125 rdf:type schema:Organization
126 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
127 schema:name Massachusetts Institute of Technology, Cambridge, USA
128 Weizmann Institute of Science, Rehovot, Israel
129 rdf:type schema:Organization
130 grid-institutes:grid.189504.1 schema:alternateName Boston University, Boston, USA
131 schema:name Boston University, Boston, USA
132 Tel Aviv University, Tel Aviv, Israel
133 rdf:type schema:Organization
134 grid-institutes:grid.21166.32 schema:alternateName IDC Herzliya, Herzliya, Israel
135 schema:name IDC Herzliya, Herzliya, Israel
136 rdf:type schema:Organization
137 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research New England, Cambridge, USA
138 schema:name Microsoft Research New England, Cambridge, USA
139 rdf:type schema:Organization
 




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


...