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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bar-Ilan University, 52900, Ramat Gan, Israel", 
          "id": "http://www.grid.ac/institutes/grid.22098.31", 
          "name": [
            "Bar-Ilan University, 52900, Ramat Gan, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Asharov", 
        "givenName": "Gilad", 
        "id": "sg:person.016347606461.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NTT Research, 94303, Palo Alto, CA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "NTT Research, 94303, Palo Alto, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Komargodski", 
        "givenName": "Ilan", 
        "id": "sg:person.012204235441.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, 14850, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, 14850, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Wei-Kai", 
        "id": "sg:person.015030115735.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University, 27708, Durham, NC, USA", 
          "id": "http://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Duke University, 27708, Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nayak", 
        "givenName": "Kartik", 
        "id": "sg:person.011031600672.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011031600672.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e0 degli Studi di Padova, Padova, PD, Italy", 
          "id": "http://www.grid.ac/institutes/grid.5608.b", 
          "name": [
            "Universit\u00e0 degli Studi di Padova, Padova, PD, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Peserico", 
        "givenName": "Enoch", 
        "id": "sg:person.0755702417.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0755702417.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, 14850, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, 14850, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shi", 
        "givenName": "Elaine", 
        "id": "sg:person.014706274717.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-05-01", 
    "datePublishedReg": "2020-05-01", 
    "description": "Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC \u201987 and J. ACM \u201996) is a technique for provably obfuscating programs\u2019 access patterns, such that the access patterns leak no information about the programs\u2019 secret inputs. To compile a general program to an oblivious counterpart, it is well-known that \u03a9(logN)\\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}$$\\varOmega (\\log N)$$\\end{document} amortized blowup is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy\u2019s original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO \u201918) for computational security.A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with O(logN)\\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}$$O(\\log N)$$\\end{document} amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS \u201918) who gave a construction with O(logN\u00b7loglogN)\\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}$$O(\\log N\\cdot \\log \\log N)$$\\end{document} amortized blowup, assuming one-way functions.One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O(n) algorithm improves the previously best known deterministic or randomized algorithms whose running time is O(n\u00b7logn)\\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}$$O(n \\cdot \\log n)$$\\end{document} or O(n\u00b7loglogn)\\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}$$O(n \\cdot \\log \\log n)$$\\end{document}, respectively.", 
    "editor": [
      {
        "familyName": "Canteaut", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Ishai", 
        "givenName": "Yuval", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-45724-2_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-45723-5", 
        "978-3-030-45724-2"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2020", 
      "type": "Book"
    }, 
    "keywords": [
      "Oblivious RAM", 
      "one-way functions", 
      "access patterns", 
      "logarithmic lower bounds", 
      "deterministic oblivious algorithm", 
      "computational security", 
      "ORAM constructions", 
      "lower bounds", 
      "secret inputs", 
      "statistical security", 
      "independent interest", 
      "obfuscating programs", 
      "blowup", 
      "oblivious algorithms", 
      "restricted model", 
      "algorithm", 
      "security", 
      "Goldreich", 
      "general program", 
      "n elements", 
      "beautiful work", 
      "open question", 
      "bounds", 
      "et al", 
      "deterministic", 
      "rams", 
      "building blocks", 
      "ground-breaking work", 
      "Ostrovsky", 
      "work", 
      "problem", 
      "array", 
      "function", 
      "information", 
      "construction", 
      "input", 
      "memory", 
      "model", 
      "Patel et al", 
      "elements", 
      "program", 
      "front", 
      "technique", 
      "Larsen", 
      "block", 
      "Nielsen", 
      "al", 
      "interest", 
      "counterparts", 
      "results", 
      "patterns", 
      "size", 
      "time", 
      "questions", 
      "compaction", 
      "logical memory", 
      "paper", 
      "tight compaction"
    ], 
    "name": "OptORAMa: Optimal Oblivious RAM", 
    "pagination": "403-432", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1127314719"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-45724-2_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-45724-2_14", 
      "https://app.dimensions.ai/details/publication/pub.1127314719"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_342.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-45724-2_14"
  }
]

Download the RDF metadata as:  json-ld nt turtle xml License info

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

170 TRIPLES      23 PREDICATES      83 URIs      76 LITERALS      7 BLANK NODES