Perfect Structure on the Edge of Chaos View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-12-19

AUTHORS

Nir Bitansky , Omer Paneth , Daniel Wichs

ABSTRACT

We construct trapdoor permutations based on (sub-exponential) indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring.Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\text{ SZK } $$ \end{document} — indeed, while factoring-based candidates do not possess such security, future constructions of indistinguishability obfuscation might.As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on indistinguishability obfuscation. More... »

PAGES

474-502

Book

TITLE

Theory of Cryptography

ISBN

978-3-662-49095-2
978-3-662-49096-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-49096-9_20

DOI

http://dx.doi.org/10.1007/978-3-662-49096-9_20

DIMENSIONS

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


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/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0905", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Civil Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MIT, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT, Cambridge, USA"
          ], 
          "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": [
            "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": "Northeastern University, Boston, USA", 
          "id": "http://www.grid.ac/institutes/grid.261112.7", 
          "name": [
            "Northeastern University, Boston, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wichs", 
        "givenName": "Daniel", 
        "id": "sg:person.016071322513.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016071322513.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-12-19", 
    "datePublishedReg": "2015-12-19", 
    "description": "We construct trapdoor permutations based on (sub-exponential) indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring.Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$\\text{ SZK } $$\n\\end{document}\u00a0\u2014 indeed, while factoring-based candidates do not possess such security, future constructions of indistinguishability obfuscation might.As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on indistinguishability obfuscation.", 
    "editor": [
      {
        "familyName": "Kushilevitz", 
        "givenName": "Eyal", 
        "type": "Person"
      }, 
      {
        "familyName": "Malkin", 
        "givenName": "Tal", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-49096-9_20", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-49095-2", 
        "978-3-662-49096-9"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "function", 
      "first candidate", 
      "candidates", 
      "need", 
      "attacks", 
      "trapdoor permutations", 
      "indistinguishability obfuscation", 
      "one-way functions", 
      "possible ways", 
      "class", 
      "obfuscation", 
      "hardness of factoring", 
      "factoring", 
      "structured primitives", 
      "hardness assumption", 
      "noisy structures", 
      "structure", 
      "candidate construction", 
      "way", 
      "quantum attacks", 
      "problem", 
      "complexity classes", 
      "such security", 
      "permutations", 
      "construction", 
      "primitives", 
      "assumption", 
      "SZK", 
      "security", 
      "corollary", 
      "edge of chaos", 
      "edge", 
      "hardness", 
      "future construction", 
      "recent construction", 
      "chaos", 
      "perfect structure"
    ], 
    "name": "Perfect Structure on the Edge of Chaos", 
    "pagination": "474-502", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001843931"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-49096-9_20"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-49096-9_20", 
      "https://app.dimensions.ai/details/publication/pub.1001843931"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:27", 
    "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_134.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-49096-9_20"
  }
]
 

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-49096-9_20'

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-49096-9_20'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-49096-9_20'

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-49096-9_20'


 

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

122 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-49096-9_20 schema:about anzsrc-for:09
2 anzsrc-for:0905
3 schema:author Naebe80eb06bb4125a003cb3241bc3d6e
4 schema:datePublished 2015-12-19
5 schema:datePublishedReg 2015-12-19
6 schema:description We construct trapdoor permutations based on (sub-exponential) indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring.Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\text{ SZK } $$ \end{document} — indeed, while factoring-based candidates do not possess such security, future constructions of indistinguishability obfuscation might.As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on indistinguishability obfuscation.
7 schema:editor N3493376ab792402793a59100c694f3e7
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N5a48af7001a8450f8796df3ea5229259
12 schema:keywords SZK
13 assumption
14 attacks
15 candidate construction
16 candidates
17 chaos
18 class
19 complexity classes
20 construction
21 corollary
22 edge
23 edge of chaos
24 factoring
25 first candidate
26 function
27 future construction
28 hardness
29 hardness assumption
30 hardness of factoring
31 indistinguishability obfuscation
32 need
33 noisy structures
34 obfuscation
35 one-way functions
36 perfect structure
37 permutations
38 possible ways
39 primitives
40 problem
41 quantum attacks
42 recent construction
43 security
44 structure
45 structured primitives
46 such security
47 trapdoor permutations
48 way
49 schema:name Perfect Structure on the Edge of Chaos
50 schema:pagination 474-502
51 schema:productId N7eaaf7ee9d604630b093fbe56df8ee71
52 Nf9d52c6b6c46441eb80c542e398ee9ea
53 schema:publisher Nea8ed03056ae49eebf1c48ca1a986049
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001843931
55 https://doi.org/10.1007/978-3-662-49096-9_20
56 schema:sdDatePublished 2022-06-01T22:27
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher Nd882608255d3406c9b91c169065e553c
59 schema:url https://doi.org/10.1007/978-3-662-49096-9_20
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N1977717e1a3a4fe0ac42f1ed8e5497c0 rdf:first sg:person.014073524511.68
64 rdf:rest N8f79ba7ff4be4777a94776b7986947f2
65 N23af070364084e93bbe5de70d004b286 schema:familyName Kushilevitz
66 schema:givenName Eyal
67 rdf:type schema:Person
68 N3493376ab792402793a59100c694f3e7 rdf:first N23af070364084e93bbe5de70d004b286
69 rdf:rest N38cbe82cc0164872b9e30d9eea1c2790
70 N38cbe82cc0164872b9e30d9eea1c2790 rdf:first N6096395dce0b44cf8e31945f5ceefc58
71 rdf:rest rdf:nil
72 N5a48af7001a8450f8796df3ea5229259 schema:isbn 978-3-662-49095-2
73 978-3-662-49096-9
74 schema:name Theory of Cryptography
75 rdf:type schema:Book
76 N6096395dce0b44cf8e31945f5ceefc58 schema:familyName Malkin
77 schema:givenName Tal
78 rdf:type schema:Person
79 N7eaaf7ee9d604630b093fbe56df8ee71 schema:name dimensions_id
80 schema:value pub.1001843931
81 rdf:type schema:PropertyValue
82 N8f79ba7ff4be4777a94776b7986947f2 rdf:first sg:person.016071322513.42
83 rdf:rest rdf:nil
84 Naebe80eb06bb4125a003cb3241bc3d6e rdf:first sg:person.016302552357.74
85 rdf:rest N1977717e1a3a4fe0ac42f1ed8e5497c0
86 Nd882608255d3406c9b91c169065e553c schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nea8ed03056ae49eebf1c48ca1a986049 schema:name Springer Nature
89 rdf:type schema:Organisation
90 Nf9d52c6b6c46441eb80c542e398ee9ea schema:name doi
91 schema:value 10.1007/978-3-662-49096-9_20
92 rdf:type schema:PropertyValue
93 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
94 schema:name Engineering
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0905 schema:inDefinedTermSet anzsrc-for:
97 schema:name Civil Engineering
98 rdf:type schema:DefinedTerm
99 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.189504.1
100 schema:familyName Paneth
101 schema:givenName Omer
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
103 rdf:type schema:Person
104 sg:person.016071322513.42 schema:affiliation grid-institutes:grid.261112.7
105 schema:familyName Wichs
106 schema:givenName Daniel
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016071322513.42
108 rdf:type schema:Person
109 sg:person.016302552357.74 schema:affiliation grid-institutes:grid.116068.8
110 schema:familyName Bitansky
111 schema:givenName Nir
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74
113 rdf:type schema:Person
114 grid-institutes:grid.116068.8 schema:alternateName MIT, Cambridge, USA
115 schema:name MIT, Cambridge, USA
116 rdf:type schema:Organization
117 grid-institutes:grid.189504.1 schema:alternateName Boston University, Boston, USA
118 schema:name Boston University, Boston, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.261112.7 schema:alternateName Northeastern University, Boston, USA
121 schema:name Northeastern University, Boston, USA
122 rdf:type schema:Organization
 




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


...