Cryptology ePrint Archive: Report 2014/605
On the Possibilities and Limitations of Computational Fuzzy Extractors
Kenji Yasunaga and Kosuke Yuzawa
Abstract: Fuller et~al. (Asiacrypt 2013) studied on computational fuzzy extractors,
and showed, as a negative result, that the existence of a computational ``secure sketch''
implies the existence of an information-theoretically secure sketch with slightly weaker parameters.
In this work, we show a similar negative result such that
the existence of a computational fuzzy extractor satisfying a certain computational condition implies the existence of
an information-theoretic fuzzy extractor with slightly weaker parameters.
The condition is that the generation procedure of the fuzzy extractor can be efficiently invertible.
This result implies that to circumvent the limitations of information-theoretic fuzzy extractors,
we need to employ computational fuzzy extractors in which the generation procedure cannot be efficiently invertible.
As positive results, we present a construction of computational fuzzy extractor
based on a leakage-resilient key encapsulation mechanism and a construction based on a strong decisional Diffie-Hellman assumption.
Category / Keywords: fuzzy extractor, error-correcting code, leakage-resilient cryptography, key encapsulation mechanism
Date: received 6 Aug 2014, last revised 26 Apr 2015
Contact author: yasunaga at se kanazawa-u ac jp
Available format(s): PDF | BibTeX Citation
Version: 20150427:052848 (All versions of this report)
Short URL: ia.cr/2014/605
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]