Delegating RAM Computations with Adaptive Soundness and Privacy View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016-10-21

AUTHORS

Prabhanjan Ananth , Yu-Chi Chen , Kai-Min Chung , Huijia Lin , Wei-Kai Lin

ABSTRACT

We consider the problem of delegating RAM computations over persistent databases. A user wishes to delegate a sequence of computations over a database to a server, where each computation may read and modify the database and the modifications persist between computations. Delegating RAM computations is important as it has the distinct feature that the run-time of computations maybe sub-linear in the size of the database.We present the first RAM delegation scheme that provide both soundness and privacy guarantees in the adaptive setting, where the sequence of delegated RAM programs are chosen adaptively, depending potentially on the encodings of the database and previously chosen programs. Prior works either achieved only adaptive soundness without privacy [Kalai and Paneth, ePrint’15], or only security in the selective setting where all RAM programs are chosen statically [Chen et al. ITCS’16, Canetti and Holmgren ITCS’16].Our scheme assumes the existence of indistinguishability obfuscation (iO\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {i}\mathcal {O}$$\end{document}) for circuits and the decisional Diffie-Hellman (DDH) assumption. However, our techniques are quite general and in particular, might be applicable even in settings where iO is not used. We provide a “security lifting technique” that “lifts” any proof of selective security satisfying certain special properties into a proof of adaptive security, for arbitrary cryptographic schemes. We then apply this technique to the delegation scheme of Chen et al. and its selective security proof, obtaining that their scheme is essentially already adaptively secure. Because of the general approach, we can also easily extend to delegating parallel RAM (PRAM) computations. We believe that the security lifting technique can potentially find other applications and is of independent interest. More... »

PAGES

3-30

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53644-5_1

DOI

http://dx.doi.org/10.1007/978-3-662-53644-5_1

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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, University of California Los Angeles, Los Angeles, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Center for Encrypted Functionalities, University of California Los Angeles, 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": "Academia Sinica, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Academia Sinica, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Yu-Chi", 
        "id": "sg:person.011041173537.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011041173537.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Academia Sinica, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Academia Sinica, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chung", 
        "givenName": "Kai-Min", 
        "id": "sg:person.015157715672.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015157715672.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, Santa Barbara, USA", 
          "id": "http://www.grid.ac/institutes/grid.133342.4", 
          "name": [
            "University of California, Santa Barbara, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Huijia", 
        "id": "sg:person.07447665001.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07447665001.15"
        ], 
        "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": "2016-10-21", 
    "datePublishedReg": "2016-10-21", 
    "description": "We consider the problem of delegating RAM computations over persistent databases. A user wishes to delegate a sequence of computations over a database to a server, where each computation may read and modify the database and the modifications persist between computations. Delegating RAM computations is important as it has the distinct feature that the run-time of computations maybe sub-linear in the size of the database.We present the first RAM delegation scheme that provide both soundness and privacy guarantees in the adaptive setting, where the sequence of delegated RAM programs are chosen adaptively, depending potentially on the encodings of the database and previously chosen programs. Prior works either achieved only adaptive soundness without privacy [Kalai and Paneth, ePrint\u201915], or only security in the selective setting where all RAM programs are chosen statically [Chen et al. ITCS\u201916, Canetti and Holmgren ITCS\u201916].Our scheme assumes the existence of indistinguishability obfuscation (iO\\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}$$\\mathsf {i}\\mathcal {O}$$\\end{document}) for circuits and the decisional Diffie-Hellman (DDH) assumption. However, our techniques are quite general and in particular, might be applicable even in settings where iO is not used. We provide a \u201csecurity lifting technique\u201d that \u201clifts\u201d any proof of selective security satisfying certain special properties into a proof of adaptive security, for arbitrary cryptographic schemes. We then apply this technique to the delegation scheme of Chen et al. and its selective security proof, obtaining that their scheme is essentially already adaptively secure. Because of the general approach, we can also easily extend to delegating parallel RAM (PRAM) computations. We believe that the security lifting technique can potentially find other applications and is of independent interest.", 
    "editor": [
      {
        "familyName": "Hirt", 
        "givenName": "Martin", 
        "type": "Person"
      }, 
      {
        "familyName": "Smith", 
        "givenName": "Adam", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53644-5_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53643-8", 
        "978-3-662-53644-5"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "RAM computation", 
      "delegation scheme", 
      "RAM programs", 
      "decisional Diffie-Hellman assumption", 
      "adaptive soundness", 
      "Diffie-Hellman assumption", 
      "sequence of computations", 
      "privacy guarantees", 
      "cryptographic schemes", 
      "adaptive security", 
      "security proof", 
      "persistent database", 
      "selective security", 
      "indistinguishability obfuscation", 
      "security", 
      "privacy", 
      "selective setting", 
      "computation", 
      "adaptive setting", 
      "certain special properties", 
      "independent interest", 
      "scheme", 
      "soundness", 
      "database", 
      "Chen et al", 
      "server", 
      "general approach", 
      "obfuscation", 
      "users", 
      "proof", 
      "guarantees", 
      "technique", 
      "encoding", 
      "special properties", 
      "distinct features", 
      "applications", 
      "lifting technique", 
      "program", 
      "features", 
      "sequence", 
      "setting", 
      "interest", 
      "et al", 
      "assumption", 
      "circuit", 
      "size", 
      "modification", 
      "properties", 
      "existence", 
      "al", 
      "lift", 
      "problem", 
      "approach"
    ], 
    "name": "Delegating RAM Computations with Adaptive Soundness and Privacy", 
    "pagination": "3-30", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084904587"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53644-5_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53644-5_1", 
      "https://app.dimensions.ai/details/publication/pub.1084904587"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:43", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_186.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53644-5_1"
  }
]
 

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-53644-5_1'

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-53644-5_1'

Turtle is a human-readable linked data format.

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

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-53644-5_1'


 

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

159 TRIPLES      23 PREDICATES      79 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53644-5_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author N2f4b5b081eda4fa0a37ecdb4bdf123fe
5 schema:datePublished 2016-10-21
6 schema:datePublishedReg 2016-10-21
7 schema:description We consider the problem of delegating RAM computations over persistent databases. A user wishes to delegate a sequence of computations over a database to a server, where each computation may read and modify the database and the modifications persist between computations. Delegating RAM computations is important as it has the distinct feature that the run-time of computations maybe sub-linear in the size of the database.We present the first RAM delegation scheme that provide both soundness and privacy guarantees in the adaptive setting, where the sequence of delegated RAM programs are chosen adaptively, depending potentially on the encodings of the database and previously chosen programs. Prior works either achieved only adaptive soundness without privacy [Kalai and Paneth, ePrint’15], or only security in the selective setting where all RAM programs are chosen statically [Chen et al. ITCS’16, Canetti and Holmgren ITCS’16].Our scheme assumes the existence of indistinguishability obfuscation (iO\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {i}\mathcal {O}$$\end{document}) for circuits and the decisional Diffie-Hellman (DDH) assumption. However, our techniques are quite general and in particular, might be applicable even in settings where iO is not used. We provide a “security lifting technique” that “lifts” any proof of selective security satisfying certain special properties into a proof of adaptive security, for arbitrary cryptographic schemes. We then apply this technique to the delegation scheme of Chen et al. and its selective security proof, obtaining that their scheme is essentially already adaptively secure. Because of the general approach, we can also easily extend to delegating parallel RAM (PRAM) computations. We believe that the security lifting technique can potentially find other applications and is of independent interest.
8 schema:editor Nc8737ebbd32a4187be6188d412f0bf42
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf N4d1dce1c603c437eb8a85abd28c02ec6
13 schema:keywords Chen et al
14 Diffie-Hellman assumption
15 RAM computation
16 RAM programs
17 adaptive security
18 adaptive setting
19 adaptive soundness
20 al
21 applications
22 approach
23 assumption
24 certain special properties
25 circuit
26 computation
27 cryptographic schemes
28 database
29 decisional Diffie-Hellman assumption
30 delegation scheme
31 distinct features
32 encoding
33 et al
34 existence
35 features
36 general approach
37 guarantees
38 independent interest
39 indistinguishability obfuscation
40 interest
41 lift
42 lifting technique
43 modification
44 obfuscation
45 persistent database
46 privacy
47 privacy guarantees
48 problem
49 program
50 proof
51 properties
52 scheme
53 security
54 security proof
55 selective security
56 selective setting
57 sequence
58 sequence of computations
59 server
60 setting
61 size
62 soundness
63 special properties
64 technique
65 users
66 schema:name Delegating RAM Computations with Adaptive Soundness and Privacy
67 schema:pagination 3-30
68 schema:productId Nc803d421cba742f9a0847ecade66e37f
69 Nd5b8853a155244f58ab32edfc30faebc
70 schema:publisher N284080513b3c46cda2e78cc4b7cf64c6
71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084904587
72 https://doi.org/10.1007/978-3-662-53644-5_1
73 schema:sdDatePublished 2022-05-20T07:43
74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
75 schema:sdPublisher Ne3c3370c98184e29ac524d1563022278
76 schema:url https://doi.org/10.1007/978-3-662-53644-5_1
77 sgo:license sg:explorer/license/
78 sgo:sdDataset chapters
79 rdf:type schema:Chapter
80 N087c7dbd9a8a49ea9399ce9f3f5073d7 rdf:first sg:person.015157715672.30
81 rdf:rest N8ea23d4dca0a4c639983fb89da43d2f5
82 N284080513b3c46cda2e78cc4b7cf64c6 schema:name Springer Nature
83 rdf:type schema:Organisation
84 N2f4b5b081eda4fa0a37ecdb4bdf123fe rdf:first sg:person.012042213735.83
85 rdf:rest Nfa9f052243394221a17e5aff980719e3
86 N4ce1d8bcba0d4a0195c6609b5a4f7af6 schema:familyName Smith
87 schema:givenName Adam
88 rdf:type schema:Person
89 N4d1dce1c603c437eb8a85abd28c02ec6 schema:isbn 978-3-662-53643-8
90 978-3-662-53644-5
91 schema:name Theory of Cryptography
92 rdf:type schema:Book
93 N82802b2f470742a19cd93df35b45916f schema:familyName Hirt
94 schema:givenName Martin
95 rdf:type schema:Person
96 N8ea23d4dca0a4c639983fb89da43d2f5 rdf:first sg:person.07447665001.15
97 rdf:rest Nea3443dcc72a45f484b1a48a6dd77ebe
98 Na55cf17807ba4bc38f9c509046afb1c7 rdf:first N4ce1d8bcba0d4a0195c6609b5a4f7af6
99 rdf:rest rdf:nil
100 Nc803d421cba742f9a0847ecade66e37f schema:name dimensions_id
101 schema:value pub.1084904587
102 rdf:type schema:PropertyValue
103 Nc8737ebbd32a4187be6188d412f0bf42 rdf:first N82802b2f470742a19cd93df35b45916f
104 rdf:rest Na55cf17807ba4bc38f9c509046afb1c7
105 Nd5b8853a155244f58ab32edfc30faebc schema:name doi
106 schema:value 10.1007/978-3-662-53644-5_1
107 rdf:type schema:PropertyValue
108 Ne3c3370c98184e29ac524d1563022278 schema:name Springer Nature - SN SciGraph project
109 rdf:type schema:Organization
110 Nea3443dcc72a45f484b1a48a6dd77ebe rdf:first sg:person.015030115735.91
111 rdf:rest rdf:nil
112 Nfa9f052243394221a17e5aff980719e3 rdf:first sg:person.011041173537.52
113 rdf:rest N087c7dbd9a8a49ea9399ce9f3f5073d7
114 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
115 schema:name Information and Computing Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
118 schema:name Computation Theory and Mathematics
119 rdf:type schema:DefinedTerm
120 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
121 schema:name Data Format
122 rdf:type schema:DefinedTerm
123 sg:person.011041173537.52 schema:affiliation grid-institutes:grid.28665.3f
124 schema:familyName Chen
125 schema:givenName Yu-Chi
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011041173537.52
127 rdf:type schema:Person
128 sg:person.012042213735.83 schema:affiliation grid-institutes:grid.19006.3e
129 schema:familyName Ananth
130 schema:givenName Prabhanjan
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012042213735.83
132 rdf:type schema:Person
133 sg:person.015030115735.91 schema:affiliation grid-institutes:grid.5386.8
134 schema:familyName Lin
135 schema:givenName Wei-Kai
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91
137 rdf:type schema:Person
138 sg:person.015157715672.30 schema:affiliation grid-institutes:grid.28665.3f
139 schema:familyName Chung
140 schema:givenName Kai-Min
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015157715672.30
142 rdf:type schema:Person
143 sg:person.07447665001.15 schema:affiliation grid-institutes:grid.133342.4
144 schema:familyName Lin
145 schema:givenName Huijia
146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07447665001.15
147 rdf:type schema:Person
148 grid-institutes:grid.133342.4 schema:alternateName University of California, Santa Barbara, USA
149 schema:name University of California, Santa Barbara, USA
150 rdf:type schema:Organization
151 grid-institutes:grid.19006.3e schema:alternateName Center for Encrypted Functionalities, University of California Los Angeles, Los Angeles, USA
152 schema:name Center for Encrypted Functionalities, University of California Los Angeles, Los Angeles, USA
153 rdf:type schema:Organization
154 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Taipei, Taiwan
155 schema:name Academia Sinica, Taipei, Taiwan
156 rdf:type schema:Organization
157 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, USA
158 schema:name Cornell University, Ithaca, USA
159 rdf:type schema:Organization
 




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


...