\begin{itemize} \item We show how to efficiently convert any linear secret sharing scheme into a {\em robust secret sharing scheme}, which ensures that no \emph{unqualified subset} of players can modify their shares and cause the reconstruction of some value $s'\neq s$.
\item We show how how to build nearly optimal {\em robust fuzzy extractors} for several natural metrics. Robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets, such as biometrics, by relying only on {\em non-robust public storage}. In the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. Our construction relies on a randomly chosen common reference string (CRS) available to all parties. \end{itemize}
Category / Keywords: foundations / Secret Sharing, Fuzzy Extractors, Information Theory, Authentication Codes Publication Info: This is the full version of a paper accepted to Eurocrypt 2008 Date: received 22 Jan 2008, last revised 6 Feb 2008 Contact author: wichs at cs nyu edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20080206:171158 (All versions of this report) Short URL: ia.cr/2008/030