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 *a-priori* knowledge of x.

We introduce a new primitive called an 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:

-- We show how to efficiently convert any linear secret sharing scheme
 into a robust secret sharing scheme, which ensures that no unqualified
 subset of players can modify their shares and cause the reconstruction
 of some value s different from s.

-- We show how how to build nearly optimal 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
 *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.

The paper is available at http://people.csail.mit.edu/dodis/ps/rob-ext.ps

==============================