TY - GEN

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

AU - Cramer, Ronald

AU - Dodis, Yevgeniy

AU - Fehr, Serge

AU - Padró, Carles

AU - Wichs, Daniel

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=44449149774&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44449149774&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78967-3_27

DO - 10.1007/978-3-540-78967-3_27

M3 - Conference contribution

AN - SCOPUS:44449149774

SN - 3540789669

SN - 9783540789666

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 471

EP - 488

BT - Advances in Cryptology - EUROCRYPT 2008 - 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

T2 - 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2008

Y2 - 13 April 2008 through 17 April 2008

ER -