Title | Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors |
---|---|

Booktitle | IACR Eprint archive |

Pages | |

Year | 2008 |

URL | http://eprint.iacr.org/2008/030 |

Author | Ronald Cramer |

Author | Yevgeniy Dodis |

Author | Carles Padró |

Author | Serge Fehr |

Author | 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} |

@misc{eprint-2008-17707, title={Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors}, booktitle={IACR Eprint archive}, keywords={foundations / Secret Sharing, Fuzzy Extractors, Information Theory, Authentication Codes}, url={http://eprint.iacr.org/2008/030}, note={This is the full version of a paper accepted to Eurocrypt 2008 wichs@cs.nyu.edu 13915 received 22 Jan 2008, last revised 6 Feb 2008}, author={Ronald Cramer and Yevgeniy Dodis and Carles Padró and Serge Fehr and Daniel Wichs}, year=2008 }