Reusable Fuzzy Extractors for Low-Entropy Distributions View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016-04-28

AUTHORS

Ran Canetti , Benjamin Fuller , Omer Paneth , Leonid Reyzin , Adam Smith

ABSTRACT

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person’s biometric is enrolled with multiple unrelated organizations).We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates.Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates—lower than those supported by prior (nonreusable) constructions—assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates.We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, building a computationally secure and an information-theoretically secure construction for large-alphabet sources. More... »

PAGES

117-146

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-49890-3_5

DOI

http://dx.doi.org/10.1007/978-3-662-49890-3_5

DIMENSIONS

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


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": "Tel Aviv University, Tel Aviv, Israel", 
          "id": "http://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Boston University, Boston, MA, USA", 
            "Tel Aviv University, Tel Aviv, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Canetti", 
        "givenName": "Ran", 
        "id": "sg:person.012320111457.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Lincoln Laboratory, Lexington, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.504876.8", 
          "name": [
            "Boston University, Boston, MA, USA", 
            "MIT Lincoln Laboratory, Lexington, MA, 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": "Paneth", 
        "givenName": "Omer", 
        "id": "sg:person.014073524511.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68"
        ], 
        "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-04-28", 
    "datePublishedReg": "2016-04-28", 
    "description": "Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person\u2019s biometric is enrolled with multiple unrelated organizations).We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates.Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates\u2014lower than those supported by prior (nonreusable) constructions\u2014assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates.We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, building a computationally secure and an information-theoretically secure construction for large-alphabet sources.", 
    "editor": [
      {
        "familyName": "Fischlin", 
        "givenName": "Marc", 
        "type": "Person"
      }, 
      {
        "familyName": "Coron", 
        "givenName": "Jean-S\u00e9bastien", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-49890-3_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-49889-7", 
        "978-3-662-49890-3"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "fuzzy extractor", 
      "initial enrollment phase", 
      "noisy readings", 
      "enrollment phase", 
      "large alphabet sources", 
      "random oracle model", 
      "reusable fuzzy extractor", 
      "error rate", 
      "computational security", 
      "oracle model", 
      "hash function", 
      "secure construction", 
      "same secret", 
      "lower entropy rate", 
      "noisy version", 
      "noisy sources", 
      "extractor", 
      "min-entropy rate", 
      "binary strings", 
      "security", 
      "secrets", 
      "random subsequences", 
      "minentropy", 
      "multiple times", 
      "strings", 
      "entropy rate", 
      "subsequences", 
      "noise", 
      "key", 
      "information", 
      "entropy distribution", 
      "construction", 
      "different structural properties", 
      "additional structure", 
      "version", 
      "source distribution", 
      "structural assumptions", 
      "assumption", 
      "tolerates", 
      "model", 
      "source", 
      "multiple readings", 
      "reading", 
      "time", 
      "subsequent reading", 
      "distribution", 
      "function", 
      "structure", 
      "phase", 
      "structural properties", 
      "rate", 
      "converts", 
      "properties"
    ], 
    "name": "Reusable Fuzzy Extractors for Low-Entropy Distributions", 
    "pagination": "117-146", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014328379"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-49890-3_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-49890-3_5", 
      "https://app.dimensions.ai/details/publication/pub.1014328379"
    ], 
    "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_89.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-49890-3_5"
  }
]
 

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-49890-3_5'

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-49890-3_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-49890-3_5'

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-49890-3_5'


 

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

157 TRIPLES      23 PREDICATES      78 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-49890-3_5 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nc91e064678704185bb0ec2ac1d685fa2
4 schema:datePublished 2016-04-28
5 schema:datePublishedReg 2016-04-28
6 schema:description Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person’s biometric is enrolled with multiple unrelated organizations).We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates.Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates—lower than those supported by prior (nonreusable) constructions—assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates.We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, building a computationally secure and an information-theoretically secure construction for large-alphabet sources.
7 schema:editor N0dad8a4e7879438883e377d8bdb7c95f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nb69f1b79493545c597d5637f69cb794f
12 schema:keywords additional structure
13 assumption
14 binary strings
15 computational security
16 construction
17 converts
18 different structural properties
19 distribution
20 enrollment phase
21 entropy distribution
22 entropy rate
23 error rate
24 extractor
25 function
26 fuzzy extractor
27 hash function
28 information
29 initial enrollment phase
30 key
31 large alphabet sources
32 lower entropy rate
33 min-entropy rate
34 minentropy
35 model
36 multiple readings
37 multiple times
38 noise
39 noisy readings
40 noisy sources
41 noisy version
42 oracle model
43 phase
44 properties
45 random oracle model
46 random subsequences
47 rate
48 reading
49 reusable fuzzy extractor
50 same secret
51 secrets
52 secure construction
53 security
54 source
55 source distribution
56 strings
57 structural assumptions
58 structural properties
59 structure
60 subsequences
61 subsequent reading
62 time
63 tolerates
64 version
65 schema:name Reusable Fuzzy Extractors for Low-Entropy Distributions
66 schema:pagination 117-146
67 schema:productId N795c5930c9704396b09f2fa4c4792216
68 N7a706422edd843e99d121b63d1836bfa
69 schema:publisher N159446992be540dea55a0da81252643e
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014328379
71 https://doi.org/10.1007/978-3-662-49890-3_5
72 schema:sdDatePublished 2022-06-01T22:37
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher N888a45c54426494e87e8908eb9d39d39
75 schema:url https://doi.org/10.1007/978-3-662-49890-3_5
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N0dad8a4e7879438883e377d8bdb7c95f rdf:first Nfac9d6244df54b968e02ececb1727b0c
80 rdf:rest Nb2d3819e31bf4fe0b7bd2157b3b16f6e
81 N159446992be540dea55a0da81252643e schema:name Springer Nature
82 rdf:type schema:Organisation
83 N58fb8ea29c664ac68b3afbf91dae8ca5 schema:familyName Coron
84 schema:givenName Jean-Sébastien
85 rdf:type schema:Person
86 N795c5930c9704396b09f2fa4c4792216 schema:name doi
87 schema:value 10.1007/978-3-662-49890-3_5
88 rdf:type schema:PropertyValue
89 N7a706422edd843e99d121b63d1836bfa schema:name dimensions_id
90 schema:value pub.1014328379
91 rdf:type schema:PropertyValue
92 N7b113156ff834a2c8b5ab162a2f5faf8 rdf:first sg:person.013307226666.21
93 rdf:rest rdf:nil
94 N888a45c54426494e87e8908eb9d39d39 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 N9e6a98ed228047968c94a436f3b8c5b6 rdf:first sg:person.016627532062.10
97 rdf:rest N7b113156ff834a2c8b5ab162a2f5faf8
98 Nb2d3819e31bf4fe0b7bd2157b3b16f6e rdf:first N58fb8ea29c664ac68b3afbf91dae8ca5
99 rdf:rest rdf:nil
100 Nb69f1b79493545c597d5637f69cb794f schema:isbn 978-3-662-49889-7
101 978-3-662-49890-3
102 schema:name Advances in Cryptology – EUROCRYPT 2016
103 rdf:type schema:Book
104 Nbb9e56fddb4f4ed7a2a8edf942f91130 rdf:first sg:person.013244656177.72
105 rdf:rest Ne1d8cb757b01456c93752c3e771b7d87
106 Nc91e064678704185bb0ec2ac1d685fa2 rdf:first sg:person.012320111457.74
107 rdf:rest Nbb9e56fddb4f4ed7a2a8edf942f91130
108 Ne1d8cb757b01456c93752c3e771b7d87 rdf:first sg:person.014073524511.68
109 rdf:rest N9e6a98ed228047968c94a436f3b8c5b6
110 Nfac9d6244df54b968e02ececb1727b0c schema:familyName Fischlin
111 schema:givenName Marc
112 rdf:type schema:Person
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
117 schema:name Data Format
118 rdf:type schema:DefinedTerm
119 sg:person.012320111457.74 schema:affiliation grid-institutes:grid.12136.37
120 schema:familyName Canetti
121 schema:givenName Ran
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012320111457.74
123 rdf:type schema:Person
124 sg:person.013244656177.72 schema:affiliation grid-institutes:grid.504876.8
125 schema:familyName Fuller
126 schema:givenName Benjamin
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013244656177.72
128 rdf:type schema:Person
129 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.29857.31
130 schema:familyName Smith
131 schema:givenName Adam
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
133 rdf:type schema:Person
134 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.189504.1
135 schema:familyName Paneth
136 schema:givenName Omer
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
138 rdf:type schema:Person
139 sg:person.016627532062.10 schema:affiliation grid-institutes:grid.189504.1
140 schema:familyName Reyzin
141 schema:givenName Leonid
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016627532062.10
143 rdf:type schema:Person
144 grid-institutes:grid.12136.37 schema:alternateName Tel Aviv University, Tel Aviv, Israel
145 schema:name Boston University, Boston, MA, USA
146 Tel Aviv University, Tel Aviv, Israel
147 rdf:type schema:Organization
148 grid-institutes:grid.189504.1 schema:alternateName Boston University, Boston, MA, USA
149 schema:name Boston University, Boston, MA, USA
150 rdf:type schema:Organization
151 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, University Park, PA, USA
152 schema:name Pennsylvania State University, University Park, PA, USA
153 rdf:type schema:Organization
154 grid-institutes:grid.504876.8 schema:alternateName MIT Lincoln Laboratory, Lexington, MA, USA
155 schema:name Boston University, Boston, MA, USA
156 MIT Lincoln Laboratory, Lexington, MA, USA
157 rdf:type schema:Organization
 




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


...