**Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors**

*Ronald Cramer and Yevgeniy Dodis and Serge Fehr and Carles Padr\'o and Daniel Wichs*

**Abstract: ** Consider an abstract storage device $\Sigma(\G)$ that can hold a
single element $x$ from a fixed, publicly known finite group $\G$.
Storage is private in the sense that an adversary does not have read
access to $\Sigma(\G)$ at all. However, $\Sigma(\G)$ is non-robust in the sense
that the adversary can modify its contents by adding some offset $\Delta \in \G$.
Due to the privacy of the storage device, the value $\Delta$ can only depend on an adversary's {\em a priori} knowledge of $x$. We introduce a new primitive called an {\em
algebraic manipulation detection} (AMD) code, which encodes a source $s$ into a value $x$ stored on $\Sigma(\G)$ so that any tampering
by an adversary will be detected, except with a small error probability $\delta$. We give a nearly optimal construction of AMD codes,
which can flexibly accommodate arbitrary choices for the length of the source $s$ and security level $\delta$. We use this construction in two applications:

\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)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]