On the Possibilities and Limitations of Computational Fuzzy Extractors
Kenji Yasunaga, Kosuke Yuzawa · 2015
Fuller et al. (Asiacrypt 2013) studied on computational fuzzy extractors, and showed, as a negative result, that the existence of a computational \secure implies the existence of an information-theo 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-theo 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-theo 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-resilien key encapsulation mechanism and a construction based on a strong decisional Diffie-Hellman assumption.