Paper 2008/030

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

Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, 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}

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. This is the full version of a paper accepted to Eurocrypt 2008
Keywords
Secret SharingFuzzy ExtractorsInformation TheoryAuthentication Codes
Contact author(s)
wichs @ cs nyu edu
History
2008-02-06: last of 2 revisions
2008-01-28: received
See all versions
Short URL
https://ia.cr/2008/030
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/030,
      author = {Ronald Cramer and Yevgeniy Dodis and Serge Fehr and Carles Padró and Daniel Wichs},
      title = {Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors},
      howpublished = {Cryptology ePrint Archive, Paper 2008/030},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/030}},
      url = {https://eprint.iacr.org/2008/030}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.