Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-07-21

AUTHORS

Prabhanjan Ananth , Aayush Jain , Moni Naor , Amit Sahai , Eylon Yogev

ABSTRACT

Over the last few years a new breed of cryptographic primitives has arisen: on one hand they have previously unimagined utility and on the other hand they are not based on simple to state and tried out assumptions. With the on-going study of these primitives, we are left with several different candidate constructions each based on a different, not easy to express, mathematical assumptions, where some even turn out to be insecure.A combiner for a cryptographic primitive takes several candidate constructions of the primitive and outputs one construction that is as good as any of the input constructions. Furthermore, this combiner must be efficient: the resulting construction should remain polynomial-time even when combining polynomially many candidate. Combiners are especially important for a primitive where there are several competing constructions whose security is hard to evaluate, as is the case for indistinguishability obfuscation (IO) and witness encryption (WE).One place where the need for combiners appears is in design of a universal construction, where one wishes to find “one construction to rule them all”: an explicit construction that is secure if any construction of the primitive exists.In a recent paper, Goldwasser and Kalai posed as a challenge finding universal constructions for indistinguishability obfuscation and witness encryption. In this work we resolve this issue: we construct universal schemes for IO, and for witness encryption, and also resolve the existence of combiners for these primitives along the way. For IO, our universal construction and combiners can be built based on either assuming DDH, or assuming LWE, with security against subexponential adversaries. For witness encryption, we need only one-way functions secure against polynomial time adversaries. More... »

PAGES

491-520

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53008-5_17

DOI

http://dx.doi.org/10.1007/978-3-662-53008-5_17

DIMENSIONS

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


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": "Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ananth", 
        "givenName": "Prabhanjan", 
        "id": "sg:person.012042213735.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012042213735.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jain", 
        "givenName": "Aayush", 
        "id": "sg:person.016700260675.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016700260675.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "id": "sg:person.014324616157.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014324616157.64"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yogev", 
        "givenName": "Eylon", 
        "id": "sg:person.015120037757.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-07-21", 
    "datePublishedReg": "2016-07-21", 
    "description": "Over the last few years a new breed of cryptographic primitives has arisen: on one hand they have previously unimagined utility and on the other hand they are not based on simple to state and tried out assumptions. With the on-going study of these primitives, we are left with several different candidate constructions each based on a different, not easy to express, mathematical assumptions, where some even turn out to be insecure.A combiner for a cryptographic primitive takes several candidate constructions of the primitive and outputs one construction that is as good as any of the input constructions. Furthermore, this combiner must be efficient: the resulting construction should remain polynomial-time even when combining polynomially many candidate. Combiners are especially important for a primitive where there are several competing constructions whose security is hard to evaluate, as is the case for indistinguishability obfuscation (IO) and witness encryption (WE).One place where the need for combiners appears is in design of a universal construction, where one wishes to find \u201cone construction to rule them all\u201d: an explicit construction that is secure if any construction of the primitive exists.In a recent paper, Goldwasser and Kalai posed as a challenge finding universal constructions for indistinguishability obfuscation and witness encryption. In this work we resolve this issue: we construct universal schemes for IO, and for witness encryption, and also resolve the existence of combiners for these primitives along the way. For IO, our universal construction and combiners can be built based on either assuming DDH, or assuming LWE, with security against subexponential adversaries. For witness encryption, we need only one-way functions secure against polynomial time adversaries.", 
    "editor": [
      {
        "familyName": "Robshaw", 
        "givenName": "Matthew", 
        "type": "Person"
      }, 
      {
        "familyName": "Katz", 
        "givenName": "Jonathan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53008-5_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53007-8", 
        "978-3-662-53008-5"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "witness encryption", 
      "indistinguishability obfuscation", 
      "cryptographic primitives", 
      "polynomial time adversary", 
      "one-way functions", 
      "candidate construction", 
      "encryption", 
      "primitives", 
      "input construction", 
      "obfuscation", 
      "robust combiners", 
      "universal construction", 
      "adversary", 
      "new breed", 
      "universal scheme", 
      "security", 
      "Goldwasser", 
      "LWE", 
      "combiner", 
      "scheme", 
      "construction", 
      "mathematical assumptions", 
      "explicit construction", 
      "Kalai", 
      "challenges", 
      "design", 
      "issues", 
      "hand", 
      "work", 
      "way", 
      "assumption", 
      "need", 
      "utility", 
      "recent paper", 
      "state", 
      "function", 
      "candidates", 
      "DDH", 
      "exists", 
      "place", 
      "cases", 
      "years", 
      "existence", 
      "study", 
      "breeds", 
      "paper", 
      "unimagined utility", 
      "different candidate constructions", 
      "primitive exists", 
      "existence of combiners", 
      "subexponential adversaries", 
      "time adversaries"
    ], 
    "name": "Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption", 
    "pagination": "491-520", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018457119"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53008-5_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53008-5_17", 
      "https://app.dimensions.ai/details/publication/pub.1018457119"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_278.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53008-5_17"
  }
]
 

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-53008-5_17'

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-53008-5_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53008-5_17'

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-53008-5_17'


 

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

148 TRIPLES      23 PREDICATES      77 URIs      70 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53008-5_17 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nce75cda8b2124f83a95acc9f252bca2b
4 schema:datePublished 2016-07-21
5 schema:datePublishedReg 2016-07-21
6 schema:description Over the last few years a new breed of cryptographic primitives has arisen: on one hand they have previously unimagined utility and on the other hand they are not based on simple to state and tried out assumptions. With the on-going study of these primitives, we are left with several different candidate constructions each based on a different, not easy to express, mathematical assumptions, where some even turn out to be insecure.A combiner for a cryptographic primitive takes several candidate constructions of the primitive and outputs one construction that is as good as any of the input constructions. Furthermore, this combiner must be efficient: the resulting construction should remain polynomial-time even when combining polynomially many candidate. Combiners are especially important for a primitive where there are several competing constructions whose security is hard to evaluate, as is the case for indistinguishability obfuscation (IO) and witness encryption (WE).One place where the need for combiners appears is in design of a universal construction, where one wishes to find “one construction to rule them all”: an explicit construction that is secure if any construction of the primitive exists.In a recent paper, Goldwasser and Kalai posed as a challenge finding universal constructions for indistinguishability obfuscation and witness encryption. In this work we resolve this issue: we construct universal schemes for IO, and for witness encryption, and also resolve the existence of combiners for these primitives along the way. For IO, our universal construction and combiners can be built based on either assuming DDH, or assuming LWE, with security against subexponential adversaries. For witness encryption, we need only one-way functions secure against polynomial time adversaries.
7 schema:editor N69432fcf4ade415f88c830c794339102
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3fd6ccc73c1e4430b98099252e28eee1
12 schema:keywords DDH
13 Goldwasser
14 Kalai
15 LWE
16 adversary
17 assumption
18 breeds
19 candidate construction
20 candidates
21 cases
22 challenges
23 combiner
24 construction
25 cryptographic primitives
26 design
27 different candidate constructions
28 encryption
29 existence
30 existence of combiners
31 exists
32 explicit construction
33 function
34 hand
35 indistinguishability obfuscation
36 input construction
37 issues
38 mathematical assumptions
39 need
40 new breed
41 obfuscation
42 one-way functions
43 paper
44 place
45 polynomial time adversary
46 primitive exists
47 primitives
48 recent paper
49 robust combiners
50 scheme
51 security
52 state
53 study
54 subexponential adversaries
55 time adversaries
56 unimagined utility
57 universal construction
58 universal scheme
59 utility
60 way
61 witness encryption
62 work
63 years
64 schema:name Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption
65 schema:pagination 491-520
66 schema:productId Na249f64d04254cd6b25f81fde07db221
67 Nfb77d63bea4444cc95b3b055a1aaba05
68 schema:publisher N4af268e0241d4b31951fb95d10bce01c
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018457119
70 https://doi.org/10.1007/978-3-662-53008-5_17
71 schema:sdDatePublished 2022-01-01T19:16
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher Na72af62fb03e4fdf9c6b4b01f46b1589
74 schema:url https://doi.org/10.1007/978-3-662-53008-5_17
75 sgo:license sg:explorer/license/
76 sgo:sdDataset chapters
77 rdf:type schema:Chapter
78 N160c8d2fc054434fbe03d9f06d270f61 rdf:first sg:person.07776170271.83
79 rdf:rest Nd267c7b6003342ab8d1cb53a00961f4c
80 N3fd6ccc73c1e4430b98099252e28eee1 schema:isbn 978-3-662-53007-8
81 978-3-662-53008-5
82 schema:name Advances in Cryptology – CRYPTO 2016
83 rdf:type schema:Book
84 N4af268e0241d4b31951fb95d10bce01c schema:name Springer Nature
85 rdf:type schema:Organisation
86 N69432fcf4ade415f88c830c794339102 rdf:first Nf7039fe77cc543f29aef7ec07f6b2dcc
87 rdf:rest Nefe79989a3c44c8ca0ee78bda3deddf2
88 N70d4763ed0ed463bb031eba056eaf106 schema:familyName Katz
89 schema:givenName Jonathan
90 rdf:type schema:Person
91 Na249f64d04254cd6b25f81fde07db221 schema:name dimensions_id
92 schema:value pub.1018457119
93 rdf:type schema:PropertyValue
94 Na72af62fb03e4fdf9c6b4b01f46b1589 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 Nce75cda8b2124f83a95acc9f252bca2b rdf:first sg:person.012042213735.83
97 rdf:rest Nf2bae0b6e75743d4ac88c0233a735ae0
98 Nd267c7b6003342ab8d1cb53a00961f4c rdf:first sg:person.014324616157.64
99 rdf:rest Nfa16af73cf7741718651dda25820e0d9
100 Nefe79989a3c44c8ca0ee78bda3deddf2 rdf:first N70d4763ed0ed463bb031eba056eaf106
101 rdf:rest rdf:nil
102 Nf2bae0b6e75743d4ac88c0233a735ae0 rdf:first sg:person.016700260675.28
103 rdf:rest N160c8d2fc054434fbe03d9f06d270f61
104 Nf7039fe77cc543f29aef7ec07f6b2dcc schema:familyName Robshaw
105 schema:givenName Matthew
106 rdf:type schema:Person
107 Nfa16af73cf7741718651dda25820e0d9 rdf:first sg:person.015120037757.44
108 rdf:rest rdf:nil
109 Nfb77d63bea4444cc95b3b055a1aaba05 schema:name doi
110 schema:value 10.1007/978-3-662-53008-5_17
111 rdf:type schema:PropertyValue
112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
113 schema:name Information and Computing Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
116 schema:name Data Format
117 rdf:type schema:DefinedTerm
118 sg:person.012042213735.83 schema:affiliation grid-institutes:grid.19006.3e
119 schema:familyName Ananth
120 schema:givenName Prabhanjan
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012042213735.83
122 rdf:type schema:Person
123 sg:person.014324616157.64 schema:affiliation grid-institutes:grid.19006.3e
124 schema:familyName Sahai
125 schema:givenName Amit
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014324616157.64
127 rdf:type schema:Person
128 sg:person.015120037757.44 schema:affiliation grid-institutes:grid.13992.30
129 schema:familyName Yogev
130 schema:givenName Eylon
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015120037757.44
132 rdf:type schema:Person
133 sg:person.016700260675.28 schema:affiliation grid-institutes:grid.19006.3e
134 schema:familyName Jain
135 schema:givenName Aayush
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016700260675.28
137 rdf:type schema:Person
138 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
139 schema:familyName Naor
140 schema:givenName Moni
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
142 rdf:type schema:Person
143 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
144 schema:name Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
145 rdf:type schema:Organization
146 grid-institutes:grid.19006.3e schema:alternateName Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA
147 schema:name Center for Encrypted Functionalities and Department of Computer Science, UCLA, Los Angeles, USA
148 rdf:type schema:Organization
 




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


...