Cryptology ePrint Archive: Report 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.

Category / Keywords: fuzzy extractor; error-correcting code; computational security

Date: received 6 Aug 2014, last revised 15 Mar 2018

Contact author: yasunaga at se kanazawa-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20180315:062917 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]