Paper 2021/1228

Computational Robust (Fuzzy) Extractors for CRS-dependent Sources with Minimal Min-entropy

Hanwen Feng, The University of Sydney
Qiang Tang, The University of Sydney

Robust (fuzzy) extractors are very useful for, e.g., authenticated exchange from shared weak secret and remote biometric authentication against active adversaries. They enable two parties to extract the same uniform randomness with the ``helper'' string. More importantly, they have an authentication mechanism built in that tampering of the ``helper'' string will be detected. Unfortunately, as shown by Dodis and Wichs, in the information-theoretic setting, a robust extractor for an $(n,k)$-source requires $k>n/2$, which is in sharp contrast with randomness extractors which only require $k=\omega(\log n)$. Existing work either relies on random oracles or introduces CRS and works only for CRS-independent sources (even in the computational setting). In this work, we give a systematic study of robust (fuzzy) extractors for general CRS-dependent sources. We show in the information-theoretic setting, the same entropy lower bound holds even in the CRS model; we then show we can have robust extractors in the computational setting for general CRS-dependent source that is only with minimal entropy. At the heart of our construction lies a new primitive called $\kappa$-MAC that is unforgeable with a weak key and hides all partial information about the key (both against auxiliary input), by which we can compile any conventional randomness extractor into a robust one. We further augment $\kappa$-MAC to defend against ``key manipulation" attacks, which yields a robust fuzzy extractor for CRS-dependent sources.

Note: A preliminary version of this paper appeared in \textit{Theory of Cryptography Conference}- TCC 2021, pp. 689-717. This full version includes proofs for all theorems and lemmas. Among them, the proofs for Lemma 7 and Theorem 4 are redone, giving more accurate bounds on adversary advantages. It also corrects a flaw that the original fuzzy unforgeability definition of \macname\ is unnecessarily strong and cannot be achieved by our construction. Furthermore, all results are revised to be applicable to sources with \textit{average-case} conditional min-entropy which is more general than the \textit{worst-case} notion used in the preliminary version.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2021
Robust extractorFuzzy extractorAuthenticated key exchangeMACCRS
Contact author(s)
hanwen feng @ sydney edu au
qiang tang @ sydney edu au
2023-01-19: revised
2021-09-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hanwen Feng and Qiang Tang},
      title = {Computational Robust (Fuzzy) Extractors for CRS-dependent Sources with Minimal Min-entropy},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1228},
      year = {2021},
      doi = {10.1007/978-3-030-90453-1_24},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.