Protecting Obfuscation against Algebraic Attacks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Boaz Barak , Sanjam Garg , Yael Tauman Kalai , Omer Paneth , Amit Sahai

ABSTRACT

Recently, Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013) constructed a general-purpose obfuscating compiler for NC1 circuits. We describe a simplified variant of this compiler, and prove that it is a virtual black box obfuscator in a generic multilinear map model. This improves on Brakerski and Rothblum (eprint 2013) who gave such a result under a strengthening of the Exponential Time Hypothesis. We remove this assumption, and thus resolve an open question of Garg et al. As shown by Garg et al., a compiler for NC1 circuits can be bootstrapped to a compiler for all polynomial-sized circuits under the learning with errors (LWE) hardness assumption.Our result shows that there is a candidate obfuscator that cannot be broken by algebraic attacks, hence reducing the task of creating secure obfuscators in the plain model to obtaining sufficiently strong security guarantees on candidate instantiations of multilinear maps. More... »

PAGES

221-238

Book

TITLE

Advances in Cryptology – EUROCRYPT 2014

ISBN

978-3-642-55219-9
978-3-642-55220-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-55220-5_13

DOI

http://dx.doi.org/10.1007/978-3-642-55220-5_13

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Barak", 
        "givenName": "Boaz", 
        "id": "sg:person.01253774424.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01253774424.97"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM Research, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garg", 
        "givenName": "Sanjam", 
        "id": "sg:person.010232701054.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010232701054.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, 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, USA", 
          "id": "http://www.grid.ac/institutes/grid.189504.1", 
          "name": [
            "Boston University, 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": "UCLA, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "UCLA, 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"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "Recently, Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013) constructed a general-purpose obfuscating compiler for NC1 circuits. We describe a simplified variant of this compiler, and prove that it is a virtual black box obfuscator in a generic multilinear map model. This improves on Brakerski and Rothblum (eprint 2013) who gave such a result under a strengthening of the Exponential Time Hypothesis. We remove this assumption, and thus resolve an open question of Garg et al. As shown by Garg et al., a compiler for NC1 circuits can be bootstrapped to a compiler for all polynomial-sized circuits under the learning with errors (LWE) hardness assumption.Our result shows that there is a candidate obfuscator that cannot be broken by algebraic attacks, hence reducing the task of creating secure obfuscators in the plain model to obtaining sufficiently strong security guarantees on candidate instantiations of multilinear maps.", 
    "editor": [
      {
        "familyName": "Nguyen", 
        "givenName": "Phong Q.", 
        "type": "Person"
      }, 
      {
        "familyName": "Oswald", 
        "givenName": "Elisabeth", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-55220-5_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-55219-9", 
        "978-3-642-55220-5"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2014", 
      "type": "Book"
    }, 
    "keywords": [
      "errors (LWE) hardness assumption", 
      "strong security guarantees", 
      "algebraic attacks", 
      "secure obfuscator", 
      "security guarantees", 
      "polynomial-sized circuits", 
      "Garg et al", 
      "hardness assumption", 
      "candidate obfuscator", 
      "plain model", 
      "compiler", 
      "Exponential Time Hypothesis", 
      "obfuscator", 
      "NC1 circuits", 
      "multilinear maps", 
      "map model", 
      "Time Hypothesis", 
      "attacks", 
      "simplified variant", 
      "Raykova", 
      "obfuscation", 
      "Brakerski", 
      "Sahai", 
      "instantiation", 
      "Garg", 
      "guarantees", 
      "task", 
      "learning", 
      "Halevi", 
      "Rothblum", 
      "open question", 
      "model", 
      "maps", 
      "assumption", 
      "results", 
      "circuit", 
      "gentry", 
      "et al", 
      "variants", 
      "questions", 
      "al", 
      "hypothesis", 
      "strengthening", 
      "water"
    ], 
    "name": "Protecting Obfuscation against Algebraic Attacks", 
    "pagination": "221-238", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022841991"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-55220-5_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-55220-5_13", 
      "https://app.dimensions.ai/details/publication/pub.1022841991"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:28", 
    "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_148.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-55220-5_13"
  }
]
 

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-642-55220-5_13'

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-642-55220-5_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-55220-5_13'

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-642-55220-5_13'


 

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

146 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-55220-5_13 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N71d04359da884dc79f0e17d74a2e8ee8
4 schema:datePublished 2014
5 schema:datePublishedReg 2014-01-01
6 schema:description Recently, Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013) constructed a general-purpose obfuscating compiler for NC1 circuits. We describe a simplified variant of this compiler, and prove that it is a virtual black box obfuscator in a generic multilinear map model. This improves on Brakerski and Rothblum (eprint 2013) who gave such a result under a strengthening of the Exponential Time Hypothesis. We remove this assumption, and thus resolve an open question of Garg et al. As shown by Garg et al., a compiler for NC1 circuits can be bootstrapped to a compiler for all polynomial-sized circuits under the learning with errors (LWE) hardness assumption.Our result shows that there is a candidate obfuscator that cannot be broken by algebraic attacks, hence reducing the task of creating secure obfuscators in the plain model to obtaining sufficiently strong security guarantees on candidate instantiations of multilinear maps.
7 schema:editor N272a6c8ed0104c91968d7b478673d5b1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nb2aeade771884f1d8e143e98bc7d8ad1
12 schema:keywords Brakerski
13 Exponential Time Hypothesis
14 Garg
15 Garg et al
16 Halevi
17 NC1 circuits
18 Raykova
19 Rothblum
20 Sahai
21 Time Hypothesis
22 al
23 algebraic attacks
24 assumption
25 attacks
26 candidate obfuscator
27 circuit
28 compiler
29 errors (LWE) hardness assumption
30 et al
31 gentry
32 guarantees
33 hardness assumption
34 hypothesis
35 instantiation
36 learning
37 map model
38 maps
39 model
40 multilinear maps
41 obfuscation
42 obfuscator
43 open question
44 plain model
45 polynomial-sized circuits
46 questions
47 results
48 secure obfuscator
49 security guarantees
50 simplified variant
51 strengthening
52 strong security guarantees
53 task
54 variants
55 water
56 schema:name Protecting Obfuscation against Algebraic Attacks
57 schema:pagination 221-238
58 schema:productId Nd1d734de6a844e7d9bf3d92193fc0939
59 Nea2b61f567c0414581f6ebf8ab99c274
60 schema:publisher Nbd866014b0254bb1b4e92693ac19498a
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022841991
62 https://doi.org/10.1007/978-3-642-55220-5_13
63 schema:sdDatePublished 2022-06-01T22:28
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N6abc4730d3cb499b86b14547cdf25802
66 schema:url https://doi.org/10.1007/978-3-642-55220-5_13
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N1a8d3a1f0e6f4e33b61b7a7d363b0c72 rdf:first sg:person.014073524511.68
71 rdf:rest N1df96d5919924e879e4977d2cdacb172
72 N1df96d5919924e879e4977d2cdacb172 rdf:first sg:person.014324616157.64
73 rdf:rest rdf:nil
74 N272a6c8ed0104c91968d7b478673d5b1 rdf:first N4319602daa6f4db98b184f4ec2de4d50
75 rdf:rest N7a728b2669824aa1980134e252f2ae42
76 N4319602daa6f4db98b184f4ec2de4d50 schema:familyName Nguyen
77 schema:givenName Phong Q.
78 rdf:type schema:Person
79 N50529fed0e7946298d5a404f6582fb51 schema:familyName Oswald
80 schema:givenName Elisabeth
81 rdf:type schema:Person
82 N6abc4730d3cb499b86b14547cdf25802 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N71d04359da884dc79f0e17d74a2e8ee8 rdf:first sg:person.01253774424.97
85 rdf:rest Nc5b5760c1e4948449de6a0ff71150875
86 N7a728b2669824aa1980134e252f2ae42 rdf:first N50529fed0e7946298d5a404f6582fb51
87 rdf:rest rdf:nil
88 Nb2aeade771884f1d8e143e98bc7d8ad1 schema:isbn 978-3-642-55219-9
89 978-3-642-55220-5
90 schema:name Advances in Cryptology – EUROCRYPT 2014
91 rdf:type schema:Book
92 Nbd866014b0254bb1b4e92693ac19498a schema:name Springer Nature
93 rdf:type schema:Organisation
94 Nc5b5760c1e4948449de6a0ff71150875 rdf:first sg:person.010232701054.23
95 rdf:rest Ne54ef2d6d6e44d76a720cfb9dba761b5
96 Nd1d734de6a844e7d9bf3d92193fc0939 schema:name dimensions_id
97 schema:value pub.1022841991
98 rdf:type schema:PropertyValue
99 Ne54ef2d6d6e44d76a720cfb9dba761b5 rdf:first sg:person.015074540743.62
100 rdf:rest N1a8d3a1f0e6f4e33b61b7a7d363b0c72
101 Nea2b61f567c0414581f6ebf8ab99c274 schema:name doi
102 schema:value 10.1007/978-3-642-55220-5_13
103 rdf:type schema:PropertyValue
104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information and Computing Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
108 schema:name Computer Software
109 rdf:type schema:DefinedTerm
110 sg:person.010232701054.23 schema:affiliation grid-institutes:grid.481554.9
111 schema:familyName Garg
112 schema:givenName Sanjam
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010232701054.23
114 rdf:type schema:Person
115 sg:person.01253774424.97 schema:affiliation grid-institutes:grid.419815.0
116 schema:familyName Barak
117 schema:givenName Boaz
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01253774424.97
119 rdf:type schema:Person
120 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.189504.1
121 schema:familyName Paneth
122 schema:givenName Omer
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
124 rdf:type schema:Person
125 sg:person.014324616157.64 schema:affiliation grid-institutes:grid.19006.3e
126 schema:familyName Sahai
127 schema:givenName Amit
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014324616157.64
129 rdf:type schema:Person
130 sg:person.015074540743.62 schema:affiliation grid-institutes:grid.419815.0
131 schema:familyName Kalai
132 schema:givenName Yael Tauman
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074540743.62
134 rdf:type schema:Person
135 grid-institutes:grid.189504.1 schema:alternateName Boston University, USA
136 schema:name Boston University, USA
137 rdf:type schema:Organization
138 grid-institutes:grid.19006.3e schema:alternateName UCLA, USA
139 schema:name UCLA, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research, USA
142 schema:name Microsoft Research, USA
143 rdf:type schema:Organization
144 grid-institutes:grid.481554.9 schema:alternateName IBM Research, USA
145 schema:name IBM Research, USA
146 rdf:type schema:Organization
 




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


...