Paper 2014/605

On the Limitations of Computational Fuzzy Extractors

Kenji Yasunaga and Kosuke Yuzawa

Abstract

We present a negative result of fuzzy extractors with computational security. Specifically, we show that, under a certain computational condition, the existence of a computational fuzzy extractor implies the existence of an information-theoretic fuzzy extractor with slightly weaker parameters. The condition is that the generation procedure of the fuzzy extractor is efficiently invertible by an injective function. Our result implies that to circumvent the limitations of information-theoretic fuzzy extractors, we need to employ computational fuzzy extractors that are not invertible by injective functions.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
fuzzy extractorerror-correcting codecomputational security
Contact author(s)
yasunaga @ se kanazawa-u ac jp
History
2018-03-15: last of 5 revisions
2014-08-13: received
See all versions
Short URL
https://ia.cr/2014/605
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/605,
      author = {Kenji Yasunaga and Kosuke Yuzawa},
      title = {On the Limitations of Computational Fuzzy Extractors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/605},
      year = {2014},
      url = {https://eprint.iacr.org/2014/605}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.