A Logarithmic Lower Bound for Oblivious RAM (for All Parameters) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2021-08-11

AUTHORS

Ilan Komargodski , Wei-Kai Lin

ABSTRACT

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds as well as in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters.We observe that there is a very natural setting of parameters in which no non-trivial lower bound is known, even not ones in restricted models of computation (like the so called balls and bins model). Let N and w\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{w}}$$\end{document} be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{b}}$$\end{document} the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative w/b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{w}}/{\boldsymbol{b}}$$\end{document} factor which makes them trivial in many settings of parameters of interest.In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) ΩlogNwm/logbw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \varOmega \left( \log \left( \frac{N{\boldsymbol{w}}}{m}\right) /\log \left( \frac{{\boldsymbol{b}}}{{\boldsymbol{w}}}\right) \right) $$\end{document}memory probes for every logical operation. Here, m denotes the bit-size of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if b≫w\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {\boldsymbol{b}}\gg {\boldsymbol{w}}$$\end{document}. Our lower bound is tight for all settings of parameters, up to the log(b/w)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log ({\boldsymbol{b}}/{\boldsymbol{w}})$$\end{document} factor. Our bound also extends to the non-colluding multi-server setting.As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online vs. offline models. Specifically, we show that when w=logN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{w}}=\log N$$\end{document} and , there exists an offline ORAM that makes (on average) o(1) memory probes per logical operation while every online one must make Ω(logN/loglogN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (\log N/\log \log N)$$\end{document} memory probes per logical operation. No such previous separation was known for any setting of parameters, not even in the balls and bins model. More... »

PAGES

579-609

Book

TITLE

Advances in Cryptology – CRYPTO 2021

ISBN

978-3-030-84258-1
978-3-030-84259-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-84259-8_20

DOI

http://dx.doi.org/10.1007/978-3-030-84259-8_20

DIMENSIONS

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


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/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "NTT Research, Sunnyvale, CA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Hebrew University, Jerusalem, Israel", 
            "NTT Research, Sunnyvale, 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, Ithaca, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, 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"
      }
    ], 
    "datePublished": "2021-08-11", 
    "datePublishedReg": "2021-08-11", 
    "description": "An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds as well as in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters.We observe that there is a very natural setting of parameters in which no non-trivial lower bound is known, even not ones in restricted models of computation (like the so called balls and bins model). Let N and w\\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}$${\\boldsymbol{w}}$$\\end{document} be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by b\\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}$${\\boldsymbol{b}}$$\\end{document} the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative w/b\\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}$${\\boldsymbol{w}}/{\\boldsymbol{b}}$$\\end{document} factor which makes them trivial in many settings of parameters of interest.In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) \u03a9logNwm/logbw\\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 \\left( \\log \\left( \\frac{N{\\boldsymbol{w}}}{m}\\right) /\\log \\left( \\frac{{\\boldsymbol{b}}}{{\\boldsymbol{w}}}\\right) \\right) $$\\end{document}memory probes for every logical operation. Here, m denotes the bit-size of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if b\u226bw\\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}$$ {\\boldsymbol{b}}\\gg {\\boldsymbol{w}}$$\\end{document}. Our lower bound is tight for all settings of parameters, up\u00a0to the log(b/w)\\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}$$\\log ({\\boldsymbol{b}}/{\\boldsymbol{w}})$$\\end{document} factor. Our bound also extends to the non-colluding multi-server setting.As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online vs. offline models. Specifically, we show that when w=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}$${\\boldsymbol{w}}=\\log N$$\\end{document} and , there exists an offline ORAM that makes (on average) o(1) memory probes per logical operation while every online one must make \u03a9(logN/loglogN)\\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/\\log \\log N)$$\\end{document} memory probes per logical operation. No such previous separation was known for any setting of parameters, not even in the balls and bins model.", 
    "editor": [
      {
        "familyName": "Malkin", 
        "givenName": "Tal", 
        "type": "Person"
      }, 
      {
        "familyName": "Peikert", 
        "givenName": "Chris", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-84259-8_20", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-84258-1", 
        "978-3-030-84259-8"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2021", 
      "type": "Book"
    }, 
    "keywords": [
      "setting of parameters", 
      "lower bounds", 
      "upper bounds", 
      "model of computation", 
      "bounds", 
      "logical operations", 
      "bin model", 
      "observed locations", 
      "parameters", 
      "model", 
      "computation", 
      "Oblivious RAM", 
      "Goldreich", 
      "terms", 
      "logarithmic", 
      "small overhead", 
      "operation", 
      "Ostrovsky", 
      "input", 
      "great progress", 
      "overhead", 
      "natural settings", 
      "applications", 
      "ball", 
      "recent years", 
      "one", 
      "number", 
      "first separation", 
      "rams", 
      "access patterns", 
      "interest", 
      "work", 
      "progress", 
      "setting", 
      "number of cells", 
      "probe", 
      "local storage", 
      "separation", 
      "location", 
      "patterns", 
      "factors", 
      "storage", 
      "Online", 
      "years", 
      "cells", 
      "previous separation", 
      "memory probes", 
      "multi-server setting"
    ], 
    "name": "A Logarithmic Lower Bound for Oblivious RAM (for All Parameters)", 
    "pagination": "579-609", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1140318704"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-84259-8_20"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-84259-8_20", 
      "https://app.dimensions.ai/details/publication/pub.1140318704"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:49", 
    "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_36.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-84259-8_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-030-84259-8_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-030-84259-8_20'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-84259-8_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-030-84259-8_20'


 

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

124 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-84259-8_20 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N1822d696e495478e91d7b93665a1a524
4 schema:datePublished 2021-08-11
5 schema:datePublishedReg 2021-08-11
6 schema:description An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e., for every input the observed locations accessed are similarly distributed. In recent years there has been great progress both in terms of upper bounds as well as in terms of lower bounds, essentially pinning down the smallest overhead possible in various settings of parameters.We observe that there is a very natural setting of parameters in which no non-trivial lower bound is known, even not ones in restricted models of computation (like the so called balls and bins model). Let N and w\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{w}}$$\end{document} be the number of cells and bit-size of cells, respectively, in the RAM that we wish to simulate obliviously. Denote by b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{b}}$$\end{document} the cell bit-size of the ORAM. All previous ORAM lower bounds have a multiplicative w/b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{w}}/{\boldsymbol{b}}$$\end{document} factor which makes them trivial in many settings of parameters of interest.In this work, we prove a new ORAM lower bound that captures this setting (and in all other settings it is at least as good as previous ones, quantitatively). We show that any ORAM must make (amortized) ΩlogNwm/logbw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \varOmega \left( \log \left( \frac{N{\boldsymbol{w}}}{m}\right) /\log \left( \frac{{\boldsymbol{b}}}{{\boldsymbol{w}}}\right) \right) $$\end{document}memory probes for every logical operation. Here, m denotes the bit-size of the local storage of the ORAM. Our lower bound implies that logarithmic overhead in accesses is necessary, even if b≫w\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {\boldsymbol{b}}\gg {\boldsymbol{w}}$$\end{document}. Our lower bound is tight for all settings of parameters, up to the log(b/w)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log ({\boldsymbol{b}}/{\boldsymbol{w}})$$\end{document} factor. Our bound also extends to the non-colluding multi-server setting.As an application, we derive the first (unconditional) separation between the overhead needed for ORAMs in the online vs. offline models. Specifically, we show that when w=logN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{w}}=\log N$$\end{document} and , there exists an offline ORAM that makes (on average) o(1) memory probes per logical operation while every online one must make Ω(logN/loglogN)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (\log N/\log \log N)$$\end{document} memory probes per logical operation. No such previous separation was known for any setting of parameters, not even in the balls and bins model.
7 schema:editor N91048d91a5904d97b8f32bb0cd813a31
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne60c5d38c7b64456b056c1dce079af92
12 schema:keywords Goldreich
13 Oblivious RAM
14 Online
15 Ostrovsky
16 access patterns
17 applications
18 ball
19 bin model
20 bounds
21 cells
22 computation
23 factors
24 first separation
25 great progress
26 input
27 interest
28 local storage
29 location
30 logarithmic
31 logical operations
32 lower bounds
33 memory probes
34 model
35 model of computation
36 multi-server setting
37 natural settings
38 number
39 number of cells
40 observed locations
41 one
42 operation
43 overhead
44 parameters
45 patterns
46 previous separation
47 probe
48 progress
49 rams
50 recent years
51 separation
52 setting
53 setting of parameters
54 small overhead
55 storage
56 terms
57 upper bounds
58 work
59 years
60 schema:name A Logarithmic Lower Bound for Oblivious RAM (for All Parameters)
61 schema:pagination 579-609
62 schema:productId N33f841a6be1f423d8b5112c88fa5c754
63 Nef30d912aa7c44faab26f7ab33a0ed5d
64 schema:publisher N2b5c062b43c145cd8a47f1afce784925
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1140318704
66 https://doi.org/10.1007/978-3-030-84259-8_20
67 schema:sdDatePublished 2022-05-10T10:49
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N066c7e8ec66f4a508d62c9588e98d3e9
70 schema:url https://doi.org/10.1007/978-3-030-84259-8_20
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N066c7e8ec66f4a508d62c9588e98d3e9 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N1822d696e495478e91d7b93665a1a524 rdf:first sg:person.012204235441.12
77 rdf:rest N5764579c74ef4fad8c9f6cb4dd30737d
78 N2b5c062b43c145cd8a47f1afce784925 schema:name Springer Nature
79 rdf:type schema:Organisation
80 N33f841a6be1f423d8b5112c88fa5c754 schema:name dimensions_id
81 schema:value pub.1140318704
82 rdf:type schema:PropertyValue
83 N5764579c74ef4fad8c9f6cb4dd30737d rdf:first sg:person.015030115735.91
84 rdf:rest rdf:nil
85 N91048d91a5904d97b8f32bb0cd813a31 rdf:first Nd9a64abd2b754329a02f5593039105a7
86 rdf:rest Nd335b2e158b540248704c50696612ee8
87 Nd335b2e158b540248704c50696612ee8 rdf:first Nd97cbaf4c3d0478c9d0955f4255ca5ea
88 rdf:rest rdf:nil
89 Nd97cbaf4c3d0478c9d0955f4255ca5ea schema:familyName Peikert
90 schema:givenName Chris
91 rdf:type schema:Person
92 Nd9a64abd2b754329a02f5593039105a7 schema:familyName Malkin
93 schema:givenName Tal
94 rdf:type schema:Person
95 Ne60c5d38c7b64456b056c1dce079af92 schema:isbn 978-3-030-84258-1
96 978-3-030-84259-8
97 schema:name Advances in Cryptology – CRYPTO 2021
98 rdf:type schema:Book
99 Nef30d912aa7c44faab26f7ab33a0ed5d schema:name doi
100 schema:value 10.1007/978-3-030-84259-8_20
101 rdf:type schema:PropertyValue
102 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
103 schema:name Psychology and Cognitive Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
106 schema:name Psychology
107 rdf:type schema:DefinedTerm
108 sg:person.012204235441.12 schema:affiliation grid-institutes:None
109 schema:familyName Komargodski
110 schema:givenName Ilan
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012204235441.12
112 rdf:type schema:Person
113 sg:person.015030115735.91 schema:affiliation grid-institutes:grid.5386.8
114 schema:familyName Lin
115 schema:givenName Wei-Kai
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91
117 rdf:type schema:Person
118 grid-institutes:None schema:alternateName NTT Research, Sunnyvale, CA, USA
119 schema:name Hebrew University, Jerusalem, Israel
120 NTT Research, Sunnyvale, CA, USA
121 rdf:type schema:Organization
122 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, USA
123 schema:name Cornell University, Ithaca, USA
124 rdf:type schema:Organization
 




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


...