Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors

Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, Daniel Wichs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Consider an abstract storage device that can hold a single element x from a fixed, publicly known finite group . Storage is private in the sense that an adversary does not have read access to at all. However, is non-robust in the sense that the adversary can modify its contents by adding some offset . 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 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2008 - 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Pages471-488
Number of pages18
DOIs
StatePublished - 2008
Event27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2008 - Istanbul, Turkey
Duration: Apr 13 2008Apr 17 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2008
CountryTurkey
CityIstanbul
Period4/13/084/17/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors'. Together they form a unique fingerprint.

Cite this