Please use this identifier to cite or link to this item:
Title: Optimal Algebraic Manipulation Detection Codes in the Constant-Error Model
Authors: Padró, Carles
Xing, Chaoping
Cramer, Ronald
Issue Date: 2015
Source: Cramer, R., Padró, C., Xing, C. (2015). Optimal algebraic manipulation detection codes in the constant-error model. Dodis, Y., & Nielsen, J. B. (eds), Lecture Notes in Computer Science, 9014, 481-501.
Series/Report no.: Lecture Notes in Computer Science
Abstract: Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as keyless combinatorial authentication codes that provide security in the presence of an oblivious, 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 ϵ 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 ρ of the tag satisfies ρ ≥ log log M + Ωϵ(1). In this paper, we shall call AMD codes meeting this lower bound optimal. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor 2 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 ϵ can be chosen as an arbitrarily small positive real number.
ISSN: 0302-9743
DOI: 10.1007/978-3-662-46494-6_20
Schools: School of Physical and Mathematical Sciences 
Rights: © 2015 International Association for Cryptologic Research. This is the author created version of a work that has been peer reviewed and accepted for publication in Lecture Notes in Computer Science, published by Springer Berlin Heidelberg on behalf of International Association for Cryptologic Research. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document.  The published version is available at: [10.1007/978-3-662-46494-6_20].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
CPX_GAMD_TCC15_v4.pdf377.6 kBAdobe PDFThumbnail

Citations 20

Updated on Sep 29, 2023

Page view(s) 50

Updated on Sep 30, 2023

Download(s) 50

Updated on Sep 30, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.