On Everlasting Security in the Hybrid Bounded Storage Model View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Danny Harnik , Moni Naor

ABSTRACT

The bounded storage model (BSM) bounds the storage space of an adversary rather than its running time. It utilizes the public transmission of a long random string \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\cal R}$\end{document} of length r, and relies on the assumption that an eavesdropper cannot possibly store all of this string. Encryption schemes in this model achieve the appealing property of everlasting security. In short, this means that an encrypted message remains secure even if the adversary eventually gains more storage or gains knowledge of (original) secret keys that may have been used. However, if the honest parties do not share any private information in advance, then achieving everlasting security requires high storage capacity from the honest parties (storage of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega(\sqrt{r})$\end{document}, as shown in [9]).We consider the idea of a hybrid bounded storage model were computational limitations on the eavesdropper are assumed up until the time that the transmission of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\cal R}$\end{document} has ended. For example, can the honest parties run a computationally secure key agreement protocol in order to agree on a shared private key for the BSM, and thus achieve everlasting security with low memory requirements? We study the possibility and impossibility of everlasting security in the hybrid bounded storage model. We start by formally defining the model and everlasting security for this model. We show the equivalence of two flavors of definitions: indistinguishability of encryptions and semantic security.On the negative side, we show that everlasting security with low storage requirements cannot be achieved by black-box reductions in the hybrid BSM. This serves as a further indication to the hardness of achieving low storage everlasting security, adding to previous results of this nature [9, 15]. On the other hand, we show two augmentations of the model that allow for low storage everlasting security. The first is by adding a random oracle to the model, while the second bounds the accessibility of the adversary to the broadcast string \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\cal R}$\end{document}. Finally, we show that in these two modified models, there also exist bounded storage oblivious transfer protocols with low storage requirements. More... »

PAGES

192-203

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11787006_17

DOI

http://dx.doi.org/10.1007/11787006_17

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Dept. of Computer Science, Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Harnik", 
        "givenName": "Danny", 
        "id": "sg:person.011037626541.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037626541.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science and Applied Math., Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Dept. of Computer Science and Applied Math., Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "The bounded storage model (BSM) bounds the storage space of an adversary rather than its running time. It utilizes the public transmission of a long random string \\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}${\\cal R}$\\end{document} of length r, and relies on the assumption that an eavesdropper cannot possibly store all of this string. Encryption schemes in this model achieve the appealing property of everlasting security. In short, this means that an encrypted message remains secure even if the adversary eventually gains more storage or gains knowledge of (original) secret keys that may have been used. However, if the honest parties do not share any private information in advance, then achieving everlasting security requires high storage capacity from the honest parties (storage of \\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}$\\Omega(\\sqrt{r})$\\end{document}, as shown in [9]).We consider the idea of a hybrid bounded storage model were computational limitations on the eavesdropper are assumed up until the time that the transmission of \\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}${\\cal R}$\\end{document} has ended. For example, can the honest parties run a computationally secure key agreement protocol in order to agree on a shared private key for the BSM, and thus achieve everlasting security with low memory requirements? We study the possibility and impossibility of everlasting security in the hybrid bounded storage model. We start by formally defining the model and everlasting security for this model. We show the equivalence of two flavors of definitions: indistinguishability of encryptions and semantic security.On the negative side, we show that everlasting security with low storage requirements cannot be achieved by black-box reductions in the hybrid BSM. This serves as a further indication to the hardness of achieving low storage everlasting security, adding to previous results of this nature [9, 15]. On the other hand, we show two augmentations of the model that allow for low storage everlasting security. The first is by adding a random oracle to the model, while the second bounds the accessibility of the adversary to the broadcast string \\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}${\\cal R}$\\end{document}. Finally, we show that in these two modified models, there also exist bounded storage oblivious transfer protocols with low storage requirements.", 
    "editor": [
      {
        "familyName": "Bugliesi", 
        "givenName": "Michele", 
        "type": "Person"
      }, 
      {
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "type": "Person"
      }, 
      {
        "familyName": "Sassone", 
        "givenName": "Vladimiro", 
        "type": "Person"
      }, 
      {
        "familyName": "Wegener", 
        "givenName": "Ingo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11787006_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35907-4", 
        "978-3-540-35908-1"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "everlasting security", 
      "low storage requirements", 
      "storage model", 
      "honest parties", 
      "storage requirements", 
      "secure key agreement protocol", 
      "indistinguishability of encryptions", 
      "key agreement protocol", 
      "low memory requirements", 
      "Bounded Storage Model", 
      "oblivious transfer protocol", 
      "long random string", 
      "semantic security", 
      "encryption scheme", 
      "private key", 
      "black-box reductions", 
      "agreement protocol", 
      "secret key", 
      "memory requirements", 
      "storage space", 
      "random oracles", 
      "transfer protocol", 
      "running time", 
      "more storage", 
      "second bounds", 
      "computational limitations", 
      "adversary", 
      "security", 
      "private information", 
      "random strings", 
      "eavesdropper", 
      "public transmission", 
      "requirements", 
      "encryption", 
      "key", 
      "oracle", 
      "protocol", 
      "high storage capacity", 
      "strings", 
      "storage capacity", 
      "indistinguishability", 
      "messages", 
      "transmission", 
      "scheme", 
      "model", 
      "parties", 
      "information", 
      "negative side", 
      "bounds", 
      "space", 
      "idea", 
      "storage", 
      "example", 
      "accessibility", 
      "time", 
      "knowledge", 
      "definition", 
      "limitations", 
      "order", 
      "advances", 
      "previous results", 
      "hand", 
      "equivalence", 
      "assumption", 
      "BSM", 
      "results", 
      "impossibility", 
      "augmentation", 
      "possibility", 
      "hybrids", 
      "nature", 
      "length r", 
      "capacity", 
      "side", 
      "properties", 
      "reduction", 
      "flavor", 
      "indications", 
      "hardness", 
      "further indication", 
      "flavors of definitions", 
      "hybrid BSM", 
      "low storage everlasting security", 
      "storage everlasting security", 
      "broadcast string", 
      "storage oblivious transfer protocols", 
      "Hybrid Bounded Storage Model"
    ], 
    "name": "On Everlasting Security in the Hybrid Bounded Storage Model", 
    "pagination": "192-203", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052593443"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11787006_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11787006_17", 
      "https://app.dimensions.ai/details/publication/pub.1052593443"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:27", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_86.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11787006_17"
  }
]
 

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/11787006_17'

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/11787006_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11787006_17'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11787006_17'


 

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

172 TRIPLES      23 PREDICATES      113 URIs      106 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11787006_17 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N60ea6329467a4efb95fadc0cb1144cbe
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description The bounded storage model (BSM) bounds the storage space of an adversary rather than its running time. It utilizes the public transmission of a long random string \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\cal R}$\end{document} of length r, and relies on the assumption that an eavesdropper cannot possibly store all of this string. Encryption schemes in this model achieve the appealing property of everlasting security. In short, this means that an encrypted message remains secure even if the adversary eventually gains more storage or gains knowledge of (original) secret keys that may have been used. However, if the honest parties do not share any private information in advance, then achieving everlasting security requires high storage capacity from the honest parties (storage of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Omega(\sqrt{r})$\end{document}, as shown in [9]).We consider the idea of a hybrid bounded storage model were computational limitations on the eavesdropper are assumed up until the time that the transmission of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\cal R}$\end{document} has ended. For example, can the honest parties run a computationally secure key agreement protocol in order to agree on a shared private key for the BSM, and thus achieve everlasting security with low memory requirements? We study the possibility and impossibility of everlasting security in the hybrid bounded storage model. We start by formally defining the model and everlasting security for this model. We show the equivalence of two flavors of definitions: indistinguishability of encryptions and semantic security.On the negative side, we show that everlasting security with low storage requirements cannot be achieved by black-box reductions in the hybrid BSM. This serves as a further indication to the hardness of achieving low storage everlasting security, adding to previous results of this nature [9, 15]. On the other hand, we show two augmentations of the model that allow for low storage everlasting security. The first is by adding a random oracle to the model, while the second bounds the accessibility of the adversary to the broadcast string \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\cal R}$\end{document}. Finally, we show that in these two modified models, there also exist bounded storage oblivious transfer protocols with low storage requirements.
7 schema:editor N439d4e5b8d0042c9be39e03986c56f45
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nfa8ceb4e18ae4686ab50426f125d07fc
12 schema:keywords BSM
13 Bounded Storage Model
14 Hybrid Bounded Storage Model
15 accessibility
16 advances
17 adversary
18 agreement protocol
19 assumption
20 augmentation
21 black-box reductions
22 bounds
23 broadcast string
24 capacity
25 computational limitations
26 definition
27 eavesdropper
28 encryption
29 encryption scheme
30 equivalence
31 everlasting security
32 example
33 flavor
34 flavors of definitions
35 further indication
36 hand
37 hardness
38 high storage capacity
39 honest parties
40 hybrid BSM
41 hybrids
42 idea
43 impossibility
44 indications
45 indistinguishability
46 indistinguishability of encryptions
47 information
48 key
49 key agreement protocol
50 knowledge
51 length r
52 limitations
53 long random string
54 low memory requirements
55 low storage everlasting security
56 low storage requirements
57 memory requirements
58 messages
59 model
60 more storage
61 nature
62 negative side
63 oblivious transfer protocol
64 oracle
65 order
66 parties
67 possibility
68 previous results
69 private information
70 private key
71 properties
72 protocol
73 public transmission
74 random oracles
75 random strings
76 reduction
77 requirements
78 results
79 running time
80 scheme
81 second bounds
82 secret key
83 secure key agreement protocol
84 security
85 semantic security
86 side
87 space
88 storage
89 storage capacity
90 storage everlasting security
91 storage model
92 storage oblivious transfer protocols
93 storage requirements
94 storage space
95 strings
96 time
97 transfer protocol
98 transmission
99 schema:name On Everlasting Security in the Hybrid Bounded Storage Model
100 schema:pagination 192-203
101 schema:productId N10106dd329c7461f9ba482d28db78edc
102 N912b7fa55ea84ba7ac08a74023d624ea
103 schema:publisher N304bd61785554a518706b3332397f121
104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052593443
105 https://doi.org/10.1007/11787006_17
106 schema:sdDatePublished 2022-01-01T19:27
107 schema:sdLicense https://scigraph.springernature.com/explorer/license/
108 schema:sdPublisher N45b1acd1d0ac40c28664fd01f79103a4
109 schema:url https://doi.org/10.1007/11787006_17
110 sgo:license sg:explorer/license/
111 sgo:sdDataset chapters
112 rdf:type schema:Chapter
113 N04dc49b7e5534ce0a18e2b595efe7a46 rdf:first N8924ff28edc84ae3baa64105e4fc8460
114 rdf:rest Nddd454535b644b05b21960e99c5fa258
115 N10106dd329c7461f9ba482d28db78edc schema:name dimensions_id
116 schema:value pub.1052593443
117 rdf:type schema:PropertyValue
118 N304bd61785554a518706b3332397f121 schema:name Springer Nature
119 rdf:type schema:Organisation
120 N3855bf1f77cb4db0a9ef73350b3c10aa schema:familyName Wegener
121 schema:givenName Ingo
122 rdf:type schema:Person
123 N439d4e5b8d0042c9be39e03986c56f45 rdf:first N57b519f7839b4bedadb575514d2f56c5
124 rdf:rest N6c1472942dea462190f02c03fe2057fd
125 N45b1acd1d0ac40c28664fd01f79103a4 schema:name Springer Nature - SN SciGraph project
126 rdf:type schema:Organization
127 N57b519f7839b4bedadb575514d2f56c5 schema:familyName Bugliesi
128 schema:givenName Michele
129 rdf:type schema:Person
130 N60ea6329467a4efb95fadc0cb1144cbe rdf:first sg:person.011037626541.00
131 rdf:rest N99370bafb20143788a6088b58605741b
132 N6c1472942dea462190f02c03fe2057fd rdf:first N97aacedc5819423ab47a7f26eb6302f7
133 rdf:rest N04dc49b7e5534ce0a18e2b595efe7a46
134 N8924ff28edc84ae3baa64105e4fc8460 schema:familyName Sassone
135 schema:givenName Vladimiro
136 rdf:type schema:Person
137 N912b7fa55ea84ba7ac08a74023d624ea schema:name doi
138 schema:value 10.1007/11787006_17
139 rdf:type schema:PropertyValue
140 N97aacedc5819423ab47a7f26eb6302f7 schema:familyName Preneel
141 schema:givenName Bart
142 rdf:type schema:Person
143 N99370bafb20143788a6088b58605741b rdf:first sg:person.07776170271.83
144 rdf:rest rdf:nil
145 Nddd454535b644b05b21960e99c5fa258 rdf:first N3855bf1f77cb4db0a9ef73350b3c10aa
146 rdf:rest rdf:nil
147 Nfa8ceb4e18ae4686ab50426f125d07fc schema:isbn 978-3-540-35907-4
148 978-3-540-35908-1
149 schema:name Automata, Languages and Programming
150 rdf:type schema:Book
151 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
152 schema:name Information and Computing Sciences
153 rdf:type schema:DefinedTerm
154 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
155 schema:name Data Format
156 rdf:type schema:DefinedTerm
157 sg:person.011037626541.00 schema:affiliation grid-institutes:grid.6451.6
158 schema:familyName Harnik
159 schema:givenName Danny
160 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037626541.00
161 rdf:type schema:Person
162 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
163 schema:familyName Naor
164 schema:givenName Moni
165 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
166 rdf:type schema:Person
167 grid-institutes:grid.13992.30 schema:alternateName Dept. of Computer Science and Applied Math., Weizmann Institute of Science, Rehovot, Israel
168 schema:name Dept. of Computer Science and Applied Math., Weizmann Institute of Science, Rehovot, Israel
169 rdf:type schema:Organization
170 grid-institutes:grid.6451.6 schema:alternateName Dept. of Computer Science, Technion, Haifa, Israel
171 schema:name Dept. of Computer Science, Technion, Haifa, Israel
172 rdf:type schema:Organization
 




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


...