CryptoDB
Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors
| Authors: | |
|---|---|
| Download: | |
| 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} |
BibTeX
@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
}