Paper 2018/681

A Reusable Fuzzy Extractor with Practical Storage Size

Jung Hee Cheon, Jinhyuck Jeong, Dongwoo Kim, and Jongchan Lee


After the concept of a Fuzzy Extractor (FE) was rst introduced by Dodis et al. , it has been regarded as one of the candidate solutions for key management utilizing biometric data. With a noisy input such as biometrics, FE generates a public helper value and a random secret key which is reproducible given another input similar to the original input. However, "helper values" may cause some leakage of information when generated repeatedly by correlated inputs, thus reusability should be considered as an important property. Recently, Canetti et al. (Eurocrypt 2016) proposed a FE satisfying both reusability and robustness with inputs from low-entropy distributions. Their strategy, the so-called Sample-then-Lock method, is to sample many partial strings from a noisy input string and to lock one secret key with each partial string independently. In this paper, modifying this reusable FE, we propose a new FE with size-reduced helper data hiring a threshold scheme. Our new FE also satises both reusability and robustness, and requires much less storage memory than the original. To show the advantages of this scheme, we analyze and compare our scheme with the original in concrete parameters of the biometric, IrisCode. As a result, on 1024-bit inputs, with false rejection rate 0.5 and error tolerance 0.25, while the original requires about 1TB for each helper value, our scheme requires only 300MB with an additional 1.35GB of common data which can be used for all helper values.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Australasian Conference on Information Security and Privacy (ACISP) 2018
threshold cryptographykey managementsecret sharingapplicationsfuzzy extractorbiometric authentication
Contact author(s)
wlsyrlekd @ snu ac kr
2018-07-16: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Jinhyuck Jeong and Dongwoo Kim and Jongchan Lee},
      title = {A Reusable Fuzzy Extractor with Practical Storage Size},
      howpublished = {Cryptology ePrint Archive, Paper 2018/681},
      year = {2018},
      doi = {10.1007/978-3-319-93638-3_3},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.