When Are Fuzzy Extractors Possible? View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016-11-09

AUTHORS

Benjamin Fuller , Leonid Reyzin , Adam Smith

ABSTRACT

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key.We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the ideal security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor.We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy min-entropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy.In this paper, we show that fuzzy min-entropy is sufficient for information theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor.Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. Our second main result is that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. We show three flavors of this impossibility result: for standard fuzzy extractors, for fuzzy extractors that are allowed to sometimes be wrong, and for secure sketches, which are the main ingredient of most fuzzy extractor constructions. More... »

PAGES

277-306

Book

TITLE

Advances in Cryptology – ASIACRYPT 2016

ISBN

978-3-662-53886-9
978-3-662-53887-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53887-6_10

DOI

http://dx.doi.org/10.1007/978-3-662-53887-6_10

DIMENSIONS

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


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": "University of Connecticut, Storrs, CT, USA", 
          "id": "http://www.grid.ac/institutes/grid.63054.34", 
          "name": [
            "University of Connecticut, Storrs, CT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fuller", 
        "givenName": "Benjamin", 
        "id": "sg:person.013244656177.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013244656177.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Boston University, Boston, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.189504.1", 
          "name": [
            "Boston University, Boston, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reyzin", 
        "givenName": "Leonid", 
        "id": "sg:person.016627532062.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016627532062.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, University Park, PA, 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": "2016-11-09", 
    "datePublishedReg": "2016-11-09", 
    "description": "Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key.We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the ideal security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor.We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy min-entropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy.In this paper, we show that fuzzy min-entropy is sufficient for information theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor.Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. Our second main result is that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. We show three flavors of this impossibility result: for standard fuzzy extractors, for fuzzy extractors that are allowed to sometimes be wrong, and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.", 
    "editor": [
      {
        "familyName": "Cheon", 
        "givenName": "Jung Hee", 
        "type": "Person"
      }, 
      {
        "familyName": "Takagi", 
        "givenName": "Tsuyoshi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53887-6_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53886-9", 
        "978-3-662-53887-6"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "fuzzy extractor", 
      "noisy sources", 
      "min-entropy", 
      "min-entropy measures", 
      "high-entropy secret", 
      "computational security", 
      "secure sketch", 
      "ideal security", 
      "program obfuscation", 
      "noisy readings", 
      "fuzzy extraction", 
      "noisy distribution", 
      "key extraction", 
      "family of sources", 
      "single extractor", 
      "security", 
      "extractor", 
      "impossibility results", 
      "extractor constructions", 
      "ambitious goal", 
      "secrets", 
      "key", 
      "adversary", 
      "obfuscation", 
      "extraction", 
      "functionality", 
      "relevant sources", 
      "goal", 
      "sketch", 
      "information", 
      "construction", 
      "guess", 
      "main ingredients", 
      "source", 
      "results", 
      "distribution W", 
      "second main result", 
      "sufficient conditions", 
      "success", 
      "main results", 
      "progress", 
      "recent progress", 
      "measures", 
      "reading", 
      "distribution", 
      "precise distribution", 
      "converts", 
      "minimum conditions", 
      "values", 
      "conditions", 
      "properties", 
      "existence", 
      "ingredients", 
      "possible sources", 
      "flavor", 
      "contrast", 
      "hardness", 
      "family", 
      "evidence", 
      "paper"
    ], 
    "name": "When Are Fuzzy Extractors Possible?", 
    "pagination": "277-306", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084920151"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53887-6_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53887-6_10", 
      "https://app.dimensions.ai/details/publication/pub.1084920151"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:32", 
    "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_344.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53887-6_10"
  }
]
 

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-53887-6_10'

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-53887-6_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53887-6_10'

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-53887-6_10'


 

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

145 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53887-6_10 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N4202a05c57ef42a383317845ffe8d3cc
4 schema:datePublished 2016-11-09
5 schema:datePublishedReg 2016-11-09
6 schema:description Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key.We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the ideal security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor.We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy min-entropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy.In this paper, we show that fuzzy min-entropy is sufficient for information theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor.Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. Our second main result is that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. We show three flavors of this impossibility result: for standard fuzzy extractors, for fuzzy extractors that are allowed to sometimes be wrong, and for secure sketches, which are the main ingredient of most fuzzy extractor constructions.
7 schema:editor N45cb342a2fea492ca0ac8eca6c6e736e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N41506243cf78405db3dafceaa82a5114
12 schema:keywords adversary
13 ambitious goal
14 computational security
15 conditions
16 construction
17 contrast
18 converts
19 distribution
20 distribution W
21 evidence
22 existence
23 extraction
24 extractor
25 extractor constructions
26 family
27 family of sources
28 flavor
29 functionality
30 fuzzy extraction
31 fuzzy extractor
32 goal
33 guess
34 hardness
35 high-entropy secret
36 ideal security
37 impossibility results
38 information
39 ingredients
40 key
41 key extraction
42 main ingredients
43 main results
44 measures
45 min-entropy
46 min-entropy measures
47 minimum conditions
48 noisy distribution
49 noisy readings
50 noisy sources
51 obfuscation
52 paper
53 possible sources
54 precise distribution
55 program obfuscation
56 progress
57 properties
58 reading
59 recent progress
60 relevant sources
61 results
62 second main result
63 secrets
64 secure sketch
65 security
66 single extractor
67 sketch
68 source
69 success
70 sufficient conditions
71 values
72 schema:name When Are Fuzzy Extractors Possible?
73 schema:pagination 277-306
74 schema:productId N8186f219cf14485dad8267cb57a4fd0c
75 Nba6108cfa41c4756b1f1591f36078eb7
76 schema:publisher Nc7c53f06cf374d22b5e890a0194fd44d
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084920151
78 https://doi.org/10.1007/978-3-662-53887-6_10
79 schema:sdDatePublished 2022-06-01T22:32
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher Na82123f5a65943339272f9ba9192b550
82 schema:url https://doi.org/10.1007/978-3-662-53887-6_10
83 sgo:license sg:explorer/license/
84 sgo:sdDataset chapters
85 rdf:type schema:Chapter
86 N2054e47251b04ab3b9b9dd1a741c5853 schema:familyName Takagi
87 schema:givenName Tsuyoshi
88 rdf:type schema:Person
89 N41506243cf78405db3dafceaa82a5114 schema:isbn 978-3-662-53886-9
90 978-3-662-53887-6
91 schema:name Advances in Cryptology – ASIACRYPT 2016
92 rdf:type schema:Book
93 N4202a05c57ef42a383317845ffe8d3cc rdf:first sg:person.013244656177.72
94 rdf:rest Nae42c26852a84a5bb9eb8cfa4649379c
95 N45cb342a2fea492ca0ac8eca6c6e736e rdf:first N4d27ca7ba4cb4b16b1b5bc08fe8f1f90
96 rdf:rest Nc103cd3ef3ea4ad0be3ecf62931385a4
97 N4d27ca7ba4cb4b16b1b5bc08fe8f1f90 schema:familyName Cheon
98 schema:givenName Jung Hee
99 rdf:type schema:Person
100 N6fd9affa979844a882ced00c6b3b50b4 rdf:first sg:person.013307226666.21
101 rdf:rest rdf:nil
102 N8186f219cf14485dad8267cb57a4fd0c schema:name doi
103 schema:value 10.1007/978-3-662-53887-6_10
104 rdf:type schema:PropertyValue
105 Na82123f5a65943339272f9ba9192b550 schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
107 Nae42c26852a84a5bb9eb8cfa4649379c rdf:first sg:person.016627532062.10
108 rdf:rest N6fd9affa979844a882ced00c6b3b50b4
109 Nba6108cfa41c4756b1f1591f36078eb7 schema:name dimensions_id
110 schema:value pub.1084920151
111 rdf:type schema:PropertyValue
112 Nc103cd3ef3ea4ad0be3ecf62931385a4 rdf:first N2054e47251b04ab3b9b9dd1a741c5853
113 rdf:rest rdf:nil
114 Nc7c53f06cf374d22b5e890a0194fd44d schema:name Springer Nature
115 rdf:type schema:Organisation
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
120 schema:name Data Format
121 rdf:type schema:DefinedTerm
122 sg:person.013244656177.72 schema:affiliation grid-institutes:grid.63054.34
123 schema:familyName Fuller
124 schema:givenName Benjamin
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013244656177.72
126 rdf:type schema:Person
127 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.29857.31
128 schema:familyName Smith
129 schema:givenName Adam
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
131 rdf:type schema:Person
132 sg:person.016627532062.10 schema:affiliation grid-institutes:grid.189504.1
133 schema:familyName Reyzin
134 schema:givenName Leonid
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016627532062.10
136 rdf:type schema:Person
137 grid-institutes:grid.189504.1 schema:alternateName Boston University, Boston, MA, USA
138 schema:name Boston University, Boston, MA, USA
139 rdf:type schema:Organization
140 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, University Park, PA, USA
141 schema:name Pennsylvania State University, University Park, PA, USA
142 rdf:type schema:Organization
143 grid-institutes:grid.63054.34 schema:alternateName University of Connecticut, Storrs, CT, USA
144 schema:name University of Connecticut, Storrs, CT, USA
145 rdf:type schema:Organization
 




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


...