Welcome to the resource topic for 2014/116
Title:
Optimal Algebraic Manipulation Detection Codes in the Constant-Error Model
Authors: Ronald Cramer, Carles Padrö, Chaoping Xing
Abstract:Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as {\em keyless} combinatorial authentication codes that provide security in the presence of an {\em oblivious}, {\em algebraic} attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive constant error probability \epsilon in combination with unbounded cardinality M of the message space. There are several applications where this model makes sense. Adapting a known bound to this regime, it follows that the binary length \rho of the tag satisfies \rho\geq \log \log M + \Omega_{\epsilon}(1). In this paper, we shall call AMD codes meeting this lower bound {\em optimal}. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor~2 {\em off} from being optimal. By a generic enhancement using error-correcting codes, these parameters can be further improved but remain suboptimal. Reaching optimality efficiently turns out to be surprisingly nontrivial. Owing to our refinement of the mathematical perspective on AMD codes, which focuses on symmetries of codes, we propose novel constructive principles. This leads to an explicit construction based on certain BCH codes that improves the parameters of the polynomial construction and to an efficient randomized construction of optimal AMD codes based on certain quasi-cyclic codes. In all our results, the error probability \epsilon can be chosen as an arbitrarily small positive real number.
ePrint: https://eprint.iacr.org/2014/116
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .