On Perfect and Adaptive Security in Exposure-Resilient Cryptography View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001-04-15

AUTHORS

Yevgeniy Dodis , Amit Sahai , Adam Smith

ABSTRACT

We consider the question of adaptive security for two related cryptographic primitives: all-or-nothing transforms and exposure-resilient functions. Both are concerned with retaining security when an intruder learns some bits of a string which is supposed to be secret: all-or-nothing transforms (AONT) protect their input even given partial knowledge of the output; exposure-resilient functions (ERF) hide their output even given partial exposure of their input. Both of these primitives can be defined in the perfect, statistical and computational settings and have a variety of applications in cryptography. In this paper, we study how these notions fare against adaptive adversaries, who may choose which positions of a secret string to observe on the fly.In the perfect setting, we prove a new, strong lower bound on the constructibility of (perfect) AONT. This applies to both standard and adaptively secure AONT. In particular, to hide an input as short as log n bits, the adversary must see no more than half of the n-bit output. This bound also provides a new impossibility result on the existence of (ramp) secret-sharing schemes [6] and relates to a combinatorial problem of independent interest: finding “balanced” colorings of the hypercube.In the statistical setting, we show that adaptivity adds strictly more power to the adversary. We relate and reduce the construction of adaptive ERF's to that of almost-perfect resilient functions [19], for which the adversary can actually set some of the input positions and still learn nothing about the output. We give a probabilistic construction of these functions which is essentially optimal and substantially improves on previous constructions of [19, 5]. As a result, we get nearly optimal adaptively secure ERF's and AONT's. Finally, extending the statistical construction we obtain optimal computational adaptive ERF's, “public-value” AONT's and resilient functions. More... »

PAGES

301-324

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44987-6_19

DOI

http://dx.doi.org/10.1007/3-540-44987-6_19

DIMENSIONS

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


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, New York University, 251 Mercer St, 10012, New York, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.137628.9", 
          "name": [
            "Department of Computer Science, New York University, 251 Mercer St, 10012, New York, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dodis", 
        "givenName": "Yevgeniy", 
        "id": "sg:person.015074130645.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074130645.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "id": "sg:person.014324616157.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014324616157.64"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Main St, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Main St, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Smith", 
        "givenName": "Adam", 
        "id": "sg:person.013307226666.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-04-15", 
    "datePublishedReg": "2001-04-15", 
    "description": "We consider the question of adaptive security for two related cryptographic primitives: all-or-nothing transforms and exposure-resilient functions. Both are concerned with retaining security when an intruder learns some bits of a string which is supposed to be secret: all-or-nothing transforms (AONT) protect their input even given partial knowledge of the output; exposure-resilient functions (ERF) hide their output even given partial exposure of their input. Both of these primitives can be defined in the perfect, statistical and computational settings and have a variety of applications in cryptography. In this paper, we study how these notions fare against adaptive adversaries, who may choose which positions of a secret string to observe on the fly.In the perfect setting, we prove a new, strong lower bound on the constructibility of (perfect) AONT. This applies to both standard and adaptively secure AONT. In particular, to hide an input as short as log n bits, the adversary must see no more than half of the n-bit output. This bound also provides a new impossibility result on the existence of (ramp) secret-sharing schemes [6] and relates to a combinatorial problem of independent interest: finding \u201cbalanced\u201d colorings of the hypercube.In the statistical setting, we show that adaptivity adds strictly more power to the adversary. We relate and reduce the construction of adaptive ERF's to that of almost-perfect resilient functions [19], for which the adversary can actually set some of the input positions and still learn nothing about the output. We give a probabilistic construction of these functions which is essentially optimal and substantially improves on previous constructions of [19, 5]. As a result, we get nearly optimal adaptively secure ERF's and AONT's. Finally, extending the statistical construction we obtain optimal computational adaptive ERF's, \u201cpublic-value\u201d AONT's and resilient functions.", 
    "editor": [
      {
        "familyName": "Pfitzmann", 
        "givenName": "Birgit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44987-6_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42070-5", 
        "978-3-540-44987-4"
      ], 
      "name": "Advances in Cryptology \u2014 EUROCRYPT 2001", 
      "type": "Book"
    }, 
    "keywords": [
      "exposure-resilient functions", 
      "statistical setting", 
      "resilient functions", 
      "statistical construction", 
      "combinatorial problems", 
      "probabilistic construction", 
      "independent interest", 
      "computational setting", 
      "n-bit output", 
      "new impossibility results", 
      "secret string", 
      "partial knowledge", 
      "previous constructions", 
      "variety of applications", 
      "secret sharing scheme", 
      "string", 
      "input position", 
      "impossibility results", 
      "cryptography", 
      "hypercube", 
      "n bits", 
      "function", 
      "coloring", 
      "constructibility", 
      "input", 
      "AONT", 
      "output", 
      "scheme", 
      "more power", 
      "construction", 
      "adaptivity", 
      "adaptive adversary", 
      "existence", 
      "problem", 
      "primitives", 
      "cryptographic primitives", 
      "adversary", 
      "transform", 
      "adaptive security", 
      "bits", 
      "perfect setting", 
      "applications", 
      "results", 
      "position", 
      "notion", 
      "power", 
      "log n bits", 
      "interest", 
      "setting", 
      "variety", 
      "intruders", 
      "security", 
      "questions", 
      "knowledge", 
      "partial exposure", 
      "ERF", 
      "flies", 
      "standards", 
      "half", 
      "exposure", 
      "paper"
    ], 
    "name": "On Perfect and Adaptive Security in Exposure-Resilient Cryptography", 
    "pagination": "301-324", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015139947"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44987-6_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44987-6_19", 
      "https://app.dimensions.ai/details/publication/pub.1015139947"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:37", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_78.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44987-6_19"
  }
]
 

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/3-540-44987-6_19'

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/3-540-44987-6_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44987-6_19'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44987-6_19'


 

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

141 TRIPLES      23 PREDICATES      86 URIs      79 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44987-6_19 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N04c034092c0e42dfa8975b0482d78fd6
4 schema:datePublished 2001-04-15
5 schema:datePublishedReg 2001-04-15
6 schema:description We consider the question of adaptive security for two related cryptographic primitives: all-or-nothing transforms and exposure-resilient functions. Both are concerned with retaining security when an intruder learns some bits of a string which is supposed to be secret: all-or-nothing transforms (AONT) protect their input even given partial knowledge of the output; exposure-resilient functions (ERF) hide their output even given partial exposure of their input. Both of these primitives can be defined in the perfect, statistical and computational settings and have a variety of applications in cryptography. In this paper, we study how these notions fare against adaptive adversaries, who may choose which positions of a secret string to observe on the fly.In the perfect setting, we prove a new, strong lower bound on the constructibility of (perfect) AONT. This applies to both standard and adaptively secure AONT. In particular, to hide an input as short as log n bits, the adversary must see no more than half of the n-bit output. This bound also provides a new impossibility result on the existence of (ramp) secret-sharing schemes [6] and relates to a combinatorial problem of independent interest: finding “balanced” colorings of the hypercube.In the statistical setting, we show that adaptivity adds strictly more power to the adversary. We relate and reduce the construction of adaptive ERF's to that of almost-perfect resilient functions [19], for which the adversary can actually set some of the input positions and still learn nothing about the output. We give a probabilistic construction of these functions which is essentially optimal and substantially improves on previous constructions of [19, 5]. As a result, we get nearly optimal adaptively secure ERF's and AONT's. Finally, extending the statistical construction we obtain optimal computational adaptive ERF's, “public-value” AONT's and resilient functions.
7 schema:editor N9d902d4c749b44de8f91b03fea226b0b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf9c426a93e4043d580fa767f348dac37
12 schema:keywords AONT
13 ERF
14 adaptive adversary
15 adaptive security
16 adaptivity
17 adversary
18 applications
19 bits
20 coloring
21 combinatorial problems
22 computational setting
23 constructibility
24 construction
25 cryptographic primitives
26 cryptography
27 existence
28 exposure
29 exposure-resilient functions
30 flies
31 function
32 half
33 hypercube
34 impossibility results
35 independent interest
36 input
37 input position
38 interest
39 intruders
40 knowledge
41 log n bits
42 more power
43 n bits
44 n-bit output
45 new impossibility results
46 notion
47 output
48 paper
49 partial exposure
50 partial knowledge
51 perfect setting
52 position
53 power
54 previous constructions
55 primitives
56 probabilistic construction
57 problem
58 questions
59 resilient functions
60 results
61 scheme
62 secret sharing scheme
63 secret string
64 security
65 setting
66 standards
67 statistical construction
68 statistical setting
69 string
70 transform
71 variety
72 variety of applications
73 schema:name On Perfect and Adaptive Security in Exposure-Resilient Cryptography
74 schema:pagination 301-324
75 schema:productId N2a6afa94865f4a10bd3d070f7f78efaa
76 N73dad7e6526f433c94d9eaaa50db2560
77 schema:publisher N201035c2031349a6978001450706386f
78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015139947
79 https://doi.org/10.1007/3-540-44987-6_19
80 schema:sdDatePublished 2022-06-01T22:37
81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
82 schema:sdPublisher N618d157bf8dd4cbd8993cfcf3387a274
83 schema:url https://doi.org/10.1007/3-540-44987-6_19
84 sgo:license sg:explorer/license/
85 sgo:sdDataset chapters
86 rdf:type schema:Chapter
87 N04c034092c0e42dfa8975b0482d78fd6 rdf:first sg:person.015074130645.34
88 rdf:rest N9b196a5fefde41ff93d0b9614919a9ac
89 N201035c2031349a6978001450706386f schema:name Springer Nature
90 rdf:type schema:Organisation
91 N2a6afa94865f4a10bd3d070f7f78efaa schema:name doi
92 schema:value 10.1007/3-540-44987-6_19
93 rdf:type schema:PropertyValue
94 N618d157bf8dd4cbd8993cfcf3387a274 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 N73dad7e6526f433c94d9eaaa50db2560 schema:name dimensions_id
97 schema:value pub.1015139947
98 rdf:type schema:PropertyValue
99 N9b196a5fefde41ff93d0b9614919a9ac rdf:first sg:person.014324616157.64
100 rdf:rest Nd641e4aded39427db553f99e7bb56aa0
101 N9d902d4c749b44de8f91b03fea226b0b rdf:first Ncd3385b46e004d8eb6f4997bd80771af
102 rdf:rest rdf:nil
103 Ncd3385b46e004d8eb6f4997bd80771af schema:familyName Pfitzmann
104 schema:givenName Birgit
105 rdf:type schema:Person
106 Nd641e4aded39427db553f99e7bb56aa0 rdf:first sg:person.013307226666.21
107 rdf:rest rdf:nil
108 Nf9c426a93e4043d580fa767f348dac37 schema:isbn 978-3-540-42070-5
109 978-3-540-44987-4
110 schema:name Advances in Cryptology — EUROCRYPT 2001
111 rdf:type schema:Book
112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
113 schema:name Information and Computing Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
116 schema:name Data Format
117 rdf:type schema:DefinedTerm
118 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.116068.8
119 schema:familyName Smith
120 schema:givenName Adam
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
122 rdf:type schema:Person
123 sg:person.014324616157.64 schema:affiliation grid-institutes:grid.16750.35
124 schema:familyName Sahai
125 schema:givenName Amit
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014324616157.64
127 rdf:type schema:Person
128 sg:person.015074130645.34 schema:affiliation grid-institutes:grid.137628.9
129 schema:familyName Dodis
130 schema:givenName Yevgeniy
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074130645.34
132 rdf:type schema:Person
133 grid-institutes:grid.116068.8 schema:alternateName Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Main St, 02139, Cambridge, MA, USA
134 schema:name Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Main St, 02139, Cambridge, MA, USA
135 rdf:type schema:Organization
136 grid-institutes:grid.137628.9 schema:alternateName Department of Computer Science, New York University, 251 Mercer St, 10012, New York, NY, USA
137 schema:name Department of Computer Science, New York University, 251 Mercer St, 10012, New York, NY, USA
138 rdf:type schema:Organization
139 grid-institutes:grid.16750.35 schema:alternateName Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA
140 schema:name Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA
141 rdf:type schema:Organization
 




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


...