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

Consider an abstract storage device

$\Sigma(\mathcal{G})$

that can hold a single element

x

from a fixed, publicly known finite group

$\mathcal{G}$

. Storage is private in the sense that an adversary does not have read access to

$\Sigma(\mathcal{G})$

at all. However,

$\Sigma(\mathcal{G})$

is non-robust in the sense that the adversary can modify its contents by adding some offset

$\Delta \in \mathcal{G}$

. Due to the privacy of the storage device, the value

Δ

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(\mathcal{G})$

so that any tampering by an adversary will be detected. 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. 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

′ ≠ 

s

.

We show 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.