Deterministic History-Independent Strategies for Storing Information on Write-Once Memories View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Tal Moran , Moni Naor , Gil Segev

ABSTRACT

Motivated by the challenging task of designing “secure” vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most K elements from a large universe of size N on write-once memories in a manner that does not reveal the insertion order of the elements. Whereas previously known constructions were either inefficient (required Θ(K2) memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements.In addition, we consider one of the classical distributed computing problems: Conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors. More... »

PAGES

303-315

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-73419-2
978-3-540-73420-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73420-8_28

DOI

http://dx.doi.org/10.1007/978-3-540-73420-8_28

DIMENSIONS

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


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": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Moran", 
        "givenName": "Tal", 
        "id": "sg:person.012022173111.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012022173111.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Segev", 
        "givenName": "Gil", 
        "id": "sg:person.016423726453.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "Motivated by the challenging task of designing \u201csecure\u201d vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most K elements from a large universe of size N on write-once memories in a manner that does not reveal the insertion order of the elements. Whereas previously known constructions were either inefficient (required \u0398(K2) memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements.In addition, we consider one of the classical distributed computing problems: Conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.", 
    "editor": [
      {
        "familyName": "Arge", 
        "givenName": "Lars", 
        "type": "Person"
      }, 
      {
        "familyName": "Cachin", 
        "givenName": "Christian", 
        "type": "Person"
      }, 
      {
        "familyName": "Jurdzi\u0144ski", 
        "givenName": "Tomasz", 
        "type": "Person"
      }, 
      {
        "familyName": "Tarlecki", 
        "givenName": "Andrzej", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-73420-8_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-73419-2", 
        "978-3-540-73420-8"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "universe of elements", 
      "multiple-access channel", 
      "cryptographic techniques", 
      "poly-logarithmic factor", 
      "hostile environment", 
      "computing problems", 
      "adversarial attacks", 
      "challenging task", 
      "such environments", 
      "insertion order", 
      "basic building blocks", 
      "information storage mechanism", 
      "large universe", 
      "information storage", 
      "storage mechanism", 
      "conflict resolution", 
      "write", 
      "environment", 
      "size n", 
      "building blocks", 
      "security", 
      "memory", 
      "task", 
      "attacks", 
      "technique", 
      "tight connection", 
      "information", 
      "set", 
      "undesirable properties", 
      "storage", 
      "elements", 
      "block", 
      "channels", 
      "order", 
      "resolution", 
      "construction", 
      "connection", 
      "number", 
      "strategies", 
      "time", 
      "manner", 
      "mechanism", 
      "amount", 
      "setting", 
      "universe", 
      "size", 
      "addition", 
      "properties", 
      "total amount", 
      "majority", 
      "factors", 
      "problem", 
      "vote storage mechanisms", 
      "powerful adversarial attacks", 
      "non-adaptive conflict resolution", 
      "Deterministic History-Independent Strategies", 
      "History-Independent Strategies"
    ], 
    "name": "Deterministic History-Independent Strategies for Storing Information on Write-Once Memories", 
    "pagination": "303-315", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009768729"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-73420-8_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-73420-8_28", 
      "https://app.dimensions.ai/details/publication/pub.1009768729"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:26", 
    "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_53.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-73420-8_28"
  }
]
 

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-540-73420-8_28'

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-540-73420-8_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73420-8_28'

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-540-73420-8_28'


 

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

146 TRIPLES      23 PREDICATES      82 URIs      75 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-73420-8_28 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N37f6c929bbf34efd94525df02888f0fd
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description Motivated by the challenging task of designing “secure” vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most K elements from a large universe of size N on write-once memories in a manner that does not reveal the insertion order of the elements. Whereas previously known constructions were either inefficient (required Θ(K2) memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements.In addition, we consider one of the classical distributed computing problems: Conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.
7 schema:editor N9917cff972a24b20ae8a4927bcdcf9ab
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8471f2b8fe894c5f9e184e2460075b26
12 schema:keywords Deterministic History-Independent Strategies
13 History-Independent Strategies
14 addition
15 adversarial attacks
16 amount
17 attacks
18 basic building blocks
19 block
20 building blocks
21 challenging task
22 channels
23 computing problems
24 conflict resolution
25 connection
26 construction
27 cryptographic techniques
28 elements
29 environment
30 factors
31 hostile environment
32 information
33 information storage
34 information storage mechanism
35 insertion order
36 large universe
37 majority
38 manner
39 mechanism
40 memory
41 multiple-access channel
42 non-adaptive conflict resolution
43 number
44 order
45 poly-logarithmic factor
46 powerful adversarial attacks
47 problem
48 properties
49 resolution
50 security
51 set
52 setting
53 size
54 size n
55 storage
56 storage mechanism
57 strategies
58 such environments
59 task
60 technique
61 tight connection
62 time
63 total amount
64 undesirable properties
65 universe
66 universe of elements
67 vote storage mechanisms
68 write
69 schema:name Deterministic History-Independent Strategies for Storing Information on Write-Once Memories
70 schema:pagination 303-315
71 schema:productId N92d792e54b124a28b91377f364fb0a57
72 Nbdda4579bc2743f89d674f768b89bce1
73 schema:publisher N12ca0493842f4683b1d4983b43c39556
74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009768729
75 https://doi.org/10.1007/978-3-540-73420-8_28
76 schema:sdDatePublished 2022-01-01T19:26
77 schema:sdLicense https://scigraph.springernature.com/explorer/license/
78 schema:sdPublisher Nf86aa8b3ce674b508588d8d8188bd1de
79 schema:url https://doi.org/10.1007/978-3-540-73420-8_28
80 sgo:license sg:explorer/license/
81 sgo:sdDataset chapters
82 rdf:type schema:Chapter
83 N02acdc6e90af498d9fa045ddd32569af rdf:first sg:person.07776170271.83
84 rdf:rest Ne544baa657a747e09153560deb892dc3
85 N12ca0493842f4683b1d4983b43c39556 schema:name Springer Nature
86 rdf:type schema:Organisation
87 N37f6c929bbf34efd94525df02888f0fd rdf:first sg:person.012022173111.00
88 rdf:rest N02acdc6e90af498d9fa045ddd32569af
89 N3dbf6238fc01406db566e879366fb947 schema:familyName Arge
90 schema:givenName Lars
91 rdf:type schema:Person
92 N44617b1553be4e7f953ee9f29adea5af rdf:first N7a47ad4fdf424080b4e6b75ec199f946
93 rdf:rest N6e16a0d653fe4d549d043a9dee5947f1
94 N6e16a0d653fe4d549d043a9dee5947f1 rdf:first N7f6ac413429449d3b049b5632ef0dff7
95 rdf:rest rdf:nil
96 N7a47ad4fdf424080b4e6b75ec199f946 schema:familyName Jurdziński
97 schema:givenName Tomasz
98 rdf:type schema:Person
99 N7f6ac413429449d3b049b5632ef0dff7 schema:familyName Tarlecki
100 schema:givenName Andrzej
101 rdf:type schema:Person
102 N8471f2b8fe894c5f9e184e2460075b26 schema:isbn 978-3-540-73419-2
103 978-3-540-73420-8
104 schema:name Automata, Languages and Programming
105 rdf:type schema:Book
106 N92d792e54b124a28b91377f364fb0a57 schema:name dimensions_id
107 schema:value pub.1009768729
108 rdf:type schema:PropertyValue
109 N9534b99f042e4b1c915806d1eba082d6 rdf:first Nd12c829d20aa4b20b13d6650a5eb03ad
110 rdf:rest N44617b1553be4e7f953ee9f29adea5af
111 N9917cff972a24b20ae8a4927bcdcf9ab rdf:first N3dbf6238fc01406db566e879366fb947
112 rdf:rest N9534b99f042e4b1c915806d1eba082d6
113 Nbdda4579bc2743f89d674f768b89bce1 schema:name doi
114 schema:value 10.1007/978-3-540-73420-8_28
115 rdf:type schema:PropertyValue
116 Nd12c829d20aa4b20b13d6650a5eb03ad schema:familyName Cachin
117 schema:givenName Christian
118 rdf:type schema:Person
119 Ne544baa657a747e09153560deb892dc3 rdf:first sg:person.016423726453.97
120 rdf:rest rdf:nil
121 Nf86aa8b3ce674b508588d8d8188bd1de schema:name Springer Nature - SN SciGraph project
122 rdf:type schema:Organization
123 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
124 schema:name Information and Computing Sciences
125 rdf:type schema:DefinedTerm
126 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
127 schema:name Data Format
128 rdf:type schema:DefinedTerm
129 sg:person.012022173111.00 schema:affiliation grid-institutes:grid.13992.30
130 schema:familyName Moran
131 schema:givenName Tal
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012022173111.00
133 rdf:type schema:Person
134 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
135 schema:familyName Segev
136 schema:givenName Gil
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
138 rdf:type schema:Person
139 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
140 schema:familyName Naor
141 schema:givenName Moni
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
143 rdf:type schema:Person
144 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
145 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
146 rdf:type schema:Organization
 




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


...