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

Hanwen Feng, Qiang Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Robust (fuzzy) extractors are very useful for, e.g., authenticated key exchange from a shared weak secret and remote biometric authentication against active adversaries. They enable two parties to extract the same uniform randomness with a “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= ω(log n). Existing works either rely on random oracles or introduce CRS and work only for CRS-independent sources (even in the computational setting). In this work, we give a systematic study about 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. We further extend our construction to robust fuzzy extractors. Along the way, we propose a new primitive called κ -MAC, which is unforgeable with a weak key and hides all partial information about the key (both against auxiliary input); it may be of independent interests.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 19th International Conference, TCC 2021, Proceedings
EditorsKobbi Nissim, Brent Waters, Brent Waters
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages29
ISBN (Print)9783030904524
StatePublished - 2021
Externally publishedYes
Event19th International Conference on Theory of Cryptography, TCC 2021 - Raleigh, United States
Duration: Nov 8 2021Nov 11 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13043 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Conference on Theory of Cryptography, TCC 2021
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Computational Robust (Fuzzy) Extractors for CRS-Dependent Sources with Minimal Min-entropy'. Together they form a unique fingerprint.

Cite this